This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Lindemann, S. R. Articles by LaValle, S. M. Search for Related Content Social Bookmarking                         What's this?

Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions

Department of Computer Science University of Illinois Urbana, IL 61801, USA, slindema{at}uiuc.edu

Steven M. LaValle

Department of Computer Science University of Illinois Urbana, IL 61801, USA, lavalle{at}uiuc.edu

This paper presents a novel approach to computing feedback laws in the presence of obstacles. Instead of computing a trajectory between a pair of initial and goal states, our algorithms compute a vector field over the entire state space; all trajectories obtained from following this vector field are guaranteed to asymptotically reach the goal state. As a result, the vector field globally solves the navigation problem and provides robustness to disturbances in sensing and control. The vector field's integral curves (system trajectories) are guaranteed to avoid obstacles and are C smooth. We construct a vector field with these properties by partitioning the space into simple cells, defining local vector fields for each cell, and smoothly interpolating between them to obtain a global vector field. We present an algorithm that computes these feedback controls for a kinematic point robot in an arbitrary dimensional space with piecewise linear boundary; the algorithm requires minimal preprocessing of the environment and is extremely fast during execution. For many practical applications in two-dimensional environments, full computation can be done in milliseconds. We also present an algorithm for computing feedback laws over cylindrical algebraic decompositions, thereby solving a smooth feedback version of the generalized piano movers' problem.

Key Words: motion planning • collision avoidance • navigation functions • feedback control • vector fields • potential fields

The International Journal of Robotics Research, Vol. 28, No. 5, 600-621 (2009)
DOI: 10.1177/0278364908099462


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?