Exact approaches to the multi-agent collective construction problem

Edward Lam, Peter Stuckey, Sven Koenig, T. K. Satish Kumar

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

The multi-agent collective construction problem tasks agents to construct any given three-dimensional structure on a grid by repositioning
blocks. Agents are required to also use the blocks to build ramps in order to access the higher levels necessary to construct the building, and then remove the ramps upon completion of the building. This paper presents a mixed integer linear programming model and a constraint programming model of the problem, either of which can exactly optimize the problem, as previous efforts have only considered heuristic approaches. The two models are evaluated on several small instances with a large number of agents. The plans clearly show the swarm behavior of the agents. The mixed integer linear programming model is able to find optimal solutions faster than the constraint programming model and even some existing incomplete methods due to its highly-exploitable network flow substructures.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
EditorsHelmut Simonis
Place of PublicationCham Switzerland
PublisherSpringer
Pages743–758
Number of pages16
ISBN (Electronic)9783030584757
ISBN (Print)9783030584740
DOIs
Publication statusPublished - 2020
EventInternational Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium
Duration: 7 Sep 202011 Sep 2020
Conference number: 26th
https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings)
https://cp2020.a4cp.org (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12241
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2020
Abbreviated titleCP2020
CountryBelgium
CityLouvain-la-Neuve
Period7/09/2011/09/20
Internet address

Keywords

  • Classical planning
  • Multi-agent planning
  • Multi-agent path finding
  • Blocksworld
  • Swarm robotics

Cite this

Lam, E., Stuckey, P., Koenig, S., & Satish Kumar, T. K. (2020). Exact approaches to the multi-agent collective construction problem. In H. Simonis (Ed.), Principles and Practice of Constraint Programming: 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings (pp. 743–758). (Lecture Notes in Computer Science; Vol. 12241). Springer. https://doi.org/10.1007/978-3-030-58475-7_43