A Distributed Convergent Solution to the Ambulance Positioning Problem on a Streetmap Graph

In this paper, we combine ideas from multi-agent cooperative coverage control, with problem formulations from the resource allocation field, to create a distributed convergent approach to the ambulance positioning problem. Inspired by coverage control we use the graph version of so-called Voronoi regions, making the solution distributed and reactive, thereby freeing computational resources. The solution is distributed in the sense that each vehicle only needs to know the positions of its neighbors, and the computations of each vehicle only depend on the size of its Voronoi region/set. This implies that considering a problem of twice the size, using twice the number of vehicles will leave the computational load per vehicle unchanged. The freed resources are used to capture the allocation problem in more detail: maximizing an estimate of the victim survival probability instead of more coarse measures of ambulance availability. Using real city street map data from OpenStreetMap (OSM), we provide simulation results illustrating the applicability of our approach. Finally, we prove that the proposed distributed algorithm is convergent in the sense that it finds a local optimum in finite time.