Limited range spatial load balancing in non-convex environments using sampling-based motion planners

Abstract

This paper analyzes the limited range, spatial load balancing problem for agents deployed in non-convex environments and subject to differential constraints which restricts how the agents can move. First, the (unlimited range) spatial load balancing problem is introduced and the minimization problem with area constraints is defined. Then, to extend the problem for limited ranges, two cost functions and a sub-partition are defined. The problems are then analyzed and the results prove the existence of a partition that satisfies the area constraints. The non-convex environment makes the problem difficult to solve in continuous-space. Therefore, a probabilistic roadmap is used to approximate agents’ cells via a graph. A distributed algorithm is proven to converge to an approximate solution. Finally, the convergence of the algorithm is shown in simulation.

1 Introduction

This paper presents coverage algorithms that multiple agents can use to solve area-constrained, limited range, spatial load balancing problems when deployed in non-convex environments. By accounting for how the agents can move via differential constraints, a multi-robot system can more efficiently divide the load of acquiring information or of servicing tasks in a given environment in a fair way. However, non-convex environments and differential constraints generally make the description of assigned regions challenging. Thus, we aim to design and analyze algorithms based on region approximation via sampling which can reduce the communication or computation of agents effectively. Motivated by making the spatial load balancing algorithm distributed over a graph with limited communication ranges, limited traveling ranges for agents are employed.

The gradient-based descent Lloyd algorithm (1982) is the basis of many multi-agent coverage strategies. A limited sample of work building on this approach includes limited sensor footprints (Laventall and Cortés 2008), heterogeneous agents with different sensing radii (Stergiopoulos and Tzes 2011; Pimenta et al. 2008), non-holonomic agents (Kwok and Martínez 2010b; Enright et al. 2008; Savla et al. 2007), and power constraints (Kwok and Martínez 2010a). The area-constrained problem is studied in Cortés (2010), Patel et al. (2014) and Pavone et al. (2011), where a partition of the environment based on weights, is used. This partition, combined with an appropriately modified objective, is sufficient to force agents’ regions to have the desired area. In Jiang and Zefran (2013), a sink node is used to aggregate information collected by all of the agents. When the communication cost is being minimized, the agents must all communicate with the sink node. These papers assume the agents have unlimited ranges and are deployed in a convex environment. In Mahboubi et al. (2014), the area of a convex region covered by sensors is maximized by minimizing the area uncovered in the agents’ cell. Even though the algorithms have certain distributed properties, they cannot, in general, implemented over a limited-range communication graph.

Closely related to this paper is the research on multi-agent coverage in non-convex environments. A first paper is Caicedo-Nunez and Zefran (2008), which applies a diffeomorphism to transform the non-convex environment into an almost convex one, where only a finite number of points have been subtracted. The coverage problem is then solved in the transformed environment and a solution is obtained via the inverse transformation. The diffeomorphism limits this algorithm to two-dimensional environments. Environments with polygonal obstacles are considered in Zhong and Cassandras (2011) and Breitenmoser et al. (2010). A solution to the multi-agent coverage problem for non-point robots in non-convex environments can be found in Pimenta et al. (2008). The approach to solve the non-convex multi-agent coverage problem taken by Kantaros et al. (2014) is to use visibility-based Voronoi diagrams while maximizing the coverage area. The authors of Kantaros et al. (2014) extend their work in Kantaros et al. (2015) to include heterogeneous sensing. Most of the above papers do not present solutions for agents subject to differential constraints. The papers that do account for differential constraints do not consider obstacles.

The following papers are for coverage in an unknown non-convex environment with agents not subject to differential constraints. A Voronoi partition and potential field are used in Renzaglia and Martinelli (2009) to find a solution to the coverage problem in non-convex environments with unknown obstacles. The authors of Bhattacharya et al. (2013) let the agents learn and build a gridded environment map which is used to determine which grid points belong to each agents’ generalized Voronoi cells. This grid-based approach is limited to low dimensional spaces and differential constraints are difficult to handle in this manner. The paper Bhattacharya et al. (2014) is an extension of Bhattacharya et al. (2013) to Reimannian manifolds with non-convex boundaries.

This paper builds on the preliminary results presented in our previous conference papers Boardman et al. (2016) and Boardman et al. (2017), to present a unified solution to a more general problem, thus addressing the limitations of each paper. The first paper Boardman et al. (2016) introduces the Graph-based Spatial Load Balancing (GSLB) algorithm for approximately solving a non-convex spatial load balancing problem. Under some conditions, the algorithm constructs a lower-approximation, based on a lower bound of the cost function, of sample assigned regions to enable decentralization and to simplify computations. These lower approximations are dropped in this manuscript; instead we consider limited ranges. The second paper (Boardman et al. 2017) develops a distributed algorithm for solving a continuous-space, limited range, spatial load balancing problem in convex environments. In this manuscript, we go beyond both formulations and consider a limited range, non-convex spatial load balancing problem for dynamically constrained agents. We approach this problem by employing locational optimization techniques that are based on generalized Voronoi partitions of the environment. Due to the obstacles and differential constraints, obtaining an exact description of the Voronoi partition can be difficult. Thus, we expand our objective by using an approximation of the agents’ configuration space by means of a probabilistic roadmap star (PRM*).

More precisely, we start from a continuous-space version of the load balancing problem subject to a variable area constraint. With the objective of obtaining distributed algorithms, we introduce limited travel ranges and associated areas and mixed-type performance metric functions. To solve the problem, we introduce “sub-partitions” of the space dependent on a set of additive weights, $\omega$, and agent positions, P. Then, we prove the existence of a set of weights that make the sub-partition satisfy the variable area constraint and thus solve the problem. Based on this result, we provide an update law for agents that allows them to converge to a set of such weights. The agent positions are updated using a gradient law aimed at decreasing the cost function with respect to position. We then define a class of deployment algorithms for solving the problem and show convergence to a solution for the area-type performance metric case.

Building on the continuous-space version, the graph-based algorithm builds a PRM* type graph to describe the cost of an agent subject to differential constraints moving between any two configurations in a known non-convex environment. In this way, the coverage regions are approximated by assigning each agent a subset of nodes from the PRM*. This subset of nodes is further exploited to estimate the coverage regions’ corresponding areas. We provide a characterization of how the limited range algorithm is distributed over a communication graph for radially-unbounded cost functions. We provide an analysis of the algorithm’s convergence as the number of nodes in the optimal probabilistic roadmap tends to infinity. Finally, we present a simulation of the convergence of agents whose costs to move is given by the Euclidean norm squared.

This paper is organized as follows. Section 2 contains notation and details on the Probabilistic Roadmap construction. The continuous-space (limited range) spatial load balancing is in Sect. 3 followed by the graph-based spatial load balancing in Sect. 4. Analysis for the distributed properties of the algorithm is in Sect. 5 and for the convergence of the algorithm is in Sect. 6. Then, Sect. 7 has the simulations of the limited and unlimited range Graph-based Spatial Load Balancing algorithm. Finally, the conclusion and future work can be found in Sect. 8.

2 Preliminaries

To begin with, we introduce some notations. Let $X \subseteq {\mathbb {R}}^d$ be the d-dimensional configuration space of the agents and denote the obstacle space as $X_{obs }$. The free space, $Q = X {\setminus } X_{obs }$, is defined as the set of all collision-free agent configurations. In general, Q is a non-convex configuration space that is assumed to be simply connected by dynamic paths of a mobile robot so that all of Q is reachable by all agents. A sub-partition of a subset of Q, $\mathcal {W} = \{W_1,\dots ,W_n\}$, is a collection of n cells, $W_i \subset Q$, $i \in \{1,\dots , n\}$, whose interiors are disjoint and whose union covers a subset $Q' \subseteq Q$. Denote the boundary of cell $W_i$ as $\partial W_i$. Define the shared boundary between cells i and j as $\triangle _{ij} = W_i \cap W_j$ and denote the unshared boundary of cell i as $\Lambda _i = \partial W_i {\setminus } \big (\cup _{j\ne i} W_j \big )$. Finally, we let $\mathbf {1}_n = (1,\dots ,1)^\top \in {\mathbb {R}}^n$ and $\mathbf {0}_n = (0,\dots ,0)^\top \in {\mathbb {R}}^n$.

2.1 Optimal probabilistic roadmap building

This section briefly describes how to construct an asymptotically optimal probabilistic roadmap (PRM*), denoted by G, for a known environment. Note that the PRM* is limited to dynamics that can be solved with a two point boundary value problem. The graph G allows the agents to approximate the optimal path cost between two configurations in the graph as the sum of the costs of the edges defining the path. The edge cost is the cost an agent incurs while traveling between the nodes that define that edge, e.g. it can be given by length of the edge. The path cost is used in Problem 2 (Sect. 4) as an element of the cost functional being minimized. The graph G is composed of a set of nodes $\mathcal {N}_G$ and a set of edges $\mathcal {E}_G$ constructed in the same was as Karaman and Frazzoli (2011). A node $q \in \mathcal {N}_G$ is a sampled configuration from Q, and each edge, $e \in \mathcal {E}_G$, is an ordered pair, $e = (q_1,q_2)$, which corresponds to an optimal path in Q, satisfies all constraints, and has a cost $J_e(q_1,q_2)$. The cost $J(q_1,q_2)$ is assumed to be additive; given an optimal path from $q_1$ to $q_2$, and a node $q'$ in that path, it holds that, $J(q_1,q_2) = J(q_1,q') + J(q',q_2)$. The additive assumption is used in Sect. 4.1.1. We denote the out neighbors of q in G as $\mathcal {N}^{out }_G(q) = \{ q_j \in \mathcal {N}_G\; | \; (q,q_j) \in \mathcal {E}_G\}$.

Each iteration of the construction of G begins by taking a uniformly sampled random configuration from the free-space, $q_{rand } \in Q$. Next, all graph vertices that are within a ball centered at $q_{rand }$ with radius, $r = \gamma _G (\log (m) /m)^{1/d},$ are determined. Here, $\gamma _G$ is a fixed parameter, m is the number of vertices currently in $\mathcal {N}_G$, and d is the dimension of Q. Let the near vertices of $q_{rand }$ be denoted by $Q_{near }$. If $Q_{near }$ is empty, then the graph vertex that is closest to $q_{rand }$ is added to $Q_{near }$. The least-cost paths, whose cost is $J_e(q_{rand },q_{near })$, from $q_{rand }$ to $q_{near } \in Q_{near }$ are determined; these are outgoing edges of $q_{rand }$. If the cost depends on direction, as is the case with differential constraints, then the least-cost path from $q_{near }$ to $q_{rand }$ is also determined, these are the incoming edges of $q_{rand }$. Each collision-free path, e, is added to $\mathcal {E}_G$ as an edge. The application of spatial load balancing requires that G be strongly connected; a necessary condition is that all $q \in \mathcal {N}_G$ must have both an outgoing and incoming edge, so that if an agent reaches that node it may also leave that node. A sufficient condition is to construct a graph which only allows $(q_1,q_2) \in \mathcal {E}_G$ if and only if $(q_2,q_1) \in \mathcal {E}_G$.

The free-space Q is discretized by G while maintaining an asymptotically optimal roadmap of the environment. Each node $q \in \mathcal {N}_G$ has an associated area, $\beta (q)$, which is calculated as follows. Let $\mathcal {N}_X = \mathcal {N}_G\cup \mathcal {N}_{obs }$, where $\mathcal {N}_{obs }$ is a set of configurations inside $X_{obs }$. Then, determine the Voronoi partition of X using $\mathcal {N}_X$. The $\beta (q)$ for each $q \in \mathcal {N}_G$ is the area of its associated cell in this partition. A description of the external boundary of X is needed and we assume this description is available. In this paper, nodes refer to the vertices in the graph, $q \in \mathcal {N}_G$, and not to the n agents that move in the environment.

3 Continuous-space spatial load balancing

The limited range spatial load balancing problem aims to find optimal locations for n agents, with positions $P = \{ p_1, \dots , p_n\}$, $p_i \in Q$, $i\in \{1,\dots ,n\}$, and region assignments $W_i \subseteq Q$, $i \in \{1,\dots ,n\}$, as described below. Let the optimal cost of robot i to move from configuration $q_1 \in Q$ to $q_2 \in Q$ when subject to the differential constraint, $\dot{p}_i = f(p_i,u_i)$ with control input $u_i$, be $J(q_1,q_2) \ge 0$. A probability density function, $\phi (q)$, defined over Q, $\phi : Q \rightarrow {\mathbb {R}}_{\ge 0}$, describes the likelihood of an event occurring at a configuration in Q.

Let $a_1,\dots ,a_n \in {\mathbb {R}}_{>0}$, be targeted cell areas that distribute the load of covering Q among the group of agents. The $a_i$, $i \in \{1,\dots ,n\}$, are such that $\sum _{i=1}^n a_i = \int _Q \phi (q) dq$, which can be understood as a full load-balancing condition. Ideally, we would like to achieve $\int _{W_i} \phi (q) dq = a_i$, for $i \in \{1,\dots ,n\}$, with the region assignment $\{W_i\}_{i=1}^n$. However, if the $\{W_i\}_{i=1}^n$ strictly satisfy $\cup _{i=1}^n W_i = Q'\subsetneq Q$, full load balancing will not be achievable. Because of this restriction, a new variable area constraint is defined,

$$\begin{aligned} a'_i = \frac{a_i \int _{Q'} \phi (q) dq}{\int _Q \phi (q) dq}, \quad i \in \{1,\dots ,n\}, \end{aligned}$$

which corresponds to load-balancing over the restricted space $Q'$. Of particular interest is the equal area case, $a_i = a_j$ for all i, j, which results in $a_i' = a_j'$, for all $i,j \in \{1,\dots ,n\}$. Note that, when $Q' = Q$, we recover the original, full load-balancing condition. Then, the objective is to find positions, $p_i$, and regions, $W_i \subseteq Q$, for $i \in \{1,\dots ,n\}$, that solve the following minimization problem subject to the area and dynamic constraints,

Problem 1

(Multicenter optimization problem with dynamic and area constraints)

$$\begin{aligned} \min \quad&\mathcal {H}(P,\mathcal {W}) \\ \text {s.t.} \quad&p_i \in Q, \quad \dot{p}_i = f(p_i,u_i), \\&a'_i = \int _{W_i} \phi (q) dq, \quad i \in \{1,\dots ,n\}. \end{aligned}$$

In other words, the n agents want to minimize a cost functional while making sure each agent’s cell, $W_i$ in the partition $\mathcal {W}$, has area $a'_i$. The agents cannot leave Q and must obey the differential constraints that define their movement. In what follows, we describe specific cost functions, $\mathcal {H}$, and types of subpartitions motivated by coverage control objectives.

3.1 Unlimited range agents in convex spaces

The solution to Problem 1 with limited ranges builds on the previous work in Cortés (2010), Patel et al. (2014) and Pavone et al. (2011) where Q is convex and the agents have unlimited range such that $\cup _{i=1}^n W_i = Q$. Then $a_i = a'_i$ and the cost function that is minimized takes the form,

$$\begin{aligned} \mathcal {H}^{centroid }(P,\mathcal {W})&= \sum _{i=1}^{n} \int _{W_i} J(p_i,q) \phi (q) dq. \end{aligned}$$

The cost function $\mathcal {H}^{centroid }(P,\mathcal {W})$ quantifies the network performance and is called centroid because the agent positions that minimize it are the centroids of the cells. This is the problem solved in Cortés (2010).

For trivial first order dynamics, the results in Cortés (2010) state that, given a set of positions, P, there exists a weight assignment, $\omega$, that makes a generalized weighted Voronoi partition, $\mathcal {V}^{weighted }(P,\omega ;J)$, feasible and that this partition is the best among all the partitions $\mathcal {W}$ that satisfy the area constraint. Here, $\mathcal {V}^{weighted }(P,\omega ;J) = \{ V^{weighted }_i(\omega )\}_{i=1}^n$ is such that, for all $i \in \{1,\dots ,n\}$,

$$\begin{aligned} V^{weighted }_i (\omega ) = \{ q \in Q \; | \; J(p_i,q) - \omega _i \le J(p_j,q) - \omega _j, \; \forall \; i \ne j \}. \end{aligned}$$

The feasible set of weights is $U = \{\omega \in {\mathbb {R}}^n \; | \; |\omega _i - \omega _j| \le J(p_i,p_j) \;\; i,j\in \{1,\dots ,n\} \}$. If $\omega \not \in U$, then at least one cell is empty. In convex environments, given a partition, the best agent positions are the centroids of their cells. For certain metrics, such as Euclidean metrics, these centroids are given by a closed-form formula. However, in non-convex environments multiple agent positions may minimize the cost function. These positions are referred to as a generalized centroid.

3.2 Limited ranges

When the agents have a limited travel range, referred to as limited range, a sub-partition, $\cup _{i=1}^n W_i \subset Q$, is found and $a_i \ge a'_i$. Here, limited travel range refers to the maximum distance an agent can travel from its final coverage configuration position. Since the area of the sub-partition changes as a function of agent position, the cost function being minimized is modified to account for the current area covered by the agents. This leads to a cost function that either maximizes the area covered by the regions,

$$\begin{aligned} \mathcal {H}^{area }(P,\mathcal {W})&= - \sum _{i=1}^{n} \int _{W_i} \phi (q) dq, \end{aligned}$$

or combines $\mathcal {H}^{centroid }(P,\mathcal {W})$ and $\mathcal {H}^{area }(P,\mathcal {W})$ in the convenient form of,

$$\begin{aligned} \mathcal {H}^{mixed }(P,\mathcal {W})&= \sum _{i=1}^{n} \bigg ( \int _{W_i} J(p_i,q) \phi (q) dq - k_i \int _{W_i} \phi (q) dq \bigg ), \end{aligned}$$

where $k_i \in {\mathbb {R}}_{>0}$, are constants, see Sect. 3.3.2 for a particular choice.

3.2.1 Limited range sub-partition

Define the limited ranges of the agents as the reachable sets, $\mathcal {D} = \{D_1,\dots ,D_n\}$, such that, for all $i \in \{1,\dots ,n\}$,

$$\begin{aligned} D_i = \{q \in Q \; | \; J(p_i,q) - \omega _i + \frac{1}{n} \sum _{k=1}^n \omega _k \le c \}, \end{aligned}$$

(1)

where $c \in {\mathbb {R}}$ is the travel range of the agents and is a constant. When $\omega _i = \frac{1}{n} \sum _{k=1}^n \omega _k$, then $J(p_i,q) \le c$ making c the upper bound, or limited range, on the cost $J(p_i,q)$. When $\omega _i \ne \frac{1}{n} \sum _{k=1}^n \omega _k$, those terms act as a perturbation on the limited range c. These perturbations are why the effective limited range for each agent can be different. There are certain properties of $\mathcal {V}^{weighted }$ from Cortés (2010) that the limited range sub-partition should maintain in order to obtain analogous results. One such property is that the cells, $V^{weighted }_{i}$, are invariant under translation of $\omega$, $V^{weighted }_{i} (P,\omega ;J) = V^{weighted }_{i} (P,\omega +t \cdot \mathbf {1}_n;J)$. This property leads to the area of $V^{weighted }_{i}$ also being invariant under translations of $\omega$. Including the mean of $\omega$ term allows the set $D_i$ to be invariant under translation in $\omega$. The limited range sub-partition is defined as $\mathcal {V}^{LR }(P,\omega ,c) = \{V^{LR }_{i}\}_{i=1}^n$, such that, for all $i \in \{1,\dots ,n\}$, $V^{LR }_{i} = V^{weighted }_{i} \cap D_i$. An example of a limited range sub-partition can be found in Fig. 1. The shared boundaries are from $V^{weighted }_{i}$ while the unshared arcs are from $D_i$. Note that one of the agents has no shared boundaries, so its cell $V^{LR }_{i} = D_i$. In this example, the $D_i$ boundaries are circular arcs because the cost is the Euclidean norm squared, $J(p_i,q) = \Vert p_i-q\Vert ^2$.

Fig. 1

An example of a limited range sub-partition for four agents, each with a different $\omega _i$

The limited range sub-partition defines a graph which is used to describe the algorithm and its properties. This graph, $\mathcal {G}_{LR }(P,\omega )=(\mathcal {N},\mathcal {E})$, has vertices, $v_i \in \mathcal {N}$, that correspond to the n agents. In this graph, $e = (v_i,v_j) \in \mathcal {E}$, between agents i and j, if and only if $V^{LR }_{i} \cap V^{LR }_{j} \ne \emptyset$. If agents i and j share an edge in $\mathcal {G}_{LR }(P,\omega )$, $(v_i,v_j) \in \mathcal {E}$, then agents i and j are neighbors. Let $\mathcal {N}_i$ denote the set of neighbors for agent i. When $Q' \ne Q$, $\mathcal {G}_{LR }(P,\omega )$ may not be connected. The edges of $\mathcal {G}_{LR }(P,\omega )$ change as the agent positions and weights are updated. Because $D_i$, and hence $V^{LR }_{i}$, is dependent upon all agent weights, $\mathcal {G}_{LR }(P,\omega )$ is not necessarily representative of the agents’ communication graph. The remainder of the paper will abbreviate $\mathcal {G}_{LR }(P,\omega )$ as $\mathcal {G}_{LR }$. This graph is analyzed further in Sect. 5.2.

