We are happy to announce the Third Computational Geometry Challenge,
as part of CG Week in Buffalo, USA, June 7-11, 2021.
As in the last 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.
(See the website
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2021/#problem-description
for illustrations and animations.)
Given a set of n axis-aligned unit-square „robots" in the plane,
a set S = {s_1,…,s_n} of n non-overlapping „start" pixels of the integer grid,
and a set T = {t_1,…,t_n} of n non-overlapping „target" pixels of the integer grid.
During each unit of time, robots can move (at unit speed) in direction north/south/east/west
to adjacent pixels, provided they stay disjoint from all other robots.
(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 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 the two robots remain in contact,
during the movement, but never overlap.)
In addition, there may be a set of obstacles, consisting of a number of blocked pixels
that cannot be used by robots.
The task is to compute a feasible set of trajectories for all robots i that moves each of
them from s_i to t_i.
We will run the challenge in two separate categories, with the two following objective functions:
(A) minimize the makespan, i.e., the time until all robots have reached their destinations;
(B) minimize the overall energy, i.e., the total distance traveled by all robots.
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!
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 15, 2020: Release of instances, detailed rules, start of contest
- February 15, 2021: 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
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
[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.
https://www.ibr.cs.tu-bs.de/users/fekete/Videos/CoordinatedMotionPlanning.mp4
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
