Open-SPITE on GitHub

Planning in Changing Environments

Real-world robots operate in dynamic spaces where obstacles, humans, or other robots frequently move. Standard motion planners struggle in these environments because they typically rebuild or discard paths whenever the workspace changes, which causes introduces significant computational delays.


SPITE (Simple Polyhedral Intersection Techniques for modified Environments) is a framework designed to work with any existing planning libary (e.g. OMPL) to efficiently handle dynamic scenarios. SPITE updates a robot’s existing roadmap instead of starting from scratch. By using simple geometric shapes to approximate where the robot will be, SPITE drastically reduces the need for slow, complex collision checks.

Swept-Volume Approximations

SPITE bounds the robot’s motion using simple geometric approximations to use as a heuristic before performing full collision checks:

  • Over-Approximations (Bounding Boxes): A conservative outer box is drawn around the robot’s path. If this box does not hit an obstacle, the motion is definitely safe (Green).
  • Under-Approximations (Splines/Spheres): A simplified skeleton is drawn inside the robot’s path. If an obstacle intersects this inner core, the trajectory is definitely in collision (Red).

Any path that falls between these two bounds has unknown validity (Gray) and requires exact collision checking.

Motion Planning with SPITE

To maximize efficiency during query fulfillment, SPITE utilizes “lazy evaluation”. When searching for a path, the planner greedily prefers paths made of definitely safe (Green) segments. It delays performing computationally expensive exact collision checks on uncertain (Gray) segments until absolutely necessary, minimizing the overall planning time.


Performance Highlights: Compared to traditional Dynamic Roadmap (DRM) and single-query methods, the core SPITE framework achieves up to 40% faster roadmap updates and solves queries up to 60% faster. Furthermore, the initial roadmap pre-processing time is drastically reduced from hours to mere minutes.

Applications to Other Areas

Multi-Robot Motion Planning (MR-SPITE) Scaling motion planning to teams of robots is difficult because pairwise collision checking causes an exponential increase in the required collision checks. MR-SPITE uses geometric approximations of the individual trajectories to quickly determine if a set of concurrent paths is valid. By limiting the number of precise collision checks, the total planning time is reduced by up to 52% for a 16-robot team.


Task and Motion Planning (sLRS) When a robot rearranges objects in a task planning problem, the environment is constantly changing between actions. The semi-Lazy Rearrangement Solver (sLRS) uses SPITE to preemptively estimate if a sequence of moves is viable. This steers the task planner toward the action sequences with higher chances of valid motion plans, reducing failed attempts.

Planning Around Dynamic Obstacles To safely navigate around dynamic obstacles, planners must proactively incorporate predicted future trajectories. Our ongoing work explores extending the SPITE framework to space-time represeentations to work around these predicted trajectories.

Related Published Works

Updated: