Assembly sequence planning for constructing planar structures with rectangular modules

This paper addresses assembly sequence planning for constructing planar structures of the common brick wall pattern collectively with mobile modular robots that have the same rectangular footprint. Here we present a new algorithm for target structures with internal holes that our previous algorithm was not able to address. Our new algorithm constructs a feasible assembly sequence where robots do not have to pass through narrow corridors while approaching their target positions. The algorithm is provably correct and complete and runs in time that is linear in the size of a target structure, that is, the number of its parts. We also present software implementing our algorithms and a set of numerical experiments using the software. Finally, we extend our algorithms to address other symmetric patterns formed by a collection of congruent rectangles on the plane.

Authors

• Jungwon Seo
• Mark Yim
• Vijay Kumar 0001

Keywords

• Robots
• Planning
• Sequential analysis
• Face
• Hardware
• Software algorithms
• Software
• Sequence Assembly
• Assembly Sequence Planning
• Target Location
• Correction Algorithm
• Mobile Robot
• Previous Algorithms
• Brick Wall
• Narrow Corridor
• Common Wall
• Frontier
• Undirected
• Yield Potential
• Optimal Sequence
• Linear Order
• Range Of Structures
• Partial Order
• Robot Motion
• Correct Assembly
• Minimum Height
• Vertex Degree
• Physical Robot
• Breadth-first Search
• Incident Edges
• Assembly Of Parts