Simple and efficient algorithms for computing smooth, collision-free feedback laws over given cell decompositions

Stephen R. Lindemann, Steven M. La Valle

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)600-621
Number of pages22
JournalInternational Journal of Robotics Research
Issue number5
StatePublished - May 2009


  • Collision avoidance
  • Feedback control
  • Motion planning
  • Navigation functions
  • Potential fields
  • Vector fields

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Simple and efficient algorithms for computing smooth, collision-free feedback laws over given cell decompositions'. Together they form a unique fingerprint.

Cite this