Let $\eta$ be the number of connected components in $\mathcal {G}_{LR }$ and $\mathcal {G}_l$ be a single connected component of $\mathcal {G}_{LR }$ such that $\mathcal {G}_{LR }= \cup _{l=1}^\eta \mathcal {G}_l$ and $\mathcal {G}_l \cap \mathcal {G}_{l'} = \emptyset$ for all $l,\, l' \in \{1,\dots ,\eta \}$ and $l \ne l'$. Denote the number of vertices in $\mathcal {G}_l$ as $n_l$. Define the vector $\mathbf {v}_l \in {\mathbb {R}}^n$ such that the $i^\text {th}$ entry of $\mathbf {v}_l$ is equal to one if agent i is in $\mathcal {G}_l$ and is zero otherwise. Note that $\{ \mathbf {v}_l \}$ for $l \in \{1, \dots , \eta \}$ form an orthogonal basis.

3.2.2 Existence and choice of weights

This section proves the existence of weights that allow $\mathcal {V}^{LR }$ to satisfy the variable area constraint. Recall, $\mathcal {V}^{LR }$ is invariant under translations in the weights and define the weights-to-area map as,

$$\begin{aligned} \mathcal {M}(P,\omega ) = \bigg ( \int _{V^{LR }_{1}(\omega )} \phi (q) dq, \dots , \int _{V^{LR }_{n}(\omega )} \phi (q) dq\bigg ). \end{aligned}$$

For conciseness, in the following $V^{LR }_{i} = V^{LR }_{i}(\omega )$.

Lemma 1

The weights-to-area map, $\mathcal {M}$, is the gradient, $\nabla F = - \mathcal {M}$, where $F:{\mathbb {R}}^n \rightarrow {\mathbb {R}}$,

$$\begin{aligned} F(\omega ) = \frac{-n}{1-n} \sum _{j=1}^n \int _{V^{LR }_{j}} (&J(p_j,q)-\omega _j + \frac{1}{n} \sum _{k=1}^n \omega _k - c)\phi (q)dq. \end{aligned}$$

The proof of Lemma 1, and all other proofs, can be found in the “Appendix”.

The following equations show how to update an initial weight assignment, $\omega ^0$, to new weights that satisfy the area constraints.

Define $A \triangleq \sum _{i=1}^n \mathcal {M}_i(\omega ^0)$ and

$$\begin{aligned} \bar{a}_i \triangleq A \frac{a_i}{\int _Q \phi (q) dq}. \end{aligned}$$

(2)

In the equal area case, $a_i = a_j = \frac{1}{n} \int _Q \phi (q) dq$ and $\bar{a}_i = \frac{A}{n}$. Note that $\mathcal {M}_i(\omega ^0)= \bar{a}_i$ does not necessarily hold. Define $U^0 =\displaystyle \left\{ \omega \in U \; | \; \sum \nolimits _{i=1}^n \mathcal {M}_i(\omega ) = \sum \nolimits _{i =1}^n \mathcal {M}_i(\omega ^0) \right\}$. Restrict $\mathcal {M}$ to $\omega \in U^0$, and denote this restriction as $\mathcal {M}^0$.

Lemma 2, which gives properties for the Jacobian of $\mathcal {M}^0$, is analogous to Prop. IV.2 from Cortés (2010) but has a more complicated proof due to the sub-partition, $\mathcal {V}^{LR }$. Note that $\mathcal {M}^0$ is a continuous function of $\omega$.

Lemma 2

Let $J(\mathcal {M}^0)$ denote the Jacobian matrix of $\mathcal {M}^0: U^0 \subset {\mathbb {R}}^n \rightarrow {\mathbb {R}}^n$. Then

• 1. $J(\mathcal {M}^0)$ is symmetric;

• 2. Choose $\omega \in U^0$, and consider the graph $\mathcal {G}_{LR }(P,\omega )$ with $\eta$ connected components and associated $\mathbf {1}_n$ and $\mathbf {v}_l$, for all $l \in \{1,\dots ,\eta \}$. Then, these are eigenvectors of $J(\mathcal {M}^0)(\omega )$ with eigenvalue 0;

• 3. The rank of $J(\mathcal {M}^0)(\omega )$ is $n - \eta$.

From here, the existence of a weight assignment that satisfies the $\bar{a}_i$ constraint can be proven. The proof of Theorem 1 follows that of Prop. IV.4 from Cortés (2010) except that here $\mathcal {G}_{LR }$ is not necessarily connected.

Theorem 1

Let $a_1,\dots ,a_n >0$ such that $\sum _{i=1}^n a_i = \int _Q \phi (q) dq$ and let $p_1,\dots ,p_n \in Q$. Let there exist some initial weights, $\omega ^0$, such that $\mathcal {M}_i(\omega ^0) >0$ for each $i\in \{1,\dots ,n\}$. Let $\{\bar{a}_1,\dots ,\bar{a}_n\}$ be as defined in (2). Then there exists a set of weights $\omega = \{\omega _1,\dots ,\omega _n\}$ such that

$$\begin{aligned} \int _{V^{LR }_{i}(P,\omega ,c)} \phi (q) dq = \bar{a}_i, \quad i \in \{1,\dots ,n\}. \end{aligned}$$

3.3 Continuous-space algorithm

This section describes the algorithm used to solve Problem 1. The algorithm alternately updates the agents’ weights and Voronoi cells until the area of the cells has converged to the desired areas. Then, the agents update their positions. Concisely, the algorithm dynamics can be expressed as,

$$\begin{aligned} \begin{pmatrix} \omega ^+ \\ P^+ \end{pmatrix} = \psi \begin{pmatrix} \omega \\ P \end{pmatrix}, \end{aligned}$$

where $\psi$ is a function combining (3) and (4). The details of the dynamic weight and position update are presented next.

3.3.1 Weights update

From Theorem 1 and Lemma 2, there exists weights for which $\mathcal {V}^{LR }(\omega )$ satisfies the area constraints while maintaining constant area in each connected component of $\mathcal {G}_{LR }$. Instead of maintaining constant areas by numerically solving for the $n^\text {th}$ weight, the next procedure is followed in our algorithm. All the weights are iteratively updated so they eventually converge to $\omega ^*$, such that $V^{LR }_{i}(P,\omega ^*) = \bar{a}_i$, thus preserving, $\displaystyle \sum \nolimits _{i=1}^n \mathcal {M}_i(P,\omega ^0) = \sum \nolimits _{i=1}^n \mathcal {M}_i(P,\omega ^*)$. First, define $\mathcal {F}(\omega ) = \displaystyle - F(\omega ) - \sum \nolimits _{i=1}^n \omega _i \bar{a}_i,$ and set $\nabla \mathcal {F}(\omega ) = g(\omega ) = \mathbf {0}_n,$ where $g(\omega ) = \mathcal {M}(\omega _1,\dots ,\omega _n) - (\bar{a}_1,\dots ,\bar{a}_n) = \mathbf {0}_n$. The Jacobi algorithm, Bertsekas and Tsitsiklis (1997),

$$\begin{aligned} \omega ^+ = \omega - \gamma \text {diag} \left( \frac{\partial g_1}{\partial \omega _1},\dots , \frac{\partial g_n}{\partial \omega _n} \right) ^{-1} g(\omega ), \end{aligned}$$

(3)

is then used to find the $\omega$ values that optimize $\mathcal {F}$. The step size can be characterized as in Cortés (2010) Prop. IV.5 to guarantee convergence in the weights. More precisely, let $\mathcal {L}$ be a level set of $\mathcal {F}(\omega )$, and then, $\gamma \in (0, \; Y/B)$, where,

$$\begin{aligned} Y {=} \min _{i \in \{1,\dots ,n\}} \min _{\omega \in \mathcal {L}} \frac{\partial g_i(\omega )}{\partial \omega _i}> 0, B {=} \max _{i \in \{1,\dots ,n\}} \max _{\omega \in \mathcal {L}} \frac{\partial g_i(\omega )}{\partial \omega _i} {>} 0. \end{aligned}$$

To implement this algorithm, the agents each need to compute their $g_i(\omega ) = \mathcal {M}_i(\omega ) - \bar{a}_i$ and $\frac{\partial g_i}{\partial \omega _i}$, where,

3.3.2 Gradient function computation

The agents update their positions according to the derivative of $\mathcal {H}(P,\mathcal {V}^{LR }(P,\omega ,c))$ with respect to position to solve Problem 1. The gradient computation details can be found in Cortés et al. (2005). For a general $\mathcal {H}$, the dynamics for agent i are

$$\begin{aligned} p_i^+ = p_i- h \frac{\partial \mathcal {H}(P,\mathcal {V}^{LR }(P,\omega ,c))}{\partial p_i}, \end{aligned}$$

(4)

where h is an appropriate step size, found via a line search. Eq. 4 only works for convex Q and when the agents are not subject to differential constraints, $\dot{p}_i = f(p_i,u_i)$. The graph-based algorithm is introduced specifically to handle these issues, see Sect. 4.2.2.

For the area only cost function, the gradient is

$$\begin{aligned} \frac{\partial \mathcal {H}^{area }(P,\mathcal {V}^{LR }(P,\omega ,c))}{\partial p_i} = - \int _{\Lambda _i} \phi (q)\hat{n}^\top \frac{\partial q}{\partial p_i} dq. \end{aligned}$$

(5)

Here, q are at the unshared boundary configurations, $q \in \Lambda _i = \partial V^{LR }_{i} \cap D_i$, and $\hat{n}$ is the vector normal to the boundary at q. In other words, the agents move toward the (weighted) center of the unshared boundary of $V^{LR }_{i}$, and stay put when $\Lambda _i = \emptyset$.

When using $\mathcal {H}^{mixed }(P,\mathcal {V}^{LR })$, the right selection of $k_i$ reduces the gradient computation to moving to a generalized centroid of $V^{LR }_{i}$,

$$\begin{aligned}&\frac{\partial \mathcal {H}^{mixed }(P,\mathcal {V}^{LR }(P,\omega ,c))}{\partial p_i} = \int _{V^{LR }_{i}} \frac{\partial J(p_i,q)}{\partial p_i} \phi (q) dq \nonumber \\&\quad - \int _{\Lambda _i} J(p_i,q) \phi (q)\hat{n}^\top \frac{\partial q}{\partial p_i} dq + k_i \int _{\Lambda _i} \phi (q)\hat{n}^\top \frac{\partial q}{\partial p_i} dq. \end{aligned}$$

For $J(p_i,q) = \Vert p_i-q\Vert ^2$ or $J(p_i,q) = \Vert p_i-q\Vert$, choose $k_i = \mathcal {R}_i \triangleq c + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k$.

4 Graph-based limited range spatial load balancing

This section details the graph-based version of Problem 1. As a preprocessing step, a PRM*, G, is constructed in the non-convex environment Q, see Sect. 2.1. The cost to travel between two configurations $q_1$ and $q_2$, $J(q_1,q_2)$, is approximated by the sum of edge costs of the best path in G from $q_1$ to $q_2$. Define a sub-partition of a subset of $\mathcal {N}_G$ as $\mathcal {\widetilde{W}} = \{ \widetilde{W}_i\}^n_{i=1}$, such that $\cup _{i=1}^n \widetilde{W}_i \subseteq \mathcal {N}_G$ and $\widetilde{W}_i \cap \widetilde{W}_j = \emptyset$.

Let $\tilde{a}_1,\dots , \tilde{a}_n \in {\mathbb {R}}_{>0}$, such that $\sum _{i=1}^n \tilde{a}_i = \sum _{q \in \mathcal {N}_G} \phi (q) \beta (q)$, then define the approximate variable area constraint as

$$\begin{aligned} \tilde{a}'_i = \frac{\tilde{a}_i \sum _{q \in \widetilde{\mathcal {W}}} \phi (q) \beta (q)}{\sum _{q \in \mathcal {N}_G} \phi (q) \beta (q)}, \qquad i \in \{1,\dots ,n\}. \end{aligned}$$

The approximated area covered by $q \in \mathcal {N}_G$, $\beta (q)$, is pre-computed as described in Sect. 2.1. The $\sum _{q \in \widetilde{\mathcal {W}}} \phi (q) \beta (q)$ requires knowledge from all agents and varies with each algorithm iteration.

The n agents solve graph-based Problem 2, which approximates the integral as a summation over a set of nodes.

Problem 2

(Graph-based multicenter optimization problem with area constraints)

$$\begin{aligned} \min \quad&\widetilde{\mathcal {H}}^{ }(P,\widetilde{\mathcal {W}})\\ \mathrm{s.t.} \quad&p_i \in \mathcal {N}_G,\\&\tilde{a}'_i = \sum _{q \in \widetilde{W}_i} \phi (q) \beta (q), \quad i \in \{1,\dots ,n\}. \end{aligned}$$

Note that the differential constraint on $p_i$ is removed because it is incorporated into G.

The cost function that the agents minimize is an approximation to either $\mathcal {H}^{centroid }$, $\mathcal {H}^{area }$, or $\mathcal {H}^{mixed }$, given as

$$\begin{aligned} \widetilde{\mathcal {H}}^{centroid }(P,\widetilde{\mathcal {W}}) =&\sum _{i=1}^{n} \sum _{q \in \widetilde{W}_i} J(p_i,q) \phi (q) \beta (q),\\ \widetilde{\mathcal {H}}^{area }(P,\widetilde{\mathcal {W}}) =&-\sum _{i=1}^{n} \sum _{q \in \widetilde{W}_i} \phi (q) \beta (q), \end{aligned}$$

and

$$\begin{aligned}&\widetilde{\mathcal {H}}^{mixed }(P,\widetilde{\mathcal {W}}) = \sum _{i=1}^{n} \big (\sum _{q \in \widetilde{W}_i} J(p_i,q) \phi (q) \beta (q)\\&\quad - k_i \sum _{q \in \widetilde{W}_i} \phi (q) \beta (q)\big ). \end{aligned}$$

To solve Problem 2 algorithmically, each agent has a copy of G and it is assumed that the agents know the positions P and the weights $\omega$ of the other agents by communicating with each other to interchange this information. The assumption on P and $\omega$ can be relaxed in some cases so that it is only necessary to know the positions and weights of a subset of the other agents; this relaxation will be discussed further in Sect. 5.

4.1 Approximate general Voronoi tessellations

Different options are considered for an approximate generalized Voronoi partition. For conciseness, $\widehat{\mathcal {V}}$ is used to represent all approximated Voronoi partitions. In other words, if a results pertains to all the approximate Voronoi partitions, we use $\widehat{\mathcal {V}}$ (e.g. $\widehat{\mathcal {V}}= \widetilde{\mathcal {V}}^{weighted }$ or $\widehat{\mathcal {V}}= \widetilde{\mathcal {V}}^{LR }$ in the following). When the agents have unlimited range, such that $\cup _{i=1}^n W_i = \mathcal {N}_G$, they find the weighted approximate Voronoi partition, $\widetilde{\mathcal {V}}^{weighted }= \{\widetilde{V}^{weighted }_{i}\}_{i=1}^n$,

$$\begin{aligned} \widetilde{V}^{weighted }_{i}= & {} \{ q \in \mathcal {N}_G\; | \; J(p_i,q) - \omega _i\\\le & {} J(p_j,q) - \omega _j, \;\; \forall \, j \ne i \}. \end{aligned}$$

Here, $J(p_i,q)$ is the minimum sum of the edge costs of the optimal path in G defined from $p_i$ to q. Due to the random selection of q when building G, the probability that one node belongs to two different cells of $\widehat{\mathcal {V}}$ is zero.

The limited range agents find a sub-partition, $\cup _{i=1}^n W_i \subset \mathcal {N}_G$, defined as a limited range Voronoi sub-partition $\widetilde{\mathcal {V}}^{LR } = \{\widetilde{V}^{LR }_{i}\}_{i=1}^n$, $\widetilde{V}^{LR }_{i} = \widetilde{V}^{weighted }_{i} \cap \widetilde{D}_i$, where

$$\begin{aligned} \widetilde{D}_i = \left\{ q \in \mathcal {N}_G\; | \; J(p_i,q) - \omega _i + \frac{1}{n} \sum _{k=1}^n \omega _k \le c \right\} . \end{aligned}$$

In order to calculate the approximation of its own cell, $\widehat{V}_{i}$, agent i does a Dijkstra graph search, Dijkstra (1959), starting from its current configuration, $p_i$, and keeps a queue of the vertices it needs to check. To start with, $p_i$ is added to $\widehat{V}_{i}$, and all the outgoing neighboring nodes of $p_i$ are added to the queue. The agent then takes one of the nodes, $q_{check }$, from the queue and checks to see if it is part of $\widehat{V}_{i}$. If $q_{check }$ is a part of $\widehat{V}_{i}$ then its outgoing neighboring nodes are added to the queue. If $q_{check }$ is not added to $\widehat{V}_{i}$, then its neighbors are not added to the queue, see Proposition 1 for the result on why this approach is correct. Agent i constructs $\widehat{V}_{i}$ until the queue is empty.

4.1.1 Properties of $\widehat{\mathcal {V}}$

For $\widetilde{\mathcal {V}}^{weighted }$ the weights need to belong to $U = \{\omega \in {\mathbb {R}}^n \; | \; |\omega _i - \omega _j| \le J(p_i,p_j) \;\; i,j\in \{1,\dots ,n\} \}$. If $\omega \not \in U$ then at least one cell is empty. Since $\widetilde{\mathcal {V}}^{LR }$ is a subset of $\widetilde{\mathcal {V}}^{weighted }$ then the weights must also belong to the set U.

Lemma 3 gives a lower bound on the constant c for a general $J(p_i,q)$ so that $\partial \widetilde{V}^{weighted }_{i} \cap \partial \widetilde{D}_i \ne \emptyset$ for each i. If the initial agent conditions lead to $\partial \widetilde{V}^{weighted }_{i} \cap \partial \widetilde{D}_i = \emptyset$ for all i, then, assuming that $\widetilde{\mathcal {V}}^{LR }$ satisfies the area constraint, Problem 2 is trivially satisfied.

Lemma 3

Assume the triangle inequality holds for $J(p_i,q)$. If $\partial \widetilde{V}^{weighted }_{i} \cap \partial \widetilde{D}_i \ne \emptyset$, then $c \ge \frac{J(p_i,p_j) + \frac{2}{n} \sum _{k=1}^n \omega _k + \omega _i - \omega _j}{2}$.

A tighter bound can be found for particular $J(p_i,q)$. Lemmas 4 and 5 compute such bounds.

Lemma 4

Let $J(p_i,q) = \Vert p_i-q\Vert ^2$. If $\partial \widetilde{V}^{weighted }_{i} \cap \partial \widetilde{D}_i \ne \emptyset$, then $c\ge \frac{(\Vert p_i-p_j\Vert ^2 + \omega _i - \omega _j)^2}{4\Vert p_i - p_j\Vert ^2} - \omega _i + \frac{1}{n} \sum _{k=1}^n \omega _k$.

Lemma 5

Let $J(p_i,q) = \Vert p_i-q\Vert$. If $\partial \widetilde{V}^{weighted }_{i} \cap \partial \widetilde{D}_i \ne \emptyset$ then $c\ge \frac{(\Vert p_i-p_j\Vert + \omega _i - \omega _j)}{2} - \omega _i+ \frac{1}{n} \sum _{k=1}^n \omega _k$.

The proof of Lemma 5 is similar to that of Lemma 4, and therefore omitted for brevity.

The additive property of J allows the agents to only check a connected subset of nodes, $q \in \mathcal {N}_G$, to find the approximated regions $\widetilde{V}^{weighted }_{i}$.

Proposition 1

Assume that J is an additive cost and let there exist an optimal path from $p_i$ to q passing through $q'$. Then, if $q'$ is not part of $\widetilde{V}^{weighted }_{i}$ then q is not part of $\widetilde{V}^{weighted }_{i}$.

Note that $\widetilde{\mathcal {V}}^{LR }$ may not be connected but still only needs to check the same q as $\widetilde{\mathcal {V}}^{weighted }$.

Another useful property of $\widetilde{\mathcal {V}}^{weighted }$ and $\widetilde{\mathcal {V}}^{LR }$ is that they are invariant under translation in the weights, $\widehat{\mathcal {V}}(\omega + t \mathbf {1}) = \widehat{\mathcal {V}}(\omega )$, which follows from the invariance property of their continuous-space counterparts.

4.2 Discrete-space algorithm

Algorithm 1 briefly outlines the general algorithm procedure for Problem 2 with limited ranges that leads to an approximate solution. Note that $\widehat{\mathcal {V}}$ refers to a generic approximation of a Voronoi sub-partition in terms of graph nodes; we refer to $\widehat{\mathcal {V}}$ as approximate generalized Voronoi partitions. First, the agents each determine such a partition, (see Sect. 4.1 for definition and details). Then the weights are updated to reflect the error in the area constraint, the details of which are in Sect. 4.2.1. These two steps are alternated until the area constraints are satisfied to within a specified error, which can be reduced by increasing the number of nodes in G. Next, the agents move to a neighboring node that will decrease $\widetilde{\mathcal {H}}^{ }$, see Sect. 4.2.2. The steps are repeated until none of the agents are able to update their positions, $P=P^+$.

4.2.1 Updating the agent weights

Recall, for Problem 2, each agent’s cell should satisfy an approximate area constraint, $\tilde{a}'_i$. When the agents have unlimited ranges, $\tilde{a}'_i = \tilde{a}_i$. Agents with limited range follow the procedure outlined in Sect. 3.2.2 to find a weight assignment for $\widetilde{\mathcal {V}}^{LR }$. Let $\omega _0$ be the set of weights, then define $\tilde{A} = \sum _{q \in \widetilde{\mathcal {V}}^{LR }(\omega _0)} \phi (q) \beta (q)$. The new variable area constraint is $\bar{a}_i = \frac{\tilde{a}_i \tilde{A}}{\sum _{q \in \mathcal {N}_G} \phi (q) \beta (q)}$. Let $\hat{a}_i$ indicate either $\tilde{a}_i$ or $\bar{a}_i$.

Define the error between the current and specified area as

$$\begin{aligned} {\widetilde{g}}(\omega ) = \bigg (\sum _{q \in {\widehat{V}}_1(\omega )} \phi (q)\beta (q) - \hat{a}_1, \dots , \sum _{q \in \widehat{V}_n(\omega )} \phi (q)\beta (q) - \hat{a}_n\bigg ). \end{aligned}$$

Next, each agent updates $\omega$ to reduce the area error.

From Bertsekas and Tsitsiklis (1997), the Jacobian update used to minimize $\widetilde{g}(\omega )$ is approximated as

$$\begin{aligned} \omega _i^+ = \omega _i - \gamma \bigg (\frac{\partial {\widetilde{g}}(\omega )}{\partial \omega _i} \bigg )^{-1}{\widetilde{g}}_i(\omega ), \end{aligned}$$

which converges for a small enough $\gamma > 0$. The partial derivatives of $\widetilde{g}$ are approximated as,

$$\begin{aligned} \frac{\partial \widetilde{g}}{\partial \omega _i}(\omega ) \approx&\frac{\sum _{q \in \widehat{V}_i^i} \phi (q)\beta (q) - \sum _{q \in \widehat{V}_i} \phi (q)\beta (q) }{\Delta \omega _i}, \end{aligned}$$

(6)

where $\widehat{V}_i^i$ is the Voronoi cell for agent i with $\omega = \{\omega _1, \dots , \omega _i+\Delta \omega _i, \dots , \omega _n\}$. Note that $\Delta \omega _i > 0$ needs to be small enough to guarantee convergence but also large enough that $\widehat{V}^i_i \ne \widehat{V}_i$. The $\widehat{V}^i_i$ can be computed with a single Dijkstra graph search so agent i can easily compute (6).

The algorithm loops through determining $\widehat{\mathcal {V}}$ and updating $\omega$ until the area constraint is satisfied to within a specified error.

4.2.2 Updating the agent positions

After $\widehat{V}_i$ and $\omega$ have been determined, agent i decides where to move. Ideally, each agent minimizing $\widetilde{\mathcal {H}}^{centroid }$ or $\widetilde{\mathcal {H}}^{mixed }$ would move to a position in the generalized centroid set on $\widehat{V}_i$, which is computationally intensive. Instead, agent i moves in the direction of one of the generalized centroids by moving to a neighboring node of $p_i$ such that

$$\begin{aligned} p_i^+ \in {{\mathrm{argmin}}}_{p \in \mathcal {N}^{out }_G(p_i)} \;\; \sum _{q \in \widehat{V}_i} J(p,q) \phi (q) \beta (q). \end{aligned}$$

If the agents have limited range, and are solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$, they update their position by approximating (5),

$$\begin{aligned} \frac{\partial \widetilde{\mathcal {H}}^{area }(P,\widetilde{\mathcal {V}}^{LR })}{\partial p_i} =&\sum _{i=1}^n \sum _{q \in \lambda _i} \phi (q) \hat{n}^\top (q) \frac{\partial q}{\partial p_i}. \end{aligned}$$

The agent then moves to a neighboring node in the graph that is in a direction as close as possible to $\frac{\partial \widetilde{\mathcal {H}}^{area }(P,\widetilde{\mathcal {V}}^{LR })}{\partial p_i}$.

Note that because the agent is moving to another node in the graph, the new agent position will automatically be in Q. The new agent position is shared among the Voronoi neighbors of agent i, who need it to calculate their Voronoi cell. The algorithm loops through these steps until the agents’ positions become fixed; indicating that convergence has been reached. Note that when iterating these steps in the continuous-space version, Problem 1, agents are locally minimizing the functional with respect to their positions.

5 Distributed algorithm properties

This section looks at the distributed nature of the Graph-based Spatial Load Balancing algorithm using $\widetilde{\mathcal {V}}^{weighted }$ and $\widetilde{\mathcal {V}}^{LR }$. The following discussion focuses on the discrete-space case, but analogous considerations hold for the continuous-space counterpart.

The information that agent i needs for the implementation of the Graph-based Spatial Load Balancing using $\mathcal {V}^{weighted }$ is limited to those other agents j whose approximated regions are connected to the approximated region of i via boundary nodes (or $V^{weighted }_{i}(P,\omega ;J) \cap V^{weighted }_{j}(P,\omega ;J) \ne \emptyset$ in the continuous-space counterpart). In the case where no obstacles are present, this property generally involves a limited number of agents which depends on the specific metric. In the Euclidean metric case, where, for equal weights, the generic number of neighbors is six (Okabe et al. 2000). When obstacles are present, this characterization is more difficult. The distributed properties of the Graph-based Spatial Load Balancing using $\widetilde{\mathcal {V}}^{LR }$ are discussed below, but first an alternate definition of $\widetilde{\mathcal {D}}$ using a maximum radius is introduced.

5.1 Alternate definition of $\widetilde{\mathcal {D}}$

Under certain costs, $J(p_i,q)$, $D_i$ can be defined as a ball with radius $R_i$. This definition is intuitive in a way that the c definition, (1), is not. Assume $J(p_i,q) = \Vert p_i - q\Vert ^2$ or $J(p_i,q) = \Vert p_i - q\Vert$, then the radius of the ball defined by $\widetilde{D}_i$ is denoted by $R_i$ for all $i \in \{1,\dots ,n\}$. Recall $\mathcal {R}_i \triangleq c + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k$, then, using the definition of $D_i$ at the boundary, $J(p_i,q) = \Vert p_i-q\Vert ^2$ implies $R_i = \mathcal {R}_i^{1/2}$ and $J(p_i,q) = \Vert p_i-q\Vert$ implies $R_i = \mathcal {R}_i$.

Depending upon the physical system, an upper bound may be imposed on $R_i$, denoted by $R_{max }$. We want to remove c from the definition of $D_i$ and replace it with the fixed $R_{max }$. To remove c, let c be a function of $R_{max }$ and $\omega$, instead of a constant. Then, define $c_{max } = \displaystyle R_{max } - \max _k(\omega ) + \frac{1}{n} \sum _{k=1}^n \omega _k$. Substituting $c_{max }$ into $\mathcal {R}_i \triangleq c + \omega _i - \frac{1}{n} \sum \nolimits _{k=1}^n \omega _k$, gives,

$$\begin{aligned} \mathcal {R}_i&= R_{max } - \max _k(\omega ) + \frac{1}{n} \sum _{k=1}^n \omega _k + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k, \\&= R_{max } - \max _k(\omega ) + \omega _i. \end{aligned}$$

Notice that now $\mathcal {R}_i$, and hence $R_i$, are no longer dependent on c nor the mean of $\omega$, but on $R_{max }$ and the maximum value of $\omega$. The new definition of $D_i$ is,

$$\begin{aligned} D_i = \{q \in Q \; | \; J(p_i,q) \le R_{max } - \max _k(\omega ) + \omega _i \}, \end{aligned}$$

(7)

when $J(p_i,q) = \Vert p_i-q\Vert$, and is

$$\begin{aligned} D_i = \{q \in Q \; | \; J(p_i,q) \le \sqrt{R_{max } - \max _k(\omega ) + \omega _i} \}, \end{aligned}$$

when $J(p_i,q) = \Vert p_i-q\Vert ^2$. Algorithm 1 needs some minor modifications to account for the maximum radius constraint. First, in Lines 6 and 12, the primitive $\mathsf {VoronoiPartition}$ now takes inputs $R_{max }$ and $R_i$ instead of c. Then, after Line 11, $R_i$ is determined.

Let $D_i$ denote the continuous-space counterpart of $\widetilde{D}_i$. Then defining $D_i$ using $R_{max }$ causes problems in Lemma 1 because $\max _{k} \omega$ is not differentiable. However, given the $\max$ operator’s properties, one can conjecture that an analogous result exists using generalized gradients. As a consequence, assuming the analogous result leads to $\mathcal {M}(\omega )$ being gradient (i.e. that the weights-to-area map is in the generalized gradient of F,) then all other results follow. In particular, in Lemma 2, the new $D_i$ still satisfies the conditions on the partial derivatives. With the assumption that Lemma 1 holds, a weight assignment exists that satisfies the area constraint. Then, the convergence result in Theorem 2 still holds for the $D_i$ definition using $R_{max }$, (7).

5.2 Distributed properties using $\widetilde{\mathcal {V}}^{LR }$

While the algorithm in Cortés (2010) for solving the spatial load balancing problem is distributed in the sense that only information is needed for neighboring agents, these neighboring agents may be significantly far away from one another. Especially when Euclidean norms are used, the limited range constraint forces the agents to only consider neighbors within a certain distance of each other.

More precisely, the computation of $\widetilde{V}^{LR }_{i}(P,\omega )$ requires knowledge of the positions and weights of agent i’s neighbors and knowledge of the mean of the weights for $\widetilde{D}_i$. The latter can be computed using a distributed consensus algorithm performed over a connected communication graph. This communication graph might not be $\mathcal {G}_{LR }$, since $\mathcal {G}_{LR }$ is not necessarily connected. If $\widetilde{D}_i$ is defined as in Sect. 5.1, the agents need the maximum $\omega$ value instead of the mean. The maximum value is found using a $\max$ operation over a connected system, requiring fewer communications between the agents.

Before each weight update, the area covered by $\widetilde{\mathcal {V}}^{LR }$ needs to be determined. Again, a distributed consensus algorithm over a connected communication graph is needed. Once inside the weights update loop, agents only need the information from their cell, $\widetilde{V}^{LR }_{i}$, to determine $\omega ^+_i$. Likewise, the position update using the gradient of $\widetilde{\mathcal {H}}^{area }(P,\widetilde{\mathcal {V}}^{LR })$ or the centroid of $\widetilde{V}^{LR }_{i}$ for $\widetilde{\mathcal {H}}^{mixed }(P,\widetilde{\mathcal {V}}^{LR })$, only requires knowledge from the agent’s own cell. In all, the algorithm is distributed over the smallest connected graph containing $\mathcal {G}_{LR }$.

The $R_{max }$ constraint can be used to define a disk graph $\mathcal {G}_{2R_{max }}$ that is sufficient for agents to determine neighbors in $\mathcal {G}_{LR }$. When using a general J, the balls are defined as a reachable set. If J is radially unbounded, the balls are compact sets. In the Euclidean metric case, the balls are circles whose radii are related to $R_{max }$ and correspond to the standard r-disk graph. Define $\mathcal {G}_{2R_{max }}$ over the set of agents, where a (communication) edge exists between agents i and j if and only if the balls centered at the agents’ position with radius $R_{max }$ intersect, $\mathbb {B}(p_i,R_{max }) \cap \mathbb {B}(p_j,R_{max }) \ne \emptyset$. The $\mathcal {G}_{2R_{max }}$ can be used to determine an over approximation of the sets of neighboring agents in $\mathcal {G}_{LR }$. To see this approximation, note that $\widetilde{V}^{LR }_{i} \subseteq \widetilde{D}_i \subseteq \mathbb {B}(p_i,R_{max })$, for all $i \in \{1,\dots ,n\}$. Therefore, $\widetilde{V}^{LR }_{i} \cap \widetilde{V}^{LR }_{j} \ne \emptyset$ only if $\widetilde{D}_i \cap \widetilde{D}_j \ne \emptyset$, which happens only if $\mathbb {B}(p_i,R_{max }) \cap \mathbb {B}(p_j,R_{max }) \ne \emptyset$. This result implies that agent i can compute its cell, $\widetilde{V}^{LR }_{i}$, communicating only with neighbors j in $\mathcal {G}_{2R_{max }}$. In other words, an agent only needs to communicate with other agents within a distance of $2R_{max }$ of itself, $\Vert p_i - p_j \Vert \le 2R_{max }$.

6 Convergence

The spatial load balancing algorithm in Cortés (2010) is shown to converge to a $(P^*,\mathcal {V}^{weighted }(P^*,\omega ^*;J))$ solution of Problem 1 for convex environments. A similar result holds for non-convex Q since there exists $\omega$ that allows a generalized Voronoi partition $\mathcal {V}^{weighted }(P,\omega ;J)$ to satisfy the constraints. Lemma 6 is used to extend Prop. IV.4 from Cortés (2010) to non-convex Q; Prop. IV.4 sates there exists a set of weights that make $\mathcal {V}^{weighted }$ satisfy the area constraints in a convex continuous-space.

Lemma 6

Let $\mathcal {V}^{weighted }$, $J(p_i,q)$, $\phi (q)$, and $\omega$ be defined as above. Define the weights-to-area map as

$$\begin{aligned} \mathcal {M}(P,\omega ) = \left( \int _{V^{weighted }_{i}(\omega )} \phi (q) dq, \dots , \int _{V^{weighted }_{n}(\omega )} \phi (q) dq \right) . \end{aligned}$$

Then, $\mathcal {M}$ is gradient, $\nabla F = - \mathcal {M}$, where $F:{\mathbb {R}}^n \rightarrow {\mathbb {R}}$,

$$\begin{aligned} F(\omega ) = \sum _{j=1}^n \int _{V^{weighted }_{j}(\omega )} (J(p_j,q)-\omega _j)\phi (q)dq. \end{aligned}$$

The proof of Lemma 6 is similar to that of Lemma 1 and therefore omitted.

For the discrete case note that for any $\widetilde{\mathcal {W}} =\{\widetilde{W}_i\}_{i=1}^n$ partition of $\mathcal {N}_G$, one can find (many) continuous-space partitions $\mathcal {W}=\{W_i\}_{i=1}^n$ such that $\widetilde{W}_i = W_i \cap \mathcal {N}_G$ and $\mathcal {W}$ satisfies the constraints. As the number of nodes in $\mathcal {N}_G$ goes to infinity, $\widetilde{\mathcal {W}}$ will converge to a $\mathcal {W}$. Due to integration properties, and because $\mathcal {H}^{centroid }(P,\mathcal {W})$ is continuous,

$$\begin{aligned} |\mathcal {H}^{centroid }(P,\mathcal {W}) - \widetilde{\mathcal {H}}^{centroid }(P,\widetilde{\mathcal {W}})| \le&\epsilon , \end{aligned}$$

(8)

is true for a sufficiently small sample dispersion.

The Graph-based Spatial Load Balancing algorithm with $\mathcal {V}^{weighted }$ cannot converge to the exact partition and centroids of the continuous problem, but an approximate solution is guaranteed, see Theorem 2.

Theorem 2

The unlimited range Graph-based Spatial Load Balancing algorithm is guaranteed to converge to an approximate solution $(P^*,\widetilde{\mathcal {V}}^{weighted }(P^*,\omega ^*))$ which is in a continuous-space set defined by $\Vert \mathcal {H}^{centroid }(P^*,\mathcal {V}^{weighted })(P,\omega ) - \mathcal {H}^{centroid }(P^*,\mathcal {V}^{weighted }(P^*,\omega ^*)) \Vert \le 2 \epsilon$.

Proving convergence of the limited range $\textsc {Graph-based Spatial Load Balancing}$ relies on the continuous-space convergence Theorem 3 which is only shown to converge for $\mathcal {H}^{area }(P,\mathcal {V}^{LR })$.

Theorem 3

The continuous-space version of Algorithm 1, used to solve the limited range spatial load balancing problem, converges to a solution $(P^*,\mathcal {V}^{LR }(P^*,\omega ^*))$ when $\mathcal {H} = \mathcal {H}^{area }(P,\mathcal {V}^{LR })$.

Then, convergence to an approximate solution is guaranteed by Lemma 7.

Lemma 7

The limited range Graph-based Spatial Load Balancing using $\widetilde{\mathcal {H}}^{area }$ is guaranteed to converge to an approximate solution $(P^*,\widetilde{\mathcal {V}}^{LR }(P^*,\omega ^*))$ which is in a continuous-space set defined by $\Vert \mathcal {H}^{area }(P^*,\mathcal {V}^{LR }(P),\omega ) - \mathcal {H}^{area }(P^*,\mathcal {V}^{LR }(P^*,\omega ^*)) \Vert \le 2 \epsilon$.

The proof of Lemma 7 is similar to that of Theorem 2 and therefore omitted.

7 Simulations

The simulations below examine agents without differential constraints whose edge cost, $J_e$, is Euclidean distance and for Dubins vehicle agents whose edge cost is the distance traveled. There are simulations for six agents each of them solving graph-based Problem 2 with an equal area constraint and a uniform probability density function, $\phi (q) = 1$, $\forall \, q \in \mathcal {N}_G$. Each agent is initialized with $\omega _i = 5$. The simulations compare the limited range defined by a constant $c = 3$ and $R_{max } = 3.5$.

All simulations have the same initial agent positions; clustered together in the top right corner. The simulations were run for a graph constructed with 2000 samples and a more dense graph constructed using 5000 samples. The graph should be constructed such that the edge lengths are less than $\partial \widetilde{D}_i$. This will ensure that there exists neighboring nodes of $p_i$ within $\widetilde{V}^{LR }_{i}$ for the agent to move to.

7.1 Voronoi graph partitions

This section compares the weighted Voronoi graph partition, $\widetilde{\mathcal {V}}^{weighted }$ for six agents solving Problem 2. Figures 2 and 3 are the initial and final $\widetilde{\mathcal {V}}^{weighted }$ partitions, respectively, in the non-convex environment using the graph with 5000 samples.

Fig. 2

The initial 5000 node graph $\widetilde{\mathcal {V}}^{weighted }$ for six agents before solving Problem 2 with $\widetilde{\mathcal {H}}^{centroid }$

Fig. 3

The final 5000 node graph $\widetilde{\mathcal {V}}^{weighted }$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{centroid }$

The initial and final limited range Voronoi graph partitions for agents solving Problem 2 with $\widetilde{\mathcal {H}}^{ } = \widetilde{\mathcal {H}}^{area }$ in the non-convex environment using the 5000 sample graph are in Figs. 4, 5 and 6. Figure 5 is the final $\widetilde{\mathcal {V}}^{LR }$ partition when $c=3$. When $R_{max } = 3.5$, the agents’ final $\widetilde{\mathcal {V}}^{LR }$ partition is in Fig. 6. The final $\widetilde{\mathcal {V}}^{LR }$ partitions for the 5000 sample graph in the non-convex environment under $\widetilde{\mathcal {H}}^{ } = \widetilde{\mathcal {H}}^{Mixed }$ are Fig. 7 when $c=3$, and Fig. 8 when $R_{max }=3.5$.

Fig. 4

The Initial 5000 node graph $\widetilde{\mathcal {V}}^{LR }$ with $c=3$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$

Fig. 5

The final 5000 node graph $\widetilde{\mathcal {V}}^{LR }$ with $c=3$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$

Fig. 6

The final 5000 node graph $\widetilde{\mathcal {V}}^{LR }$ with $R_{max } = 3.5$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$

Fig. 7

The final 5000 node graph $\widetilde{\mathcal {V}}^{LR }$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{mixed }$

Fig. 8

The final 5000 node graph $\widetilde{\mathcal {V}}^{LR }$ for six agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{mixed }$

7.2 Evolution of $\widetilde{\mathcal {H}}^{ }$

The following simulations are a comparison of the evolution of the different cost functions for the various problems. The plots show the algorithm converges to a solution.

The evolution of $\widetilde{\mathcal {H}}^{centroid }$ for agents solving Problem 2 in the non-convex environment using partition $\widetilde{\mathcal {V}}^{weighted }$ is in Fig. 9. The cost function decreases monotonically as expected.

Fig. 9

The evolution of $\widetilde{\mathcal {H}}^{centroid }$ obtained by solving Problem 2 using $\widetilde{\mathcal {V}}^{weighted }$, where the solid line is the 5000 node graph and the dashed is the 2000 node graph

Figure 10 is the evolution of $\widetilde{\mathcal {H}}^{area }$ for the agents solving Problem 2 with limited ranges in the non-convex environment. The evolution of $\widetilde{\mathcal {H}}^{mixed }$ for the limited range agents in the convex environment solving Problem 2 is in Fig 11. Both the 2000 and 5000 sample graphs produce costs that decrease smoothly until the algorithm gets close to convergence then chatters slightly. It is important to note that when the algorithm uses $\widetilde{\mathcal {H}}^{area }$ or $\widetilde{\mathcal {H}}^{mixed }$, the position update is approximate. The agents do not follow the gradient exactly, but rather a close approximation based on the neighboring nodes. The more nodes there are in the graph, the less error there will be in following the gradient. This can be seen by comparing the 2000 and 5000 node graphs. The 5000 node graph produces a cost function plot with less pronounced increases and less chattering.

Fig. 10

The evolution of $\widetilde{\mathcal {H}}^{area }$ obtained by solving Problem 2 using $\widetilde{\mathcal {V}}^{LR }$ from the 2000 node graph with $c=3$ (blue dash-dot line), $R_{max }=3.5$ (red solid line), from the 5000 node graph with $c=3$ (cyan dashed line), $R_{max }=3.5$ (magenta dotted line) (Color figure online)

Fig. 11

The evolution of $\widetilde{\mathcal {H}}^{mixed }$ obtained by solving Problem 2 using $\widetilde{\mathcal {V}}^{LR }$ from the 2000 node graph with $c=3$ (blue dash-dot line), $R_{max }=3.5$ (red solid line), from the 5000 node graph with $c=3$ (cyan dashed line), $R_{max }=3.5$ (magenta dotted line) (Color figure online)

The following simulation is with seven agents in a hallway type environment. The initial and final agent partitions are shown in Figs. 12 and 13. The area-only cost function is plotted in Fig. 14 for both the c and $R_{max }$ definitions of the limited range sub-partition. The cost function decreases and then chatters due to the error in the gradient. Figure 15 is the mixed cost function. The c definition decreases monotonically while the $R_{max }$ definition increases first then decreases monotonically.

Fig. 12

A 5000 node graph initial $\widetilde{\mathcal {V}}^{LR }$ for seven agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$

Fig. 13

A 5000 node graph final $\widetilde{\mathcal {V}}^{LR }$ for seven agents obtained by solving Problem 2 with $\widetilde{\mathcal {H}}^{area }$

Fig. 14

The evolution of $\widetilde{\mathcal {H}}^{area }$ obtained by solving Problem 2 using $\widetilde{\mathcal {V}}^{LR }$ from a 5000 node graph with $c=3$ (blue dash-dot line), $R_{max }=3.5$ (red solid line) (Color figure online)

Fig. 15

The evolution of $\widetilde{\mathcal {H}}^{mixed }$ obtained by solving Problem 2 using $\widetilde{\mathcal {V}}^{LR }$ from a 5000 node graph with $c=3$ (blue dash-dot line), $R_{max }=3.5$ (red solid line) (Color figure online)

7.2.1 Dubins’ vehicle results

Simulations for Dubins’ vehicle agents, subject to limited ranges, solving Problem 2 using $\widetilde{\mathcal {V}}^{LR }$ were run for a 2000 node graph. Figure 16 is the evolution of $\widetilde{\mathcal {H}}^{area }$ and Fig. 17 is the evolution of $\widetilde{\mathcal {H}}^{mixed }$ in the non-convex environment. The blue dashed lines are for $\widetilde{\mathcal {V}}^{LR }$ with a constant $c=7$ and the red solid lines are for $R_{max } = 8$. The $\widetilde{\mathcal {H}}^{area }$ and $\widetilde{\mathcal {H}}^{mixed }$ decrease initially and then chatters until convergence is reached. The $\widetilde{\mathcal {H}}^{mixed }$ decreases smoothly for $\widetilde{\mathcal {V}}^{LR }$ with a constant $c=7$. The chattering produced by the Dubins’ vehicle is due to the resolution in the graph. If the graph were to have more nodes, the position update would have less error and therefore less chattering. Because an increase in the number of nodes in the graph causes the algorithm to increase in run time, a balance between the run time and the smoothness of the cost function decrease is needed.

Fig. 16

The evolution of $\widetilde{\mathcal {H}}^{area }$ obtained by solving Problems 2 for Dubins’ vehicle using $\widetilde{\mathcal {V}}^{LR }$, where the blue dashed line is with $c=7$ and solid red line is with $R_{max }=8$ (Color figure online)

Fig. 17

The evolution of $\widetilde{\mathcal {H}}^{mixed }$ obtained by solving Problems 2 for Dubins’ vehicle using $\widetilde{\mathcal {V}}^{LR }$, where the blue dashed line is with $c=7$ and solid red line is with $R_{max }=8$ (Color figure online)

8 Conclusions

A limited range spatial load balancing problem for agents subject to differential constraints in a non-convex environment is defined and discussed. To handle differential constraints, the problem is redefined using a probabilistic roadmap star (PRM*) and an algorithm is given that finds an approximate solution to the original problem. We discuss how introducing the limited range sub-partition and determining a subset of agents containing the Voronoi neighbors of a specific agent limits the amount of communication between agents. A convergence proof is given for the Graph-based Spatial Load Balancing algorithm. All other defined approximated problems are shown to converge in simulation. Future work includes more extensive differential constraint simulations as well as implementation of the algorithm on a set of mobile robots.

Appendix

Proof of Lemma 1

Take the derivative of $F(\omega )$ with respect to $\omega _i$ using the Leibniz rule (Flanders 1973), which applies over general domains,

$$\begin{aligned}&\frac{\partial F(\omega )}{\partial \omega _i} = \frac{-n}{1-n} \left( \sum _{j=1}^n \int _{V^{LR }_{j}} - \left[ \frac{\partial q}{\partial \omega _i} \right. \right. \\&\left. \quad \times \left( \frac{\partial }{\partial q}\left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) \right] \cdot dq \\&\quad +\sum _{j=1}^n \int _{\partial V^{LR }_{j}} \frac{\partial q}{\partial \omega _i} \cdot \left( \left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) dq \\&\left. \quad +\sum _{j=1}^n \int _{V^{LR }_{j}} \frac{\partial }{\partial \omega _i} \left( \left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q) \right) dq \right) . \end{aligned}$$

