Adaptive Model-predictive Motion Planning for Navigation in Complex Environments

Abstract

Outdoor mobile robot motion planning and navigation is a challenging problem in artificial intelligence. The search space density and dimensionality, system dynamics and environmental interaction complexity, and the perceptual horizon limitation all contribute to the difficultly of this problem. It is hard to generate a motion plan between arbitrary boundary states that considers sophisticated vehicle dynamics and all feasible actions for nontrivial mobile robot systems. Accomplishing these goals in real time is even more challenging because of dynamic environments and updating perception information. This thesis develops effective search spaces for mobile robot trajectory generation, motion planning, and navigation in complex environments. Complex environments are defined as worlds where locally optimal motion plans are numerous and where the sensitivity of the cost function is highly dependent on state and motion model fidelity. Examples include domains where obstacles are prevalent, terrain shape is varied, and the consideration of terramechanical effects is important. Three specific contributions are accomplished. First, a model-predictive trajectory generation technique is developed that numerically linearizes and inverts general predictive motion models to determine parameterized actions that satisfy the two-point boundary value problem. Applications on a number of mobile robot platforms (including skidsteered field robots, planetary rovers with actively articulating chassis, mobile manipulators, and autonomous automobiles) demonstrate the versatility and generality of the presented approach. Second, an adaptive search space is presented that exploits environmental information to maintain feasibility and locally optimize the mapping between nodes and states. Sequential search in the relaxed motion planning graph is shown to produce better (shorter/faster/lowerrisk) trajectories in dense obstacle fields without modifying the graph topology. Results demonstrate that a coarse, adaptive search space can produce better solutions faster than dense, fixed search spaces in sufficiently complex environments. Lastly, a receding-horizon model-predictive control method that exploits structure from sequential search to determine trajectory following actions is presented. The action space is parameterized by the regional motion plan and subsequently relaxed through unconstrained optimization. Examples are shown to effectively navigate intricate paths in a natural environment while maintaining a constant horizon.