Efficient Hierarchical Robot Motion Planning Under Uncertainty and Hybrid Dynamics

Ajinkya Jain, Scott Niekum

Abstract

Noisy observations coupled with nonlinear dynamics pose one of the biggest challenges in robot motion planning. By decomposing nonlinear dynamics into a discrete set of local dynamics models, hybrid dynamics can be leveraged to make complex planning tractable in a belief space.

Introduction

Robot motion planning is notoriously difficult when combining nonlinear dynamics—such as the sudden change in physics when a gripper touches a surface—with noisy sensor observations. The standard mathematical framework for this, the Partially Observable Markov Decision Process (POMDP), is computationally intensive for long-range planning. Researchers at UT Austin have developed a hierarchical planner that makes these problems tractable by breaking nonlinear dynamics into a sequence of simpler "local" models. By planning in a "hybrid belief space," the robot can leverage physical constraints to reduce its own state uncertainty, resulting in plans that are significantly faster and more robust than traditional approaches.

Methods: Hierarchical Planning and Hybrid Dynamics

The proposed system operates on Hybrid Dynamics, decomposing the environment into a discrete set of local linear models (e.g., "moving in free space" or "sliding on a wall"). It maintains a hybrid belief, tracking both the continuous position distribution and the probability of which discrete dynamics model is active.

The Hierarchy

Planning is divided into two distinct levels:

  1. High-Level Planner: Finds the optimal sequence of local dynamics models to visit, creating a "confidence map" to identify regions that help the robot localize.
  2. Low-Level Planner: Uses Sequential Least Squares Programming (SLSQP) to find the precise, cost-minimized continuous path through the chosen models.
Comparison of Direct Planning (a) vs. Hierarchical Planning (b). The hierarchical approach strategically uses walls to localize, significantly reducing uncertainty (represented by grey circles) compared to the direct method.

Constraints as Sensors

A key feature is that the planner treats physical constraints as resources. If the robot's state uncertainty is high, the planner may choose to bump into a wall. The physical constraint provides "indirect feedback," acting as a high-accuracy sensor to zero out uncertainty in one direction.

Evaluation and Key Results

The planner was evaluated on two main setups: a simulated 2D Walled Domain and a real-world-inspired Airplane Assembly task using YCB objects.

  • Efficiency: In the walled domain, the hierarchical planner found solutions 5 times faster than direct planning approaches.
  • Precision: In the assembly task, the robot achieved a 0.2 cm precision requirement even when initial sensor noise was ten times larger (2.0 cm).
Time steps of the airplane assembly task, demonstrating the robot's ability to achieve high-precision insertion (0.2 cm tolerance) under significant sensor uncertainty.

Conclusion

By separating the logic of mode sequences from the geometry of exact paths, this hierarchical approach bypasses the exponential complexity of long-horizon POMDPs. While the current model requires expert-provided dynamics, future work focuses on autonomously learning these hybrid models from data to create a truly end-to-end system for complex manipulation tasks.

Summary updated

Abstract

Noisy observations coupled with nonlinear dynamics pose one of the biggestchallengesinrobotmotionplanning. Bydecomposingnonlineardynamics into a discrete set of local dynamics models, hybrid dynami...
BibTeX
@inproceedings{jain2018efficient,
  author = {Ajinkya Jain and Scott Niekum},
  title = {{Efficient Hierarchical Robot Motion Planning Under Uncertainty and Hybrid Dynamics}},
  booktitle = {Conference on Robot Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=7tGD5InuDaH},
}
Figure