The first term,

$$\begin{aligned} \sum _{j=1}^n&\int _{V^{LR }_{j}} -\left[ \frac{\partial q}{\partial \omega _i} \right. \\&\left. \times \left( \frac{\partial }{\partial q}\left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) \right] \cdot dq = 0. \end{aligned}$$

There are two vectors in the $(q_1,q_2)$ plane being crossed, resulting in a vector perpendicular to the $(q_1,q_2)$ plane, in dot product with a vector in the $(q_1,q_2)$ plane, thus resulting in a zero value. The second term becomes

$$\begin{aligned}&\sum _{j=1}^n \int _{\partial V^{LR }_{j}} \frac{\partial q}{\partial \omega _i} \cdot \left( \left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) dq \\&\quad = \sum _{j=1}^n \int _{\triangle _{ij}} \hat{n}^\top \frac{\partial q}{\partial \omega _i} \left( \left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) dq \\&\qquad +\sum _{j = 1}^n \int _{\Lambda _j} \hat{n}^\top \frac{\partial q}{\partial \omega _i} \left( \left( J(p_j,q)-\omega _j+\frac{1}{n} \sum _{k=1}^n \omega _k-c\right) \phi (q)\right) dq. \end{aligned}$$

This term then vanishes along $\triangle _{ij}$ because the opposing normal vectors are multiplying the same terms which then cancel each other out. For all $q \in \Lambda _j$, $J(p_j,q)-\omega _j + \frac{1}{n} \sum _{k=1}^n \omega _k - c= 0$. The third term,

