Title | ||
---|---|---|
Decomposition algorithm for global reachability analysis on a time-varying graph with an application to planetar exploration |
Abstract | ||
---|---|---|
Hot air (Montgolfiere) balloons represent a promising vehicle system for possible future exploration of planets and moons with thick atmospheres such as Venus and Titan. To go to a desired location, this vehicle can primarily use the horizontal wind that varies with altitude, with a small help of its own actuation. A main challenge is how to plan such trajectory in a highly nonlinear and time-varying wind field. This paper poses this trajectory planning as a graph search on the space-time grid and addresses its computational aspects. When capturing various time scales involved in the wind field over the duration of long exploration mission, the size of the graph becomes excessively large. We show that the adjacency matrix of the graph is block-triangular, and by exploiting this structure, we decompose the large planning problem into several smaller subproblems, whose memory requirement stays almost constant as the problem size grows. The approach is demonstrated on a global reachability analysis of a possible Titan mission scenario. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/IROS.2009.5354578 | St. Louis, MO |
Keywords | Field | DocType |
time-varying wind field,time-varying graph,problem size,long exploration mission,horizontal wind,graph search,decomposition algorithm,global reachability analysis,possible titan mission scenario,possible future exploration,wind field,promising vehicle system,large planning problem,adjacency matrix,moons,titan,data mining,planning,dijkstra s algorithm,wind velocity,matrix,trajectory,matrix decomposition,reachability,color,planets,dijkstras algorithm,indexing terms,algorithms,space time,decomposition,graph theory | Graph theory,Adjacency matrix,Mathematical optimization,Wind speed,Computer science,Matrix decomposition,Algorithm,Reachability,Trajectory,Grid,Dijkstra's algorithm | Conference |
ISBN | Citations | PageRank |
978-1-4244-3804-4 | 3 | 0.57 |
References | Authors | |
3 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshiaki Kuwata | 1 | 324 | 23.28 |
Lars Blackmore | 2 | 30 | 3.85 |
Michael Wolf | 3 | 9 | 1.06 |
Nanaz Fathpour | 4 | 10 | 1.26 |
Claire Newman | 5 | 10 | 1.26 |
Alberto Elfes | 6 | 1470 | 416.36 |