Optimal task planning and predictive online motion control for a multi-manipulator system

Produktbeschreibung

Diese Arbeit befasst sich mit einem Ansatz zur Aufgaben- und Bewegungsplanung (TAMP), der eine autonome Kooperation zwischen mehreren Manipulatoren in Echtzeit ermöglicht. Die simultane und echtzeitfähige Ausführung von Aufgaben durch eine Gruppe von Manipulatoren stellt nach wie vor eine große Herausforderung dar, da eine komplexe Koordination zwischen den Robotern erforderlich ist, um Kollisionen und Deadlocks zu verhindern. Der vorgeschlagene optimierungsbasierte TAMP Ansatz ist hierarchisch aufgebaut und basiert auf einem gemischt-ganzzahligen linearen Optimierungsproblem sowie der verteilten modellprädiktiven Regelung. Umfangreiche simulationsbasierte und experimentelle Studien, einschließlich mehrerer Benchmark-Analysen, werden durchgeführt, um die Vorteile des vorgeschlagenen TAMP-Ansatzes zu demonstrieren. Eine zusätzliche Skalierbarkeitsanalyse zeigt die Grenzen des Ansatzes auf.

Contents
Acknowledgments III
List of Abbreviations VIII
Kurzfassung IX
Abstract X
1 Introduction 1
2 State of the art 5
2.1 Path planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Roadmap techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 Cell decomposition methods . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Artificial potential field methods . . . . . . . . . . . . . . . . . . . 9
2.1.4 Sampling-based planners . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Trajectory planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Optimization-based methods . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Grid-based search methods . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Alternative approaches . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Model predictive control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Mathematical formulation . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Control schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 Collision avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4 Review for robotic arm systems . . . . . . . . . . . . . . . . . . . . 21
2.4 Multi-robot systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.2 Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.3 Multi-robot task allocation . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Online motion control for a single manipulator 33
3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Object detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Optimization-based scheduling model . . . . . . . . . . . . . . . . . 38
3.2.3 Online trajectory generation using MPC . . . . . . . . . . . . . . . 40
3.2.4 Compensation of computation times . . . . . . . . . . . . . . . . . 44
3.3 Experimental study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.1 Performance metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 Sorting task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.3 Narrow passage problem . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.4 Dynamically changing environment . . . . . . . . . . . . . . . . . . 53
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 Online motion control for a multi-manipulator system 57
4.1 Requirements and assumptions . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2 Task and motion planning architecture . . . . . . . . . . . . . . . . . . . . 60
4.3 Multi-robot scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.2 Heuristic scheduling model . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.3 Optimization-based scheduling model . . . . . . . . . . . . . . . . . 65
4.3.4 Proximity and concurrency constraints . . . . . . . . . . . . . . . . 68
4.3.5 Constraints enforcing specific order of objects . . . . . . . . . . . . 69
4.4 Online trajectory generation using DMPC . . . . . . . . . . . . . . . . . . 70
4.4.1 Inter-robot collision avoidance . . . . . . . . . . . . . . . . . . . . . 73
4.4.2 Comparison of centralized and distributed optimization . . . . . . . 76
4.5 Reactive deadlock resolution approach . . . . . . . . . . . . . . . . . . . . 77
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5 Simulation-based study 83
5.1 General settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Environmental modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3 Benchmark analysis of scheduling approaches . . . . . . . . . . . . . . . . 87
5.3.1 Heuristic task assignment . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.2 Optimization-based task assignment . . . . . . . . . . . . . . . . . 90
5.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Benchmark analysis of trajectory planners . . . . . . . . . . . . . . . . . . 94
5.4.1 Performance metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.2 Heuristic task assignment . . . . . . . . . . . . . . . . . . . . . . . 95
5.4.3 Optimization-based task assignment . . . . . . . . . . . . . . . . . 97
5.4.4 Scalability analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6 Experimental study 105
6.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2 Object detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 Collision avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.4 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.4.1 Scenario 1: Objects in close proximity . . . . . . . . . . . . . . . . 113
6.4.2 Scenario 2: Objects lying on opposite sides of each robot . . . . . . 115
6.4.3 Scenario 3: Assignment of objects to the same tray . . . . . . . . . 116
6.5 Sorting task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.5.1 Heuristic task assignment . . . . . . . . . . . . . . . . . . . . . . . 119
6.5.2 Optimization-based task assignment . . . . . . . . . . . . . . . . . 120
6.6 Disassembly task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.6.1 Heuristic task assignment . . . . . . . . . . . . . . . . . . . . . . . 125
6.6.2 Optimization-based task assignment . . . . . . . . . . . . . . . . . 128
6.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7 Conclusion and Outlook 131
Appendix 137
A Model identification of an UR3 . . . . . . . . . . . . . . . . . . . . . . . . 137
B Model identification of an UR5e . . . . . . . . . . . . . . . . . . . . . . . . 139

Keywords: Multi-Robotersysteme, online Trajektorienplanung, modellprädiktive Regelung, Kollisionsvermeidung, Manipulator, Deadlock, optimale Aufgabenplanung, verteilte Optimierung, Mult-robot systems, task and motion planning, model predictive control, online motion control, optimal task allocation, distributed optimization, deadlock, cooperative manipulation, manipulator systems