TY - JOUR
ID - 7
TI - Designing Solvable Graphs for Multiple Moving Agents
JO - Journal of Optimization in Industrial Engineering
JA - JOIE
LA - en
SN - 2251-9904
AU - Masehian, Ellips
AU - Daneshzand, Farzaneh
AD - Industrial Engineering Dept., Tarbiat Modares University, Tehran, 14115-317, Iran
Y1 - 2010
PY - 2010
VL - Volume 1
IS - Issue 2
SP - 41
EP - 54
KW - Deadlocks
KW - Intelligent Moving Agents
KW - Motion Planning
KW - Solvable Graphs
DO -
N2 - 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.
UR - http://www.qjie.ir/article_7.html
L1 - http://www.qjie.ir/article_7_0f536d806b7110e5a38db18daf6a50e9.pdf
ER -