Designing Solvable Graphs for Multiple Moving Agents

Subject Areas : Design of Experiment

Ellips Masehian ¹ , Farzaneh Daneshzand ²

1 - Industrial Engineering Dept., Tarbiat Modares University, Tehran, 14115-317, Iran
2 - Industrial Engineering Dept., Tarbiat Modares University, Tehran, 14115-317, Iran

Received: 2008-11-03 Accepted : 2009-02-12 Published : 2010-02-07

Keywords: Solvable Graphs, Intelligent Moving Agents, Motion Planning, Deadlocks,

Abstract :

Solvable Graphs (also known as Reachable Graphs) are types of graphs that any arrangement of a specified number of agents located on the graph’s vertices can be reached from any initial arrangement through agents’ moves along the graph’s edges, while avoiding deadlocks (interceptions). In this paper, the properties of Solvable Graphs are investigated, and a new concept in multi agent motion planning, called Minimal Solvable Graphs is introduced. Minimal Solvable Graphs are the smallest graphs among Solvable Graphs in terms of the number of vertices. Also, for the first time, the problem of deciding whether a graph is Solvable for m agents is answered, and a new algorithm is presented for making an existing graph solvable and lean for a given number of agents. Finally, through an industrial example, it is demonstrated that how the findings of this paper can be used in designing and reshaping transportation networks (e.g. railways, traffic roads, AGV routs, robotic workspaces, etc.) for multiple moving agents such as trains, vehicles, and robots.