Feedback Motion Planning
Motion planning algorithms ordinarily produce a collision-free path,
which is later tracked by some controller that uses feedback. It
makes more sense to incorporate the feedback directly into the plan.
This leads to feedback motion planning (see Chapter 8
of my book), in which the
computed plan indicates which velocity should be acheived at every
point in the collision-free portion of the configuration space (or
phase space). Alternatively, a feedback plan may be encoded as a
navigation function (Rimon, Koditschek, 1990; imagine Lyapunov
functions or cost-to-go functions that account for obstacles). It is
widely known in control theory that feedback is crucial for
robustness; however, this idea has been slow to trickle into motion
planning research. Whereas ordinary planning hands the path off to
another module, a feedback plan is used directly during execution with
sensor feedback. The plan could be the controller itself or one could
design a control law that tracks the velocity field, rather than a
fixed path. Just as in ordinary path planning, there are feasible and
optimal versions of the feedback problem. For the feasible
case, we need only to guarantee that the goal region is reached in
finite time. For the optimal case, execution must be optimal
in time, distance, energy, or some other criterion. Also as in
ordinary path planning, there are both combinatorial (or exact)
and sampling-based algorithms that generate plans. As an
example of combinatorial feedback planning, see
our paper, which shows how to simply
compute smooth vector fields over cell decompositions. It is
suprising that given a cell decomposition,a calculating a smooth
feedback plan over it is virtually free! For more complex problems,
where a cell decomposition is not obtainable, sampling-based
approaches are preferred. For the feasible case, see
our paper
on sampling-based neighborhood graphs. For
the optimal case, we developed a very general Dijkstra-like algorithm
in IJRR 99, and
in AdvRob 12, Dijkstra and A*-like
algorithms for the more particular case Euclidean shortest paths.
Papers on Feedback Motion Planning
Continuous planning with winding constraints using optimal heuristic-driven front propagation. D. S. Yershov, P. Vernaza, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].
Simplicial label correcting algorithms for continuous stochastic shortest path problems. D. S. Yershov and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].
Simplicial Dijkstra and A* algorithms for optimal feedback planning. D. Yershov and S. M. LaValle. Advanced Robotics, 26(17):2065-2085, 2012. [pdf].
Simplicial Dijkstra and A* algorithms for optimal feedback planning. D. Yershov and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2011. [pdf].
Motion planning: Wild frontiers. S. M. LaValle. IEEE Robotics and Automation Society Magazine, 18(2):108-118, 2011. [pdf].
Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. IEEE Transactions on Automatic Control, 57(2):421-434, 2012. [pdf].
Simple and efficient algorithms for computing smooth, collision-free feedback laws over given cell decompositions. S. R. Lindemann and S. M. LaValle. International Journal of Robotics Research, 28(5):600-621, 2009. [pdf].
Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, pages 1803-1808, 2008. [pdf].
Chapter 8: Feedback Motion Planning, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].
Real time feedback control for nonholonomic mobile robots with obstacles. S. R. Lindemann, I. I. Hussein, and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, 2006. [pdf].
Computing smooth feedback plans over cylindrical algebraic decompositions. S. R. Lindemann and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2006. [pdf].
Smoothly blending vector fields for global robot navigation. S. R. Lindemann and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, pages 3353-3559, 2005. [pdf].
The sampling-based neighborhood graph: A framework for planning and executing feedback motion strategies. L. Yang and S. M. LaValle. IEEE Transactions on Robotics and Automation, 20(3):419-432, June 2004. [pdf].
Algorithms for computing numerical optimal feedback motion strategies. S. M. LaValle and P. Konkimalla. International Journal of Robotics Research, 20(9):729-752, September 2001. [pdf].
An improved random neighborhood graph approach. L. Yang and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 254-259, 2002. [pdf].
A framework for planning feedback motion strategies based on a random neighborhood graph. L. Yang and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 544-549, 2000. [pdf].
Efficient computation of optimal navigation functions for nonholonomic planning. P. Konkimalla and S. M. LaValle. In Proceedings First IEEE International Workshop on Robot Motion and Control, pages 187-192, 1999. [pdf].
Numerical computation of optimal navigation functions on a simplicial complex. S. M. LaValle. In P. K. Agarwal, L. E. Kavraki, and M. T. Mason, editors, Robotics: The Algorithmic Perspective, pages 339-350. A K Peters, Wellesley, MA, 1998. [pdf].
Optimizing robot motion strategies for assembly with stochastic models of the assembly process. R. Sharma, S. M. LaValle, and S. A. Hutchinson. IEEE Trans. on Robotics and Automation, 12(2):160-174, April 1996. [pdf].
Optimal motion planning for multiple robots having independent goals. S. M. LaValle and S. A. Hutchinson. IEEE Trans. on Robotics and Automation, 14(6):912-925, December 1998. [pdf].
An objective-based framework for motion planning under sensing and control uncertainties. S. M. LaValle and S. A. Hutchinson. International Journal of Robotics Research, 17(1):19-42, January 1998. [pdf].
On motion planning in changing, partially-predictable environments. S. M. LaValle and R. Sharma. International Journal of Robotics Research, 16(6):775-805, December 1997. [pdf].
Motion planning in stochastic environments: Theory and modeling issues. S. M. LaValle and R. Sharma. In Proceedings IEEE International Conference on Robotics and Automation, pages 3057-3062, 1995. [pdf].
Motion planning in stochastic environments: Applications and computational issues. S. M. LaValle and R. Sharma. In Proceedings IEEE International Conference on Robotics and Automation, pages 3063-3068, 1995. [pdf].
A game-theoretic framework for robot motion planning. S. M. LaValle. PhD thesis, University of Illinois, Urbana-Champaign, USA, July 1995. [pdf].
An objective-based stochastic framework for manipulation planning. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE/RSJ/GI International Conference on Intelligent Robots and Systems, pages 1772-1779, September 1994. [pdf].
Robot motion planning in a changing, partially predictable environment. S. M. LaValle and R. Sharma. In Proceedings IEEE International Symposium on Intelligent Control, pages 261-266, August 1994. [pdf].