computational robotics

from tasks to motions

Motion Planning with Dynamics

Combining Sampling-based Motion Planning with Discrete Search

The deployment of robots in exploration, navigation, search-and-rescue missions requires the capability to efficiently plan motions that enable the robots to reach desired goal regions while avoiding collisions. In order to follow the planned motions in the physical world, it is essential to take into account the underlying motion dynamics during planning. Motion planning with dynamics, however, poses significant computational challenges. In addition to collision avoidance, the planned motions need to satisfy differential constraints imposed by the dynamics on position, orientation, velocity, acceleration, and curvature. As an illustration, differential constraints ensure, for example, that wheels on a car-like robot do not slide sideways.

To effectively incorporate dynamics, we propose treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multi-layered framework is developed, which combines discrete search and sampling-based motion planning. The overall effect is that the framework significantly improves the computational efficiency, as demonstrated by simulation experiments with dynamical models of ground and flying vehicles.

Related Publications

  • Plaku E (2015): "Region-Guided and Sampling-Based Tree Search for Motion Planning with Dynamics." IEEE Transactions on Robotics, in press  [publisher]  [preprint]
  • Le D and Plaku E (2014): “Guiding Sampling-Based Tree Search for Motion Planning with Dynamics via Probabilistic Roadmap Abstractions.“ IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 212--217  [publisher]  [preprint]
  • Plaku E (2013): “Robot Motion Planning with Dynamics as Hybrid Search.” AAAI Conference on Artificial Intelligence, pp. 1415–1421  [publisher]  [preprint]
  • Plaku E (2012): "Guiding Sampling-based Motion Planning by Forward and Backward Discrete Search" Springer LNCS Intelligent Robots and Applications, vol. 7508, pp. 289--300   [publisher]   [preprint]
  • Plaku E (2012): "Motion Planning with Discrete Abstractions and Physics-Based Game Engines" Springer LNCS Motion in Games, pp. 290--301   [publisher]   [preprint]
  • Plaku E (2012): "Motion Planning with Differential Constraints as Guided Search over Continuous and Discrete Spaces." International Symposium on Combinatorial Search, pp. 171--172   [publisher]   [preprint]
  • Plaku E, Kavraki LE, and Vardi MY (2010): "Motion Planning with Dynamics by a Synergistic Combination of Layers of Planning." IEEE Transactions on Robotics, vol. 26(3), pp. 469--482   [publisher]   [preprint]
  • Plaku E, Kavraki LE, and Vardi MY (2008): "Impact of Workspace Decompositions on Discrete Search Leading Continuous Exploration (DSLX) Motion Planning." IEEE International Conference on Robotics and Automation, pp. 3751--3756   [publisher]   [preprint]
  • Plaku E, Kavraki LE, and Vardi MY (2007): "Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning" Robotics: Science and Systems, pp. 326--333   [publisher]   [preprint]