Optimal and Distributed Motion Planning for Multiple Robot Systems

Within the last decades, autonomous multirobot systems have been received an increasing interest due to their enormous application potential. Motion planning algorithm is a key enabler to a greater autonomy. This thesis focuses particularly on the motion planning algorithm for the autonomous multirobot systems. The contributions of the thesis are threefold.

Firstly, a novel high-order near time-optimal trajectory generation algorithm is presented for twodimensional robots. The proposed trajectory generation algorithm is numerical efficient and can be embedded for any point-to-point movement in factory and logistic automation. Moreover, the generated trajectories are not only near time-optimal but also bounded by high-order time derivatives. Time discretization effects as well as nonlinear constraints due to obstacles avoidance are incorporated into the trajectory generation algorithm. These properties of the trajectory generation algorithm are essential to high-performance industrial motion control systems.

Subsequently, a novel centralized motion coordination solution is introduced, which comprises a collision avoidance algorithm and a conflict resolution algorithm. The system safety can be guaranteed by employing the collision avoidance algorithm, while deadlocks can be prevented by deploying the conflict resolution algorithm. Particularly, the theoretical safety of the collision avoidance algorithm can be proved. Moreover, the centralized coordination solution is highly modular, since it can be applied as a post process to the aforementioned trajectory generation algorithm. Consequently, all important properties such as bounded high-order derivatives or time discretization consideration can be preserved.

Finally, an asynchronous distributed collision avoidance algorithm is developed for multiple passive robots translating on a grid of static rectangular intelligent agents. The distributed algorithm is deployed directly into the static intelligent agents. Furthermore, the distributed algorithm is not only able to guarantee collision-free motions but also robust with respect to stochastic arbitrarily large communication time delays. Therefore, the distributed algorithm is a key to scale existing prevalent industrial systems to another dimension.

In den letzten Jahrzehnten haben autonome Multirobotersysteme aufgrund ihres enormen Anwendungspotenzials ein zunehmendes Interesse bekommen. Algorithmen zur Bewegungsplanung sind Schlüsseltechnologien zu einer größeren Autonomie. Diese Dissertation konzentriert sich insbesondere auf die Algorithmen zur Bewegungsplanung für die autonomen Multirobotersysteme. Diese Dissertation hat drei Hauptbeiträge.

Als erster Beitrag wird ein neuartiger Algorithmus zur Erzeugung zeitoptimaler Trajektorien hoher Ordnungen für zweidimensionale Robotersysteme vorgestellt. Der vorgeschlagene Algorithmus ist numerisch effizient und kann für jede Punkt-zu-Punkt-Bewegung in Fabrik und Logistikautomatisierung eingebettet werden. Darüber hinaus sind die generierten Trajektorien nicht nur zeitoptimal sondern auch durch Zeitableitungen hoher Ordnungen begrenzt. Diskretisierungseffekte sowie nichtlineare Nebenbedingungen aufgrund der Hindernisvermeidung sind in dem Algorithmus integriert. Diese hervorragende Eigenschaften des vorgeschlagenen Algorithmus sind wesentlich für leistungsfähige industrielle Bewegungssteuerungssysteme.

Nachfolgend wird eine zentralisierte Bewegungskoordinierungslösung eingeführt, die aus einem Kollisionsvermeidungsalgorithmus und einem Konfliktlösungsalgorithmus besteht. Die Systemsicherheit kann durch den Einsatz des Kollisionsvermeidungsalgorithmus gewährleistet werden, während Deadlocks durch die Verwendung des Konfliktlösungsalgorithmus verhindert werden können. Insbesondere kann die theoretische Sicherheit des Kollisionsvermeidungsalgorithmus nachgewiesen werden. Außerdem ist die zentralisierte Koordinierungslösung hochgradig modular, da sie als ein Postprozess auf den oben erwähnten zeitoptimalen Trajektoriengenerierungsalgorithmus angewendet werden kann. Dabei werden alle wichtigen Eigenschaften wie z.B. die begrenzte Zeitableitungen oder die Berücksichtigung der Zeitdiskretisierung beibehalten.

Letztendlich wird ein asynchroner verteilter Kollisionsvermeidungsalgorithmus für passive Roboter entwickelt, die sich auf einem Gitter von statischen rechteckigen intelligenten Agenten bewegen. Der verteilte Algorithmus wird direkt in den statischen intelligenten Agenten eingesetzt. Darüber hinaus ist der verteilte Algorithmus in der Lage, nicht nur kollisionsfreie Bewegungen zu gewährleisten sondern auch robust gegenüber stochastischen beliebigen großen Kommunikationszeitverzögerungen zu sein. Daher ist der verteilte Algorithmus ein Schlüssel zur Skalierung bestehender verbreiteter industrieller Systeme in eine andere Dimension.