טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentHochmann Uriel
SubjectNavigation of Locally Interacting Autonomous Agents
on 2D Y-Node Graphs
DepartmentDepartment of Mechanical Engineering
Supervisor Professor Elon Rimon
Full Thesis textFull thesis text - English Version


Abstract

The configuration space associated with multiple robots is mostly unexplored; most of the research in the field of multiple robots was made from the viewpoint of a “master” controlling the movement of agents across the space. However, using multiple autonomous agents will allow task separation to several smaller tasks and involve cheaper and simpler individual robots that compose together a complete solution. Some of the tasks that invite the use of multiple agents are fields such as personal transportation and warehouse management. Current off the shelf solutions require a central computer to control simultaneously the paths of all the agents moving on a shared physical network on graph, this limits the solution to a finite number of agents due to limitations on the performance of the central computer. In the thesis, a topological model representing the configuration space of three agents around a node is presented. Additional models are presented as well to form a deeper understanding of the three agent configuration space. Solution algorithms for conflicts of k agents around a node are presented. These algorithms allow either an optimal minimum number of steps or simple computation of the steps required to solve the conflict. The subject of agent inclusion in mid-conflict is treated. Together all the aforementioned solution compose an algorithm for the entire physical network. The thesis additionally presents experiments held to demonstrate the solutions and prove their viability.