Multi-Robot Path Planning on Graphs Solution by A* algorithm
Updated 17 Jul 2018

We study the problem of optimal multi-robot path planning on graphs (MPP) over the makespan (last arrival time) criteria. We implemented A* search algorithm to find solution. In an MPP instance, the robots are uniquely labeled (i.e., distinguishable) and are confined to an nxn squared connected graph. The robots may move from a vertex to an adjacent one in one time step in the absence of collision, which may occur when two robots simultaneously move to the same vertex or along the same edge in different directions. A distinguishing feature of our MPP formulation is that we allow robots on fully occupied cycles to rotate synchronously.

To solve above problem, we implemented A* algorithm to find optimum route from given initial 3x3 robot positions and desired 3x3 robot positions. First algorithm starts to construct graph whose connections shows us possible movement. Then we extented it as time based graph. According to time extented graph, all nodes are dublicated for every single of time step. that means if we have 3x3 node for given example, we will have 3x3xts number of node in our time expanded graph for ts time span analysis as we set it ts=7 for our demo. every node in t layer has its own node in (t+1) layer but it has connection to one step far nodes in (t+1) layer as well.

Cite As

muhammet balcilar (2024). Multi-Robot-Path-Planning-on-Graphs (, GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2016b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Verification, Validation, and Test in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versions that use the GitHub default branch cannot be downloaded

Version Published Release Notes

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.