Motion Planning in a Competitive Environment
Extending MMS to efficiently deal with a dynamic obstacle
We present below our method for extending MMS to efficiently handle a scenario where two robots move in a single environment and compete for reaching several points of interest.
Solving for Multiple Targets
- Computation must be completed very quickly in order to generate correct motion by the time the player's turn is over.
- The opponent robot, seen as a dynamic obstacle, can make any previous plans irrelevant at any given time, especially in crowded scenarios.
- Naively navigating between points of interest by always moving to the closest unvisited free target produced fair results in experiments.
Therefore, rather than doing any sort of APSP planning we employed a simple approach.
A significant speed-up was gained when rather than planning a path to all the POIs and choosing the closest, we first sorted the POIs by their "aerial distance" and then stopped planning paths as soon as we found the shortest possible path between all remaining POIs.
Solving for Difficult Mazes
When performing preprocessing on the MMS planner, the primary objective is to improve the connectivity between connected components in the free space cells graph.
The naive approach of choosing random connectors turned out to have a low yield in difficult mazes. We turned to a different approach, where we choose connectors inside the intersection of the bounding boxes of FSCs. This turned out to have a very high yield compared to the random approach, especially for tight spaces. Further improvements were achieved when we made sure to sample connectors within a limited range of rotations, while sampling the start configuration and all POIs without constraints.
Below are visualizations of the connectors that were chosen in two sample scenarios to improve connectivity between polygons that represented FSCs of angle primitives.
Path Planning in Polygons (with holes)
Another challenge was quickly finding a path between two points in a polygon, which represents an FSCs of an angle primitive. We've examined several solutions:
- Visibility Graph
- Wall Hugging aka Edge Following
- Delaunay Triangulation
Solving for a Dynamic Obstacle
A naive solution to the problem of the dynamic obstacle within the workspace is to recreate the MMS planner every time the opponent robot moves. This means re-doing all the expensive geometric operations of extending obstacles around the player's robot, cutting polygons into FSCs and then finding the connections between them.
Our approach aimed to salvage as much information as possible between turns. Mainly, we retain a "clean" copy of the planner and then subtract the dynamic obstacle every time it moves and fix any FSC-FSC connectivity that was damaged (attempting to move around the dynamic obstacle if possible). In our experiments this yielded an improvement in the order of x1000s when compared to the naive approach.
Additional Resources & Further Reading
- Team Bender: final presentation
- Team Bender: documentation
- Team Bender: implementation
- Team Bender on GitHub