We study robot construction problems where multiple autonomous robots rearrange stacks of prefabricated blocks to build stable structures. These problems are challenging due to ramifications of actions, true concurrency, and requirements of supportedness of blocks by other blocks and stability of the structure at all times. We propose a formal hybrid planning framework to solve a wide range of robot construction problems, based on Answer Set Programming. This framework not only decides for a stable final configuration of the structure, but also computes the order of manipulation tasks for multiple autonomous robots to build the structure from an initial configuration, while simultaneously ensuring the stability, supportedness and other desired properties of the partial construction at each step of the plan. We prove the soundness and completeness of our formal method with respect to these properties. We introduce a set of challenging robot construction benchmark instances, including bridge building and stack overhanging scenarios, discuss the usefulness of our framework over these instances, and demonstrate the applicability of our method using a bimanual Baxter robot.
Later, Fahlman @cite_29 has introduced a set of robot construction problems where the goal is for a robot to build specified structures out of simple blocks of different shapes and sizes. These problems allow incorporation of subassemblies into the final design, and the use of extra blocks as temporary supports or counterweights during construction; they also consider collisions of blocks and instability of the structures, but not motion planning. Since Fahlman's main interest was in maximizing common sense (rather than soundness, completeness or optimality), he implemented a planning system guided with heuristics to solve some of these problems. These problems have not been investigated with a formal approach since then.
@cite_29
2147072697
This paper describes BUILD, a computer program which generates plans for building specified structures out of simple objects such as toy blocks. A powerful heuristic control structure enables BUILD to use a number of sophisticated construction techniques in its plans. Among these are the incorporation of pre-existing structure into the final design, pre-assembly of movable sub-structures on the table, and the use of extra blocks as temporary supports and counterweights in the course of the construction. BUILD does its planning in a modeled 3-space in which blocks of various shapes and sizes can be represented in any orientation and location. The modeling system can maintain several world models at once, and contains modules for displaying states, testing them for inter-object contact and collision, and for checking the stability of complex structures involving frictional forces. Suggestions are included for the extension of BUILD-like systems to other domains. Also discussed are the merits of BUILD's implementation language, conniver, for this type of problem solving.