CG:SHOP 2021

Coordinated Motion Planning

We are happy to announce the Third Computational Geometry Challenge, as part of CG Week in Buffalo, USA, June 7-11, 2021.

As in previous years, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. The specific problem chosen for the 2021 Challenge is Coordinated Motion Planning, as follows.

Description

Given a set of $n$ axis-aligned unit-square robots in the plane, a set $S = \{s_1,…,s_n\}$ of $n$ distinct start pixels (unit squares) of the integer grid, and a set $T = \{t_1,…,t_n\}$ of $n$ distinct target pixels of the integer grid. During each unit of time, each robot can move (at unit speed) in a direction (north, south, east or west) to an adjacent pixel, provided the robot remains disjoint from all other robots during the motions.

This condition has to be satisfied at all times, not just when robots are at pixel positions. For example, if there are robots at each of the two adjacent pixels $(x,y)$ and $(x+1,y)$, then the robot at $(x,y)$ can move east into position $(x+1,y)$ only if the robot at $(x+1,y)$ moves east at the same time, so that the two robots remain in contact, during the movement, but never overlap.

In addition, for some instances, there may be given a set of obstacles, consisting of a number of stationary, blocked pixels that cannot be used by robots at any time.

The task is to compute a set of feasible trajectories for all $n$ robots, with the trajectory for robot $i$ moving it from $s_i$ to $t_i$.

Objectives

We will run the challenge in two separate categories, with the two following objective functions:

1. minimize the makespan, i.e., the time until all robots have reached their destinations;
2. minimize the total distance traveled by all robots.

Motivation

The problem is motivated by questions of multi-object motion planning, such as robot navigation and air traffic control. Even the version considered in the Challenge is known to be NP-complete; see [1], and [2] for an illustrating video.

Details of the competition (such as benchmark instances, data formats, and rules for submission and evaluation) will be announced in coming weeks; see the timeline below.

The contributors with the most outstanding solutions will be recognized at CG Week and invited to present their results, both at the event and in the proceedings.

We are looking forward to your contributions and welcome questions and comments!

Notes

• As the square-shaped robots completely fill their pixels, they do not allow rotation moves like in the video [2] referenced below; that takes better separation, e.g., because robots are moved apart. (See 7:45-8:35 in the video for some context.)
• In the "Flip" example, robots are not confined to the 4x4 grid that they occupy in the beginning, so they can be pulled further apart.

References

[1] E.D. Demaine, S.P. Fekete, P. Keldenich, H. Meijer, C. Scheffer.
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch.
SIAM Journal on Computing, Vol. 48, No. 6, pp. 1727-1762, 2019.
arXiv version

[2] A.T. Becker, S.P. Fekete, P. Keldenich, M. Konitzny, L. Lin, C. Scheffer.
Coordinated Motion Planning: The Video.
In: Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), pp. 74:1-74:6.
Available online.

Challenge Team

Sándor Fekete, Phillip Keldenich, Dominik Krupke, Joe Mitchell

Advisory Board

Bill Cook, Andreas Fabri, Michael Kerber, Philipp Kindermann, Kevin Verbeek

Timeline

November 20, 2020 (0:00 a.m., UTC)

Release of instances, detailed rules, start of contest

February 15, 2021 (11:59 p.m., AoE)

Contest closes, winners are invited to submit an abstract for the SoCG proceedings by early March

March 1, 2021

First version of proceedings abstracts due for screening and editing

March 15, 2021

Feedback on abstracts, notification of acceptance, details of final revision

March 31, 2021

Final versions due