Stubenschrott, M. (2008). Collision Avoidance in a Multi-Agent System [Master Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-29396
The aim of collision avoidance is to find a path to an object's target without colliding with other static or moving obstacles.<br />Furthermore, the length of this path should be minimized while still ensuring there is no crash with other objects. The demand for such a system is huge, as collision avoidance is essential for most robots but also for applications like autonomous vehicles.<br />This master's thesis goal is to design, to implement and to evaluate a collision avoidance algorithm for a multi-agent system with quickly moving objects. The obvious choice was to reuse an existing robot soccer framework from the IHRT institute of the Vienna University of Technology. While the IHRT has a long and successful tradition in playing robot soccer, the current system is lacking a proper collision avoidance module. Additionally - and even more important - robot soccer serves as a prime example for a multi-agent system because it needs intelligent interaction between robots.<br />The algorithm itself is divided in two parts: First we try to find information about the next collision for each robot and categorize it into one of three possible types (head-on, perpendicular or angular collision). Using this information, the algorithm aims to prevent the anticipated collision by using one of two strategies: The path of an individual robot is modified by either changing its direction or its speed.<br />The system is evaluated with two robots moving on predetermined and random paths. We count the number of collisions and calculate the average speed with and without using the collision avoidance module.<br />Thus we find out whether the proposed algorithm works well and where its drawbacks are.
en
Das Ziel von Kollisionsvermeidung ist es einen Pfad zum Ziel eines Objektes zu finden ohne mit anderen statischen bzw. beweglichen Hindernissen zu kollidieren.<br />Zusätzlich soll dieser Pfad möglichst kurz sein ohne jedoch das Risiko einzugehen, mit anderen Objekten zu kollidieren. Der Bedarf an ein solches System ist hoch, da die meisten Roboter eine Kollisionsvermeidung benötigen, aber auch andere Anwendungen wie selbstfahrende Fahrzeuge profitieren davon.<br />Das Ziel dieser Diplomarbeit ist es, einen Algorithmus zur Kollisionsvermeidung in einem Multiagentensystem zu entwerfen, zu implementieren und zu testen. Die Wahl fiel darauf, ein existierendes Roboterfußball-Framework des IHRT Instituts der Technischen Universität Wien als Basis dafür zu verwenden. Denn obwohl das IHRT eine lange und erfolgreiche Tradition im Roboterfußballspielen hat, fehlt bisher ein ordentliches Kollisionsvermeidungsmodul. Außerdem - und noch viel wichtiger - kann man Roboterfußball als Paradebeispiel für ein Multiagentensystem ansehen da es intelligente Kommunikation zwischen den einzelnen Robotern benötigt.<br />Der Algorithmus wird dazu in zwei Teile gespalten: Als erstes versuchen wir müglichst viele Informationen uber die nächste Kollision zu erhalten und kategorisieren diese in drei unterschiedliche Kollisionstypen (frontal, rechtwinkelig oder schräg). Auf Grund dieser Informationen versucht der Algorithmus die bevorstehende Kollision mit Hilfe von zwei Strategien zu vermeiden: Wir verändern den Pfad von einzelnen Robotern indem wir entweder deren Richtung oder deren Geschwindigkeit ändern.<br />Das System wird evaluiert, indem man zwei Roboter auf vordefinierte bzw. zufällige Pfade schickt. Nun zählen wir die Anzahl der Kollision und berechnen die Durchschnittsgeschwindigkeit sowohl mit ein- als auch ausgeschalteter Kollisionsvermeidung. Dadurch können wir herausfinden, ob der vorgeschlagene Algorithmus gut funktioniert und wo es noch Probleme gibt.<br />