Search-Based Planning:
Toward High Dimensionality and Differential Constraints

Many real-world planning problems push the limits of traditional AI solutions. Competent reasoning systems, such as robots, must make split-second decisions, while facing considerable challenges in their environment. Systematic search is a traditional planning tool due to a number of beneficial features, yet it does not scale well to many realistic planning problems. This tutorial attempts to demonstrate that a large class of real-world hard problems – involving high dimensionality and differential constraints – can be solved efficiently using systematic graph search enabled with algorithmic and representation improvements.

• Introduction
  
• Search-based planning overview,
• Motivation, applications,
  
• Modeling strategies for search-based planning,
  • Action sampling,
    
  • Generating motion primitives,
    
• Planning strategies,
  • Review of heuristic search,
    
  • Any-angle search-based planning,
  • Search-based planning in high-dimensionality setting.

While tree-based techniques, including randomized approaches, have been applied to many hard planning problems, graph methods offer certain advantages. In addition to enabling useful search paradigms, such as reuse of previous computation, they can provide solution quality guarantees, stronger completeness properties and consistency in performance. In addition, they can yield concrete bounds on worst-case runtime, thereby justifying hard real-time implementations – an increasing interest to technologists. However, it is recognized that they are limited in scalability. Motivated by these considerations, the tutorial presents an array of recent advances that attempt to overcome these limitations.

The objective of the tutorial is to synthesize established and recent results, to propose new directions of inquiry to the research community, as well as to suggest field-validated ideas to the industrial audience.

The discussion will be illustrated with plentiful examples, including recent fielded robotics systems such as nonholonomic mining trucks, autonomous cars (including Boss, the winner of the DARPA Urban Challenge), high-DOF mobile manipulators, autonomous aerial vehicles and quadruped robots, among others.

We anticipate the tutorial to be engaging to AI and robotics theoreticians interested in novel representations for planning as well as to developers interested in deploying capable reasoning systems. In particular, three categories of attendees of the AAAI-2012 conference will find the proposed tutorial useful:

• Students, who are interested in learning about the state of the art in representation and graph design for high-performance motion planning,
• Established researchers, who wish to relate their work to this area,
• Industry technologists, who would like to develop functional and reliable planning solutions in a variety of automation industries, such as automotive, mining, agriculture and others.