Putting everything together results in

$$\begin{aligned} \frac{\partial F}{\partial \omega _i} = -\int _{V^{LR }_{i} } \phi (q)dq = - \mathcal {M}_i(\omega ), \;\; i \in \{1,\dots ,n\}. \end{aligned}$$

$\square$

Proof of Lemma 2

Fact 1 follows from $\mathcal {M}$, and thus $\mathcal {M}^0$, being gradient. For Fact 2, by definition, the sum of $\mathcal {M}^0$ stays constant when $\omega$ is updated, therefore, the range of $\mathcal {M}^0$ is in $\{m \in {\mathbb {R}}_{\ge 0}^n \, | \, \mathbf {1}_n^\top m = A\}$, and thus, $\mathbf {1}_n^\top J(\mathcal {M}^0) = \mathbf {0}_n$. Because $J(\mathcal {M}^0)$ is symmetric, $\mathbf {1}_n$ is a right eigenvector with eigenvalue 0. Consider $\omega \in U^0$ and let $\eta$ be the number of connected components to $\mathcal {G}_{LR }\equiv \mathcal {G}_{LR }(P,\omega )$, such that each connected component, $\mathcal {G}_l$, has a corresponding vector $\mathbf {v}_l$ associated with it. Then, because each $\mathcal {G}_l$ maintains a constant area during the weights update, additional eigenvectors with eigenvalue zero can be defined, $\mathbf {v}_l^\top J(\mathcal {M}^0)(\omega ) = \mathbf {0}_n$. For Fact 3, first show that for $i \in \{1,\dots ,n\}$ and $(\omega _1,\dots ,\omega _i,\dots ,\omega _n)$, $(\omega _1,\dots ,\omega '_i,\dots ,\omega _n)$ such that $\omega '_i \ge \omega _i$,

$$\begin{aligned} \mathcal {M}^0_i(\omega _1,\dots ,\omega '_i,\dots ,\omega _n) \ge&\mathcal {M}^0_i(\omega _1,\dots ,\omega _i,\dots ,\omega _n), \\ \mathcal {M}^0_j(\omega _1,\dots ,\omega '_i,\dots ,\omega _n) \le&\mathcal {M}^0_j(\omega _1,\dots ,\omega _i,\dots ,\omega _n), j{\ne }i. \end{aligned}$$

Recall, $V^{LR }_{i} = V^{weighted }_{i} \cap D_i$. First, how $\partial V^{weighted }_{i}$ changes with respect to $\omega$ is examined. When $q \in \triangle _{ij}$ then $J(p_i,q) - \omega _i = J(p_j,q) - \omega _j$. If $\omega _i$ increases, then the boundary $\triangle _{ij}$ moves further away from $p_i$ which increases the area of $V^{weighted }_{i}$ and decreases the area of $V^{weighted }_{j}$. Second, examine the change in the boundary of $D_i$. Let $J_{max }(p_i,q)$ be the cost at the boundary of $D_i$, then $J_{max }(p_i,q) = c + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k$. If $\omega _i$ increases then so does $J_{max }(p_i,q)$ which in turn increases the area of $D_i$. For $D_j$, if $\omega _i$ increases then $J_{max }(p_j,q)$ decreases and hence the area of $D_j$ decreases. Then, the partial derivatives of $\mathcal {M}^0$ for $\mathcal {V}^{LR }$ at $\omega$ satisfy

$$\begin{aligned} \frac{\partial \mathcal {M}^0_i}{\partial \omega _i} \ge 0, \quad \frac{\partial \mathcal {M}^0_j}{\partial \omega _i} \le 0, \quad j \ne i. \end{aligned}$$

The above expression, when combined with Facts 1 and 2, leads to $J(\mathcal {M}^0)(\omega )$ being the Laplacian of $\mathcal {G}_{LR }$. Because $\mathcal {G}_{LR }$ has exactly $\eta$ connected components, the rank($J(\mathcal {M}^0))(\omega ) = n- \eta$. $\square$

Proof of Theorem 1

First, consider the function $G \, : \, U^0 \rightarrow {\mathbb {R}}$ defined as

$$\begin{aligned} G(\omega ) = \frac{1}{2} \Vert \mathcal {M}^0(\omega ) - (\bar{a}_1,\dots ,\bar{a}_n) \Vert ^2. \end{aligned}$$

(9)

This function is continuous and invariant under translations. Therefore, it induces a continuous function on $U^0/\sim$, the quotient set of $U^0$ for which $\omega _1 \sim \omega _2$ if they differ in a translation. It can be proven that $U^0/\sim$ is a compact set and there is a minimizer of G on $U^0/\sim$. Evaluate the derivative of (9) with respect to $\omega$ at $\omega ^*$,

$$\begin{aligned} 0&= \frac{\partial }{\partial \omega _i} \bigg |_{\omega = \omega ^*} \bigg (\frac{1}{2} \Vert \mathcal {M}^0(\omega ) - (\bar{a}_1,\dots ,\bar{a}_n)\Vert ^2 \bigg )\\&= \sum _{k=1}^n \left( \mathcal {M}^0_k(\omega ^*) - \bar{a}_k\right) \frac{\partial \mathcal {M}^0_k}{\partial \omega _i}\bigg |_{\omega = \omega ^*}, \; \forall \; i \in \{1,\dots , n\}, \end{aligned}$$

which can then be expressed as $\displaystyle (\mathcal {M}^0(\omega ^*) - (\bar{a}_1,\dots ,\bar{a}_n))J(\mathcal {M}^0)(\omega ^*) = \mathbf {0}_n$. The weights-to-area map, $\mathcal {M}^0(\omega )$, is differentiable in the same way that $F(\omega )$ from Lemma 1 is differentiable. Note that $\omega ^*$ is in the interior of $U^0/\sim$ because $\bar{a}_i >0$ (boundary points are those for which the cell of an agent is empty). Recall that, over $U^0$, there are eigenvectors such that $\mathbf {v}_l^\top J(\mathcal {M}^0)(\omega ^*) = \mathbf {0}_n$ for all $l \in \{1,\dots ,\eta \}$ and that the rank$(J(\mathcal {M}^0)(\omega ^*)) = n - \eta$. From here, deduce that $\mathcal {M}^0(\omega ^*) - (\bar{a}_1,\dots ,\bar{a}_n) = \sum _{l=1}^n b_l \mathbf {v}_l$ for some $b_l \in {\mathbb {R}}$. Next, notice that $0 = \mathbf {v}_l^\top (\mathcal {M}^0(\omega ^*) - (\bar{a}_1,\dots ,\bar{a}_n)) = b_l n_l$, and therefore $b_l = 0$ for all $l \in \{1,\dots ,\eta \}$, or $\mathcal {M}^0(\omega ^*) = (\bar{a}_1,\dots ,\bar{a}_n)$. $\square$

Proof of Lemma 3

Because $q \in \partial \widetilde{D}_i$, $J(p_i,q) = c + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k$. This same q is also in $\partial \widetilde{V}^{weighted }_{i}$,

$$\begin{aligned} J(p_i,q) - \omega _i + \omega _j&= J(p_j,q), \text { for some } j. \end{aligned}$$

Substituting the above expression into the triangle inequality, $J(p_i,q) + J(p_j,q) \ge J(p_i,p_j)$, gives

$$\begin{aligned} 2c - \frac{2}{n} \sum _{k=1}^n \omega _k + \omega _i + \omega _j&\ge J(p_i,p_j). \end{aligned}$$

Therefore, the c must be larger than

$$\begin{aligned} c \ge \frac{J(p_i,p_j) + \frac{2}{n} \sum _{k=1}^n \omega _k-\omega _i - \omega _j}{2}. \end{aligned}$$

$\square$

Proof of Lemma 4

Because $q \in \widetilde{V}^{weighted }_{i}$ then

$$\begin{aligned} \Vert p_i-q\Vert ^2 - \omega _i = \Vert p_j-q\Vert ^2 - \omega _j \text { for some } j. \end{aligned}$$

(10)

Now, squaring the triangle inequality of the Euclidean norm,

$$\begin{aligned} \Vert p_j - q\Vert ^2&\ge \Vert p_i - p_j\Vert ^2 + \Vert p_i - q \Vert ^2 - 2\Vert p_i-p_j\Vert \Vert p_i-q\Vert . \end{aligned}$$

Substitute this equation into (10), and rearranging, gives

$$\begin{aligned} \Vert p_i-q\Vert \ge&\frac{\Vert p_i - p_j\Vert ^2 + \omega _i - \omega _j}{2\Vert p_i-p_j\Vert }. \end{aligned}$$

Using $q \in \partial \widetilde{D}_i$, leads to $\Vert p_i - q\Vert = (c + \omega _i - \frac{1}{n} \sum _{k=1}^n \omega _k)^{1/2}$, which is substituted into the above expression giving the bound on c,

$$\begin{aligned} c \ge&\frac{(\Vert p_i - p_j\Vert ^2 + \omega _i - \omega _j)^2}{4\Vert p_i-p_j\Vert ^2} - \omega _i+ \frac{1}{n} \sum _{k=1}^n \omega _k \text { for all } j. \end{aligned}$$

$\square$

Proof of Proposition 1

The existence of an optimal path from $p_i$ to q passing through $q'$ leads to $J(p_i,q') + J(q',q) = J(p_i,q)$. From $q' \notin \widetilde{V}^{weighted }_{i}$, we have $J(p_i,q') - \omega _i \ge J(p_j,q') - \omega _j$ for some $j \ne i$. Putting these two equations together, along with the triangle inequality $J(p_j,q) \le J(p_j,q') + J(q',q)$ gives

$$\begin{aligned} J(p_i,q') - \omega _i&\ge J(p_j,q') - \omega _j \\ J(p_i,q) - J(q',q) - \omega _i&\ge J(p_j,q) - J(q',q) - \omega _j \\ J(p_i,q) - \omega _i&\ge J(p_j,q) - \omega _j. \end{aligned}$$

which implies that $q \notin \widetilde{V}^{weighted }_{i}$. $\square$

Proof of Theorem 2

Convergence can be proved by showing that $\widetilde{\mathcal {H}}^{centroid }$ decreases monotonically at every step. Recall that the agent positions are updated specifically so that $\widetilde{\mathcal {H}}^{centroid }$ decreases, $\widetilde{\mathcal {H}}^{centroid }(P,\widetilde{\mathcal {V}}^{weighted }(P)) \ge \widetilde{\mathcal {H}}^{centroid }(P^+,\widetilde{\mathcal {V}}^{weighted }(P))$. Next, using (8),

$$\begin{aligned}&\widetilde{\mathcal {H}}^{centroid }(P^+,\widetilde{\mathcal {V}}^{weighted }(P)) \\&\quad \ge \mathcal {H}^{centroid }(P^+,\mathcal {V}^{weighted }(P)) - \epsilon \\&\quad \ge \mathcal {H}^{centroid }(P^+,\mathcal {V}^{weighted }(P^+)) - \epsilon \\&\quad \ge \widetilde{\mathcal {H}}^{centroid }(P^+,\widetilde{\mathcal {V}}^{weighted }(P^+)) - 2\epsilon . \end{aligned}$$

Thus, $\widetilde{\mathcal {H}}^{centroid }$ decreases as long as $\mathcal {H}^{centroid }(P^+,\mathcal {V}^{weighted })(P)$ is $2\epsilon$ larger than $\mathcal {H}^{centroid }(P^+,\mathcal {V}^{weighted }(P^+))$. $\square$

Proof of Theorem 3

Note that Q be compact and invariant under the dynamics T, and define $\mathcal {H}_{v }(P) = \mathcal {H}^{area }(P,\mathcal {V}^{LR }(P,\mathcal {A}(P))$. Because the limited range spatial load balancing algorithm alternately updates the agents’ positions and weight assignments, the evolution of $\mathcal {H}^{area }(P,\mathcal {V}^{LR })$ is,

$$\begin{aligned}&\mathcal {H}_{v }(P) = \mathcal {H}^{area }(P,\mathcal {V}^{LR }(P,\mathcal {A}(P))) \\&\quad = \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(P,\mathcal {A}(P))) \ge \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(T(P),\mathcal {A}(P))) \\&\quad = \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(T(P),\mathcal {A}(T(P)))) = \mathcal {H}_{v }(T(P)), \end{aligned}$$

