Paper Info
Title
Locally optimal decomposition for autonomous obstacle avoidance with the Tunnel-MILP algorithm.
Abstract
The Tunnel-MILP algorithm is a three stage path planning method for 2-D environments that relies on the iden- tification of a sequence of convex polygons to form an obstacle free tunnel through which to plan a dynamically feasible path. This work investigates two aspects of the algorithm. First, a greedy cut method is proposed for improved decomposition of the environment, resulting in fewer regions than existing algorithms. Second, the effect of the decomposition on the resulting solution is investigated, and conditions are presented to demonstrate that the resulting tunnel cannot be improved to yield a better solution. This ensures that the tunnel provided does not adversely affect the resulting dynamically feasible trajectory, and guarantees local optimality of the solution. I. INTRODUCTION With the increasing demand for autonomous vehicles, there is a pressing need for fast algorithms to plan trajec- tories through complex environments. Several examples of projects that require this technology are: search and rescue, reconnaissance, surveillance, and disaster response. These projects have motivated the Stanford Testbed of Autonomous Rotorcraft for Multi-Agent Control (STARMAC), a system used to test novel algorithms for multi-vehicle coordination and autonomous operation (1). Obstacle avoidance is an essential technology for au- tonomous operation and one proposed solution to this prob- lem applies mixed integer linear programming (MILP) ((2), (3)). It is well known that MILP is NP-hard in the number of binary variables required in the problem formulation (4), and so computational requirements grow exponentially as the number of binary variables needed to model the prob- lem increases. Randomized methods, such as probabilistic roadmaps (5), have also been proposed to solve the obstacle avoidance problem, particularly for instances with a very large number of constraints. However, the resulting paths are generally not optimized in distance or time, and can result in winding paths if the vehicle dynamics are incorporated. To address these limitations, the Tunnel-MILP algorithm has been proposed. The algorithm constrains the MILP formulation by restricting the area in which the vehicle is allowed to travel, which significantly reduces the number of binary variables needed (6). Using this restriction, a significant performance increase is realized over the standard MILP formulation. However, only a locally optimal solution can be guaranteed with the Tunnel-MILP algorithm.
Year
DOI
Venue
2008
10.1109/CDC.2008.4739394
CDC
Keywords
Field
DocType
obstacle avoidance,linear programming,convex programming,path planning,trajectory,planning,greedy algorithms,optimization,radio frequency,vehicle dynamics,computational complexity,integer programming
Obstacle avoidance,Motion planning,Mathematical optimization,Control theory,Computer science,Algorithm,Greedy algorithm,Integer programming,Linear programming,Convex optimization,Trajectory,Computational complexity theory
Conference
ISSN
ISBN
Citations 
0191-2216 E-ISBN : 978-1-4244-3124-3
978-1-4244-3124-3
5
PageRank 
References 
Authors
0.74
6
3
Name
Order
Citations
PageRank
Michael P. Vitus126420.08
Steven Lake Waslander244346.89
Claire J. Tomlin31491158.05