Abstract
The multiagent collective construction problem tasks agents to construct any given threedimensional 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 highlyexploitable network flow substructures.
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 highlyexploitable network flow substructures.
Original language  English 

Title of host publication  Principles and Practice of Constraint Programming 
Subtitle of host publication  26th International Conference, CP 2020 LouvainlaNeuve, Belgium, September 7–11, 2020 Proceedings 
Editors  Helmut Simonis 
Place of Publication  Cham Switzerland 
Publisher  Springer 
Pages  743–758 
Number of pages  16 
ISBN (Electronic)  9783030584757 
ISBN (Print)  9783030584740 
DOIs  
Publication status  Published  2020 
Event  International Conference on Principles and Practice of Constraint Programming 2020  LouvainlaNeuve, Belgium Duration: 7 Sep 2020 → 11 Sep 2020 Conference number: 26th https://link.springer.com/book/10.1007/9783030584757 (Proceedings) https://cp2020.a4cp.org (Website) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  12241 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Conference on Principles and Practice of Constraint Programming 2020 

Abbreviated title  CP2020 
Country  Belgium 
City  LouvainlaNeuve 
Period  7/09/20 → 11/09/20 
Internet address 

Keywords
 Classical planning
 Multiagent planning
 Multiagent path finding
 Blocksworld
 Swarm robotics
Cite this
Lam, E., Stuckey, P., Koenig, S., & Satish Kumar, T. K. (2020). Exact approaches to the multiagent collective construction problem. In H. Simonis (Ed.), Principles and Practice of Constraint Programming: 26th International Conference, CP 2020 LouvainlaNeuve, Belgium, September 7–11, 2020 Proceedings (pp. 743–758). (Lecture Notes in Computer Science; Vol. 12241). Springer. https://doi.org/10.1007/9783030584757_43