where $\mathcal {V}^{LR }(P,\omega )$ and $\mathcal {V}^{LR }(T(P),\mathcal {A}(T(P)))$ both satisfy the variable $a'$ constraint. When the partition $\mathcal {V}^{LR }$ is kept constant and the position is updated ($\mathcal {H}^{area }(P,\mathcal {V}^{LR }(P,\mathcal {A}(P))) = \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(P,\mathcal {A}(P)))$), the area covered by $\mathcal {V}^{LR }$ is constant. Because T(P) is found to specifically increase the area, the new sub-partition, $\mathcal {V}^{LR }(T(P),\mathcal {A}(P))$, has a greater area than $\mathcal {V}^{LR }(P,\mathcal {A}(P))$ ($\mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(P,\mathcal {A}(P))) \ge \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(T(P),\mathcal {A}(P)))$). Finally, the $\mathcal {A}(P)$ values are updated in such a way that the area is kept constant during the update ($\mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(T(P),\mathcal {A}(P)))= \mathcal {H}^{area }(T(P),\mathcal {V}^{LR }(T(P),\mathcal {A}(T(P))))$). Theorem 1 says that $\mathcal {A}(T(P))$ exists. Note that if $T(P) \ne P$ then $\mathcal {H}^{area }(P,\mathcal {V}^{LR })$ decreases implying $\mathcal {H}_{v }(P) > \mathcal {H}_{v }(T(P))$. Therefore, $\mathcal {H}_{v }(P) = \mathcal {H}_{v }(T(P))$ if and only if $T(P) = P$. From here, apply the LaSalle invariance principle to guarantee the trajectories of T converge to the largest invariant set in $\mathcal {Z} = \{ P \in Q \, | \, \mathcal {H}_{v }(P) = \mathcal {H}_{v }(T(P)) \}$. It can be concluded from the above discussion that $\mathcal {Z}$ is the set of limited range generalized Voronoi configurations where the gradient of $\mathcal {H}^{area }(P,\mathcal {V}^{LR })$ is zero. $\square$