Distributed Planning for Multi-Robot Path Planning via Workspace Decompsition

We propose a distributed path planning algorithm for self-reconfigurable multi-robot systems in the large and cluttered environment. The algorithm includes three aspects, namely parallel processing based on workspace decomposition and gragh structure, information exchanges for distance between robots, and a distributed multi-constraint optimization method. In the parallel processing, the global workspace is split into a set of partially overlapped subspace and then parallelly runs the decomposition on each subspace to create graghs G(V,E), whose vertices V and edges E are the decomposited convex subset in the free obstacle workspace, in distributed robots'computers. In the information exchange, we chose relay nodes in the overlapped space. Only distances next to the relay nodes are shared in the network due to the limited inter-processor communiction bandwith. In the distributed optimization, a constrained path optimization problem is established by searching the global gragh and solved by Alternating Direction Method of Multi-pliers(ADMM). Finally, we run the parallel and distributed algorithm on simulation environment in defferent number of obstacles and it gets better optimization time on multiple processor.