Spatial load balancing in non-convex environments using sampling-based motion planners

Beth Boardman, Troy Harden, and Sonia Martínez
Proceedings of the 2016 American Control Conference, Boston, MA, USA, July 2016

Abstract:

This paper proposes an algorithm to approximately solve a spatial-load balancing problem for agents, subject to differential constraints, deployed in non-convex environments. A probabilistic roadmap is used to approximate regions via connected sets of vertices, which describe agents' configurations and optimal paths joining them. At each iteration, agents' positions and assigned graph nodes are updated to minimize the cost function. Two graph-node partitions are considered. In the first one, V, all graph vertices are allocated to one agent or another. The second one, V-lower, is a lower approximation that only allocates some of the graph vertices to the agents and has the advantage of requiring less communication than required for V. Algorithm convergence can be guaranteed for V to a neighborhood of the continuous-space counterpart, and to its solution as sampling dispersion tends to zero. The convergence of the algorithm using V-lower and tradeoffs between V-lower and V are established in simulation for a Euclidean metric case and Dubins' vehicle dynamics.

File: main.pdf

Bib-tex entry:

@InProceedings{BB-TH-SM:16},
author = {B. Boardman and T. Harden and S. Mart{\'\i}nez},
booktitle = {2016 American Control Conference},
title = { Spatial load balancing in non-convex environments using sampling-based motion planners},
month = {July},
year = {2016},
address ={Boston, MA}
pages ={}
}