• Algorithm
• Autonomous Systems
• Motion Planning
• Optimal Control
• Optimization
• Robotics

Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly-exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical per- formance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed (i.i.d.) random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certifi- cation for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random sampling sequences. It is natural to wonder whether the theoretical guarantees and practical performance of sampling-based algorithms would hold if these algorithms were to be de-randomized, i.e., run on a deterministic, as opposed to ran- dom sampling sequence. This is an important question, as de-randomized planners would significantly simplify the certification process (as needed for safety-critical applications), enable the use of offline computation (particularly important for planning under differen- tial constraints or in high-dimensional spaces(exactly the regime for which sampling-based planners are designed), and, in the case of lattice sequences, drastically simplify a number of operations (e.g., locating nearby samples).
Results in this sense, have been recently achieved by [2] for purely geometric motion planning problems by employing low L2-dispersion sampling sequences. However, this ap- proach has proven to be limited for motion planning under differential constraints, probably because Euclidean distance is no longer an adequate measure of how difficult is to join two given points in the configuration space.
On the basis of these considerations, an appealing venue for extending the determinis- tic sampling approach to kino-dynamic motion planning appears to be the development of system-specific sampling strategies designed ad hoc to cover the configuration space uni- formly, in terms of the control effort required to steer the systems from a given point to its nearest sample.
The author aims to develop and theoretically characterize such sampling strategies for two particular classes of dynamics system: systems with linear affine dynamics and driftless control affine (DCA) systems as well as outlining possible heuristics to extend these methodologies to more general examples of non-linear systems.