Reactive Integrated Motion Planning and Execution

Andreas G. Hofmann, Enrique Fernández-González, Justin Helbert, Scott D. Smith, Brian Charles WilliamsIJCAI 2015

Introduction

Standard motion planning frameworks, such as ROS MoveIt!, often struggle in dynamic, unstructured environments. These systems typically assume a static environment during the planning phase, lack support for complex temporal constraints (e.g., synchronizing with a conveyor belt), and often discard valuable control information by replanning from scratch for every task. To address these challenges, the Chekhov system provides a reactive motion planning and execution framework designed for near-instantaneous adaptation and robust execution under temporal requirements.

System Architecture and Methods

Chekhov utilizes a Tube-based Roadmap (TRM) approach, which structures motion control into a two-layer policy. This architecture allows the system to bridge the gap between high-level pathfinding and low-level reactive control.

The Chekhov system architecture, highlighting the integration of the roadmap compiler, reactive motion planner, and executive controller.

The Upper Layer: Roadmap Graph

The system maintains a graph of robot poses where edges represent feasible movements. Unlike standard search algorithms, Chekhov employs an incremental All-Pairs Shortest Path (APSP) algorithm. This allows the system to maintain optimal paths between all points in the graph simultaneously. When an obstacle is detected, the graph is updated incrementally rather than being rebuilt, significantly reducing latency.

The Lower Layer: Flow Tubes

A key innovation of Chekhov is the use of "Flow Tubes" instead of single-trajectory lines. Each edge in the roadmap is a bundle of feasible trajectories that account for the robot's dynamic limits (velocity, acceleration) and temporal flexibility. This "wiggle room" allows the robot to handle minor disturbances or delays locally without triggering a full replan.

The Executive

A dedicated Executive component monitors execution in real-time. If a disturbance is small, the Executive adjusts timing within the flow tube. If a path is completely blocked, it triggers a fast lookup from the APSP planner to find an alternative route immediately.

Performance and Reactivity

The system was evaluated using a simulated 7-DOF Barrett WAM manipulator in the OpenRAVE environment. In comparative benchmarks against standard planners like RRT and PRM, Chekhov demonstrated superior efficiency. The mean planning time for Chekhov was recorded at 0.0425 seconds, significantly faster than RRT (0.188s) and PRM (0.12s).

Sequence of a robotic arm reactively avoiding a dynamic obstacle while maintaining its goal trajectory.

When obstacles were introduced, the incremental APSP updates took between 0.97s and 2.57s on average. While not instantaneous, this speed enables fluid adaptation in industrial settings where humans and robots share a workspace. Furthermore, because Chekhov reuses a pre-computed roadmap, the resulting motions are more consistent and predictable to human observers than the stochastic paths generated by traditional sampling-based planners.

Conclusion and Future Work

Chekhov demonstrates that treating flexibility as a "first-class citizen" through flow tubes allows for highly reactive and temporally aware robotic motion. While the current implementation relies on offline pre-computation and fixed roadmap nodes, future work aims to incorporate sampling-based node generation to allow the roadmap to grow dynamically. Additionally, parallelizing the APSP algorithm on GPU architectures could further reduce update times, making the system even more responsive to complex, high-speed environmental changes.

Summary updated

BibTeX
@inproceedings{hofmann2015reactive,
  author = {Andreas G. Hofmann and Enrique Fernández-González and Justin Helbert and Scott D. Smith and Brian Charles Williams},
  title = {{Reactive Integrated Motion Planning and Execution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure