Kavraki Lab

Motion planning research has been successful in developing planning algorithms which are effective for solving problems with complicated geometric and kinematic constraints. Various applications in robotics and in other fields demand additional physical realism. Some progress has been made for non-holonomic systems. However systems with significant drift, underactuation and discrete system changes remain challenging for existing planning techniques particularly as the dimensionality of the state space increases.

We have developed a novel technique for exploring the set of reachable states for a robot with dynamics using tree-based planning which we call the Path-Directed Subdivision Tree Exploration planner (PDST-EXPLORE). PDST-EXPLORE is a sampling-based method which takes a substantially different approach from other tree-based exploration planners. Specifically, our planner represents samples as path segments rather than individual states and uses non-uniform subdivisions of the state space to estimate coverage. This change avoids many of the problems that previous sampling-based planners have had with milestone placement, metrics and coverage estimation. We use a deterministic update schedule together with randomized path generation to adaptively strike a balance between greedy exploration and methodical search. We have obtained a proof of probabilistic completeness for the planner which assumes very little about the specific robot system the planner operates.

Exploring reachable free space of a second-order differential drive robot using PDST

Planning for a car using PDST and the ODE physics-based simulator

In the sampling-based planning literature, there have been a few studies on generating paths for robots with second-order non-linear dynamics. The specific problem instances that appeared were the lane-change problem for a second-order car-like robot, the control of a spacecraft with omni-directional thrusters in a cage, second-order differential drive robots moving in a maze, and a second-order blimp-like robot moving around pillars. Motivated by the above applications as well as others such as dynamic obstacle manipulation, part manipulation with force fields, pursuit-evasion problems and hybrid system verification, our research aims to enlarge the domain and complexity of planning problems that can be solved by developing algorithmic techniques which improve adaptability and efficiency. We are particularily interested in applications with severe underactuation, significant drift, high dimensionality, discrete system changes that occur at boundary conditions and finally a system which is not reduceable to a system with lower order dynamics. This work has two concrete goals in the context of planning applications that demand a high degree of physical realism: the development of online motion planners that can provide stability and completeness guarantees and the development of offline motion planners that can be used interactively in prototyping as tools for feasibility and safety testing in complex environments.

Planning for a weight lifter using PDST and the ODE physics-based simulator

Solution for a tough second-order dynamics planning task called “The Game of Koules”

The above planning task is based loosely on a Unix game called the game of Koules. Our version of Koules is a multi-agent second-order dynamical system where inter-agent collisions are resolved by elastic collision. The agents are discs which operate in the unit square. Elastic collisions cause discrete system changes by instantaneously causing velocity discontinuities. One agent is a robot (ship) that has four different controls and the other agents (koules) move according to a force-field function determined by the current state of the system. The ship wins the game by pushing or bouncing the koules in the boundary of the workspace without touching the boundary itself. The principle challenge posed by our version of the game of Koules is twofold. Firstly, the ship is difficult to control precisely: it has a bounded turning radius and directed acceleration which cause a delay before the ship’s speed can be decreased. This is a serious problem if the ship is moving quickly towards the boundary. Secondly, the trajectories of the koules are locally and independently determined and cannot be directly influenced by the ship. In order to change the velocity of a koule, the ship must collide with it. To collide with a koule, the ship must solve a planning problem to rendezvous with it. The complex interactions caused by multiple collisions make it difficult to determine whether a solution state is close, distant or unreachable from the current state.

Short technical description

  1. A tree of samples is constructed iteratively. The root is a sample of duration 0 consisting only of the initial state.
  2. A priority queue of samples is also maintained. The samples are ordered according to a scoring scheme.
  3. At every iteration, the sample with lowest score is selected. From a state along this sample, a branch is propagated.
  4. A subdivision of an application-specific space (usually a projection of the state space) is maintained such that no sample spans more than one cell in the subdivision. This allows the planner to guarantee coverage of the search space without using a metric. When a sample is selected for branching, the subdivision cell containing that sample is split. This may cause some of the contained samples to be split as well.