Objectives
It is well known that the performance of A* like planners depends heavily on the quality of the heuristic function used to guide the search. If given a well-designed heuristic function these algorithms are computationally fast and generate high-quality solutions, even for relatively high-dimensional problems. However, if there are regions of the search space where heuristic values do not correlate well with the actual cost-to-goal values, the performance of these algorithms can degrade considerably. Consequently, the development of an efficient planner for a specific domain requires the design of a good heuristic function.
However, for many problems, it may be hard to design a single heuristic function that captures all the complexities of the problem. Furthermore, it is hard to ensure that heuristics are admissible (provide lower bounds on the cost-to-goal) and consistent, which is necessary for A* like searches to provide guarantees on completeness and bounds on sub-optimality. Hence, the first part of this workshop describes a novel heuristic search, called Multi-Heuristic A* (MHA*), that takes in multiple, arbitrarily inadmissible heuristic functions in addition to a single consistent heuristic, and simultaneously uses all of them to search in a way that preserves guarantees on completeness and bounds on sub-optimality. The consequences of not having the single consistent heuristic are also discussed. Several examples of practical application of MHA* are given including planning for navigation, full-body manipulation and humanoid planning.
The second part of the workshop explores a set of applications of A* planning and control algorithms that lead to the need for new heuristics, specifically those based on dynamic models that enable the direct generation of trajectories for minimum distance, time, and energy cost functions. This half begins with a description of several problems in robotics that require the use of a dynamic model in planning, including: planning problems such as steep hill climbing or manipulator lifting of heavy loads that are dependent upon ensuring sufficient momentum at key regions of the trajectory; autonomous spacecraft rendezvous in debris fields requiring dynamically feasible planning that ensures rendezvous at zero relative velocity; and motion planning on multiple terrains, which must take into account terrain-dependent changes in dynamic constraints. An A* planner called Sampling Based Model Predictive Optimization (SBMPO) that seamlessly works with dynamics models and various cost functions as well as enabling the direct generation of trajectories is described along with heuristics that enable the planning to be efficient. SBMPO is based on sampling the inputs to the dynamic model that is forward integrated by the algorithm as it develops trajectories (plans).
A brand new set of non-robotic applications is enabled by using a receding horizon and recognizing that SBMPO can base its planning on cost functions that are standard in model predictive control. Control applications that will be described include flow separation control in aeronautic systems, power system control, and automotive engine tuning. An important feature of these problems is that the system dynamics are sufficiently complex that it is not practically feasible to analytically derive search heuristics. Hence, a neural network learning methodology to identify a heuristic through massive online simulation is described. These learned heuristics cannot be expected to be admissible and will change as the dynamic system changes. This leads to a planning problem with multiple potentially inadmissible heuristics that lends itself well to the use of Multi-Heuristic A*. Initial results to connect the two lines of research are presented.
Topics of interest
- Motion Planning
- Model Predictive Control
- A*
- Multiple Heuristics
- Dynamic Heuristics
- Mobile Robots
- Manipulators
- Control Applications
Intended audience
This workshop is intended for researchers in two areas: 1) those who focus on robot planning; the robots can be manipulators, mobile robots, or mobile manipulators; and 2) those who use model predictive control for robot planning and/or control, or control of non-robotic systems.
Although A* and its variants are commonly understood by the planning community, there has been much less focus on the development of heuristics and the use of (possibly multiple) heuristics that are inadmissible. This tutorial will elucidate this important topic and a solution that has been demonstrated in practice. Furthermore, this audience should find of great interest how new analytical and learned heuristics arise when the planning is based on some type of a dynamic model. Although “kinodynamic planning” has been considered in the literature, this workshop will take a broader view of planning and show how almost all planning (even that which is grid-based) can be based upon some dynamic model, one of a variety of cost functions, and appropriate heuristics. If done properly, planning with dynamc models leads to direct trajectory generation. Furthermore, this community will be interested in learning about a general approach to learning heuristics, given the dynamic model on which the planning is based.
Typically, model predictive control (MPC) is thought of separately from planning based on A* and its variants. However, this workshop will show that the two can be integrated so that MPC is accomplished using sampling (of the system inputs) and A* optimization. This will be of substantial interest to MPC researchers in robotics and other application domains.