# Research Directions

## Optimal Feedback Planning

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.

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

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.