SoCG 2021

The 37th International Symposium on Computational Geometry

Challenge

Accepted CG Challenge 2021 Contributions for the Proceedings

The Third Computational Geometry Challenge takes place as part of CG Week (virtual-only), June 7-11, 2021.

As in the last year, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. 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. The specific problem chosen for the 2021 Challenge is the following:

Coordinated Motion Planning

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:

  • • minimize the makespan, i.e., the time until all robots have reached their destinations
  • • minimize the overall energy, i.e., the total distance traveled by all robots

See the website for illustrations and animations.

Challenge Team

  • • Sándor Fekete, TU Braunschweig, Germany
  • • Phillip Keldenich, TU Braunschweig, Germany
  • • Dominik Krupke, TU Braunschweig, Germany
  • • Joseph S. B. Mitchell, Stony Brook University, USA

Advisory Board

  • • Bill Cook, University of Waterloo, Canada
  • • Andreas Fabri, Geometry Factory, France
  • • Michael Kerber, Graz University of Technology, Austria
  • • Philipp Kindermann, University of Wuerzburg, Germany
  • • Kevin Verbeek, Eindhoven University of Technology, Netherlands

Important Dates

  • • 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.
    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.