Research Directions

Optimal Feedback Planning

Reeds-Shepp car optimal trajectory

The majority of motion planning algorithms implement a path-centric discretization, in which a continuous motion planning problem is discretized using a grid [1], a graph [2], or a tree [3], and a feasible solution is found on the given discrete structure. This approach, despite its appealing simplicity, is prone to several fundamental flaws. For example, path constrained on a grid are limited with respect to possible travel directions. By increasing the connectivity of the grid, this problem is mitigated, but it cannot be eliminated entirely. Moreover, paths, which are restricted to a finite set, may fail to converge to a desired solution even if the disretization is arbitrary fine, as it was demonstrated in [4]. Thus, we depart from a path-centric discretization and introduce a feedback-centric discretization.

Dubins car optimal trajectory

The feedback-centric approach discretizes a feedback control law instead of the set of all possible path. Thus, trajectories of a robot are not limited to an arbitrary finite set of trajectories. Instead, an uncountably many trajectories are generated when a provided feedback controller is integrated. A discrete set of feedback controllers is then searched for a feasible solution. In [4], we discuss how to implement a feedback-centric motion planning algorithm for an shortest path problem in "d"-dimensional world with obstacles.

Additionally, with the use of a feedback control law, we alleviate the problem of following the precomputed path using complex path following controllers. Instead, the motion strategy is given by a feedback, and it can be executed using a simple controller.

References

[1] A. Stentz, “The focussed D* algorithm for Real-Time replanning,” in the International Joint Conference on Artificial Intelligence, Aug. 1995.

[2] L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” Robotics and Automation, IEEE Transactions on, vol. 12, no. 4, pp. 566 – 580, Aug. 1996.

[3] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning,” The International Journal of Robotics Research, vol. 20, no. 5, pp. 378-400, May 2001.

[4] D.S. Yershov and S.M. LaValle, “Simplicial Dijkstra and A* Algorithms: From Graphs to Continuous Spaces,” Advanced Robotics, Vol. 26, no. 17, pp. 2065 – 2085, 2012.

Decidability of the General Motion Planning Problem

Function space sample

Computing a motion plan is a central problem in robotics. However, the digital on-board Computers are the fundamental limiting factor for these kind of computations. Indeed, considering all possible motion planning algorithms, only countable set of motion strategies can be computed. On the other hand, a continuous model of the World allows uncountably many motion plans. This fundamental limitation of digital controllers raises a question: “whether the general motion planning problem is solvable using motion planning algorithms?”

A similar question arises in theoretical computer science. Classes of decidable, semidecidable, and undecidable problems are determined by the existence of complete and semicomplete algorithms. These concepts were later reintroduced for the motion planning problem, and complete algorithms for piano movers problem were presented in [1 – 2].

In [3], we show that the general motion planning problem under an open-loop control model and differential constraints is semidecidable. We construct a function space of trajectories with an associated metric such that the solution set (a set of feasible collision-free trajectories) is open with respect to this metric. Thus, by providing a dense sample sequence in the trajectory function space, we present a semicomplete sampling-based motion planning algorithm for the general motion planning problem.

References

[1] J. Canny, “Computing roadmaps of general Semi-Algebraic sets,” The Computer Journal, vol. 36, no. 5, pp. 504 – 514, 1993.

[2] J. T. Schwartz and M. Sharir, “On the “piano movers” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,” Communications on pure and applied mathematics, vol. 36, no. 3, pp. 345 – 398, 1983.

[3] D.S. Yershov and S.M. LaValle, “Sufficient Conditions for the Existence of Resolution Complete Planning Algorithms,” in Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2010.