Multi-Robot Assembly Sequencing via Discrete Optimization

Preston Culbertson, Saptarshi Bandyopadhyay, Mac Schwager

2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2019

Abstract

Multi-robot assembly has the potential to greatly reduce the cost and risk associated with the fabrication of large structures. Using teams of robots to perform assembly offers numerous advantages such as parallelism, robustness to single-agent failures, and flexibility in scheduling and task assignment. However, while previous work on multi-robot assembly focuses on generating feasible assembly plans and decentralized control strategies, we instead study the problem of planning optimal assembly sequences.To this end, we pose the problem of multi-robot assembly as a discrete optimization, specifically an integer linear program (ILP) or quadratic program (IQP), which aims to minimize the time to complete the assembly, or to minimize the distance traveled. We develop a model of multi-robot assembly that captures both geometric constraints and actuation constraints inherent to the problem. While the ILP and IQP can be solved exactly using commercial optimization software in a substantial amount of time, we also propose heuristic strategies which can be quickly computed, and can scale to structures of reasonable size. We also verify our methods empirically by comparing their performance on a variety of test structures.

BibTeX

@inproceedings{culbertson_multi-robot_2019,
  title = {Multi-{Robot} {Assembly} {Sequencing} via {Discrete} {Optimization}},
  abstract = {Multi-robot assembly has the potential to greatly reduce the cost and risk associated with the fabrication of large structures. Using teams of robots to perform assembly offers numerous advantages such as parallelism, robustness to single-agent failures, and flexibility in scheduling and task assignment. However, while previous work on multi-robot assembly focuses on generating feasible assembly plans and decentralized control strategies, we instead study the problem of planning optimal assembly sequences.To this end, we pose the problem of multi-robot assembly as a discrete optimization, specifically an integer linear program (ILP) or quadratic program (IQP), which aims to minimize the time to complete the assembly, or to minimize the distance traveled. We develop a model of multi-robot assembly that captures both geometric constraints and actuation constraints inherent to the problem. While the ILP and IQP can be solved exactly using commercial optimization software in a substantial amount of time, we also propose heuristic strategies which can be quickly computed, and can scale to structures of reasonable size. We also verify our methods empirically by comparing their performance on a variety of test structures.},
  booktitle = {2019 {IEEE}/{RSJ} {International} {Conference} on {Intelligent} {Robots} and {Systems} ({IROS})},
  author = {Culbertson, Preston and Bandyopadhyay, Saptarshi and Schwager, Mac},
  month = nov,
  year = {2019},
  keywords = {multi-robot, optimization, planning},
  pages = {6502--6509},
  month_numeric = {11}
}