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

Due to the nature of the competition, long term planning is ill-advised. This is mainly due to the following reasons:

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.

samples samples2

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

As expected, the visibility graph approach is the most accurate, with the best results in terms of path length. However it is of quadratic complexity and employs expensive geometric calculations.

Following the edges of the outline generates longer movements by an order of 10%s, but we can find this sort of path very quickly. However in some scenarios of polygons with holes this approach may yield poor results (or no solution at all).

The triangulation method proved to be a nice compromise between the two approaches, and could effectively deal with all viable scenarios.

tri

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

By Shay Barak, Noam Inbar, Yasmin Slonimsky and Idan Sayag

Tel Aviv University, September 2012

Sections

Personal tools