부산대학교 도서관

We present an algorithmic framework for automated construction using multiple identical robots. Our approach is based on the principle of tree-based dynamic programming and a concomitant idea of local search on trees to improve the quality of the generated plans. Inspired by the TERMES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and coordinate with each other in building user-specified structures much larger than themselves. While the robots are roughly of the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. Our algorithm employs an inner loop in which the planning problem is solved by performing dynamic programming on a tree that spans the footprint of the user-specified structure. The outer loop of the algorithm furnishes a good tree for the inner loop. We show how we can search for a good tree in the outer loop using local search methods that yield significant improvements in plan quality. Synchronization rules are then applied to parallelize the execution of the generated plan for multiple identical robots.