Project Overview

Structural Properties of Solvable Graphs for Multiple Robot Motion Planning

Faculty Sponsor

Hiva Samadian (


Computer Science


Solvable or Reachable Graphs are types of graphs that any arrangement of a specified number of mobile 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. In this project, the properties of Solvable Graphs are investigated, and a new concept in multi-robot 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, the problem of deciding whether a graph is Solvable for any initial and final configurations of m robots is answered, without explicitly solving it. The results of this research can be used in designing transportation networks (e.g. railways, traffic roads, AGV routes, robotic workspaces, etc.) for multiple moving agents such as trains, vehicles, and robots. The problem has been modeled and the concepts have been defined and some properties have been proved in this ongoing project.
The objective, for this summer, is to complete the proof of two theorems. This may involve implementing the problem and doing experiments to test the conjectures to be proven. During this project, you will (1) get acquainted with the literature and subject of the research (2) use your programming skill in a research problem (3) apply your knowledge that you have learned in courses such as logic or discrete structure on a real-world problem (4) read, understand, and write critique on a research paper and learn about some other general components of doing research.

Student Qualifications

(1) Good background and high interest in mathematical proofs, OR (2) programming skill in Python, Java or Matlab are required. I encourage you to apply if you have only one of the two requirements.

Number of Student Researchers

1 student

Project Length

9 weeks

Applications open on 01/03/2020 and close on 02/05/2020

<< Back to List

If you have questions, please contact Karyn Belanger (