Decision-Making Policies for Heterogeneous Autonomous Multi-Agent Systems with Safety Constraints

1 Introduction

Autonomous multi-agent systems present many challenges in terms of intelligent decision-making algorithms. A distributed algorithm is often more practical and robust than a centralized algorithm. Agents in a distributed decisionmaking architecture are often self-interested, i.e., they optimize decisions based on local conditions, with limited consideration of global performance and constraints. Therefore, it is challenging to achieve certain global objectives in a distributed multi-agent system. Here we study a particular type of global constraint: safety density/capacity constraints, i.e., the expected number of agents in each state must not violate a prescribed upper bound given for that state. Such a global objective challenges traditional algorithms based on Markov Decision Process (MDP) models, such as reinforcement learning (RL) methods. When some states have high reward but low capacity, self-interested agents are likely to violate capacity constraints by cluttering in these states. The distributed decision-making algorithm should avoid such violations without leveraging on a complex inter-agent communication infrastructure, which is the main challenge addressed here.

We first introduce the Safety Constrained MDP (SC-MDP) problem [Arapostathis et al., 2003; Acikmese et al., 2015; El Chamie et al., 2016] and extend the problem formulation from a single agent case to a heterogeneous multi-agent system case, which is the main contribution of this paper. We propose several algorithms that provide safe decision-making policies to ensure the satisfaction of global safety constraints while maximizing the performance of the overall system. Our second contribution is the successful demonstration of the proposed algorithms for decision-making on a well-known Dynamic Traffic Assignment (DTA) problem [Peeta and Ziliaskopoulos, 2001; Hausknecht et al., 2011]. These decisionmaking algorithms have the following features: 1). The resulting decision-making policies can be implemented in a fully distributed manner and do not require a centralized controller. 2). Communicating/broadcasting each agent's state is not required but can be used as feedback to enhance performance. 3). The resulting safe decision-making policy is randomized and non-stationary. Randomization is the key to remove centralization and communication: agents do not negotiate about whether to transition to a state or not, but rather make statistically independent decisions. The overall system can collectively achieve the desired prescribed behavior. 4). The policy is the same for each agent. Randomization hence also ensures fairness: no agent has higher priority. 5). Decision-making policies can be obtained via solving Linear Programming (LP) problems, and policy synthesis is therefore numerically tractable.

2 RelatedWork

Constraints in MDPs have been utilized to handle multiple objectives, where policies are computed to maximize one of the objectives while guaranteeing that the other objective values lie within a desired range [Altman, 1999]. Hard constraints can also be imposed by the underlying physical environment (the process model) [Arapostathis et al., 2003; Hsu et al., 2006; Demir et al., 2014; Acikmese et al., 2015], which must be explicitly accounted for in decision policy synthesis. Unlike unconstrained cases, the constraints in MDPs usually cause the optimal policies to be randomized rather than deterministic policies [Nain and Ross, 1986; Altman and Shwartz, 1991]. Some recent applications of constrained MDPs include path planning for robotics [Feyzabadi and Carpin, 2014], flight control [Balachandran and Atkins, 2015], and chance-constrained optimal control [Ono et al., 2013; Blackmore et al., 2010]. [El Chamie et al., 2016] presents an SC-MDP algorithm to address a general class of safety constraints on the state probability density function (pdf ). This approach guarantees the satisfaction of safety constraints not only asymptotically but also during the transition to the steady-state, which classical approaches that are based on state-action frequencies [Altman, 1999] fail to guarantee.

An important application of the SC-MDP algorithm is to the Dynamic Traffic Assignment (DTA) problem [Peeta and Ziliaskopoulos, 2001], which we choose as our example problem to demonstrate the effectiveness of the proposed algorithms. Earlier research utilizing Markov processes in modeling traffic density evolution and optimal assignment include [Hazelton and Watling, 2004; Watling and Cantarella, 2015]. A survey of using multi-agent reinforcement learning in traffic control can be found at [Bazzan, 2009]. DTA is chosen as the key example problem because it is a real-world problem with many challenging constraints and objectives.

3 Method

3.1 Preliminaries

Consider a finite-horizon MDP for a single agent, defined by the tuple ¶H↪ S↪ A↪ ⌧a↪ Rt↪ γ♦, where

• ÷ H = ¶0↪ · · · ↪ T♦↪ T 2 N is the time horizon. t 2 H is called a time step.
• ÷ S = ¶1↪ · · · ↪ n♦↪ st 2 S is the state at time step t.
• ÷ A = ¶1↪ · · · ↪ p♦↪ at 2 A is the action at time step t.
• ÷ Rt 2 Rn⇥p is the reward matrix at t. Rt(s↪ a) denotes the immediate reward of taking action a in state s at time t. RT 2 Rn is the terminal reward vector with RT (s) being the terminal reward for s.
• ÷ ⌧a 2 Rn⇥n is the transition matrix for action a, ⌧a(s0 ↪ s) = P(st+1 = s0 ♣st = s↪ at = a).
• ÷ γ 2 (0↪ 1] is the discount factor.

We now introduce several key concepts to define the SCMDP problem. Let xt 2 Rn denote the state probability density distribution function (pdf ) at t, where xt(s) denotes the probability of finding the agent in s at t, i.e., xt(s) = P(st = s). Let Mt 2 Rn⇥n be the Markov chain (MC) transition matrix at t, where:

A non-stationary policy for finite Horizon MDP is defined as a sequence of randomized policy matrices ⇡0:T-1 := ¶⇡0↪ · · · ↪ ⇡T-1♦, ⇡t 2 Rn⇥p , where ⇡t(s↪ a) = P(at = a♣st = s). Let ⇧ be the set of all admissible policy sequences, i.e., ⇧ = ¶⇡0:T-1♣⇡t1 = 1↪ ⇡t ≥ 0♦ where 1 is the vector of all ones and ≥ is an element-wise inequality.

Let ¯rt(s) = E[rt(s↪ at)] = Pa2A ⇡t(s↪ a)Rt(s↪ a) be the expected immediate reward of s at t given a policy ⇡t. For t = T , let ¯rT = RT .

Let

where Ut(s) denotes the value of s at t under policy ⇡t:T-1, i.e., expected accumulated discounted rewards from t to T under policy ¶⇡t↪ · · · ↪ ⇡T-1♦ with st = s.

For a given policy ⇡0:T-1, the random process induced by the state of the system at different time steps: ¶s0↪ s1↪ ▷ ▷ ▷ ↪ sT♦ is a discrete-time Markov chain (DTMC) whose state space is S. The state pdf evolves according to the MC transition matrix

Note that Mt is a linear function of ⇡t as shown in (1).

Performance Metric

We use the expected accumulated discounted rewards as the performance metric for a given policy, at time-step t:

denotes the expected accumulated discounted rewards from t to T under policy ¶⇡t↪ · · · ↪ ⇡T-1♦ where xt is the state pdf at t. Naturally, the performance metric to evaluate ¶⇡0↪ · · · ↪ ⇡T-1♦ is v⇡0:T-1 0 (x0). Using the linearity of the expectation operator, (4) becomes:

3.2 Safety ConstrainedMDP Problem

The unconstrained MDP optimal policy ⇡⇤ is the policy that maximizes the performance metric.

⇡⇤ can be solved using backward induction algorithm [Puterman, 1994, p. 92]. Now, we introduce Safety Constrained MDP (SC-MDP) [El Chamie et al., 2016], which is an MDP with the safety constraints:

where  denotes the element-wise inequalities, and d 2 [0↪ 1]n is a vector giving upper bounds on the system state pdf. We assume d is independent of t. Intuitively, at any given t, d constrains the probability of finding a single agent in each state. Later we will show that for a multi-agent system, d constrains the density of agents in each state.

To solve the SC-MDP policy is equivalent to solving the following constrained optimization problem:

Note that according to (3), xt = Mt-1 ▷ ▷ ▷M1M0x0, hence although each Mi is linear in the decision variables ⇡i, constraints (6) are non-convex in general. Also directly applying Dynamic Programming (DP) will not help in this case: if we try to apply forward induction, i.e., for t = 0↪ · · · ↪ T - 1

Then at t-th iteration, according to (2), Ut is unknown since it depends on ¶⇡t↪ · · · ↪ ⇡T-1♦. Similarly, according to (3), xt is unknown at t-th iteration of backward induction.

3.3 Multi-Agent System

The constraints in (6) give upper bounds on the probability distribution of a single agent. We now extend the single-agent results [El Chamie et al., 2016] to a multi-agent system using the law of large numbers. We will show that having bounds on the probability distribution of being in a state induces bounds on the expected number of agents in that particular state.

Assume now that N agents are operating in the same environment, i.e., each agent uses the same motion decision policy obtained by solving the MDP. The probability distribution of agent k at t, given by x(k) t , has the following interpretation: x(k) t (s) represents the probability of finding the agent k in s at t. Since all N agents have identical MDP, 1 then PNk=1 x(k) t (s) describes the expected number of agents in s at t. Let ct = [ct(1)↪ ▷▷▷↪ ct(n)]| denote the actual number of agents in each state. Then, ct(s) is generally different from PNk=1 x(k) t (s), although it follows from the i.i.d. agent realizations that

and from the law of large numbers we will show next that that ct◁N ! xt as N !1↪ 8t 2 H where x0 = PNk=1 x(k) 0 ◁N and xt follows the dynamics of the n-dimensional system (3).

The idea behind extending the probabilistic guidance of a single agent to multi-agents using the law of large numbers is to control the propagation of the probability vector, xt, rather than each individual agent's position. While, in general, ct◁N 6=xt, it will always be equal on average, and can be made arbitrarily close to xt by making the number of agents N sufficiently large [Demir et al., 2015].

Consider a multi-agent system comprised of N agents. Suppose that each agent has the following probability distribution over a given domain at t:

Then the following result holds.

Proposition 1. Consider a multi-agent system of N agents such that x0 := PNk=1 x(k) 0 N at time t = 0. Further, suppose that each agent acts independently such that x(k) t+1 = Mt(⇡t)x(k) t ↪ k = 1↪ ▷▷▷↪N↪ where Mt(⇡t) is a column stochastic Markov matrix and it is defined by the same policy ⇡t for all agents. Then xt+1 = Mtxt↪ t = 0↪ 1↪ 2↪ ▷▷▷↪ and where ct is the vector of number of agents in each state at t.

1 We later introduce heterogeneous agents where agents can have different transition and reward functions.

Proof. Next, consider xt(i) which is the probability of finding any agent in state i at time t. Consider a new Random Variable (RV), Z (k) t (i), such that Z (k) t (i) = 1 if agent k is in i at t (i.e., if X(k) t = i), and zero otherwise. Clearly, E[Z (k) t (i)] = x(k) t (i), where E is the expectation operator and Z (k) t (i)↪ k = 1↪ ▷▷▷↪N↪ form i.i.d. RVs. Then it follows that ct(i) = Z (1) t (i) + · · · + Z N t (i). Note that xt(i) = E[PNk=1 Z (k) t (i)◁N], and since Z (k) t (i)↪ k = 1↪ ▷▷▷↪N are i.i.d. RVs and E[♣Z (k) t (i)♣] <1, we can use the strong LLN theorem, [Chung, 2001, Theorem 5.4.2], to conclude that:

which then gives the desired result.

This result shows that when all agents evolve independently according to an identical MC transition matrix, the ensemble of agent positions has a distribution that approaches xt with probability one as N increases, which makes constraints on xt constrain agent density asymptotically. Hence results for a single agent in [El Chamie et al., 2016] can be applied to a multi-agent system. We refer solving a multi-agent SC-MDP policy as a policy synthesis problem.

3.4 Multi-Agent Policy Synthesis Algorithms

First, we define the following two sets:

where M(⇡) is defined as in (1). We refer to X as the safe density set, and to C(X) as the safe policy set for X.

Note that C(x) is a convex set of policies because M(⇡) is linear in ⇡, and C(X) is also convex since it is the intersection of convex sets. The convexity of these sets allows them to be characterized by linear constraints.

As discussed before, DP is not directly applicable to SCMDP: neither forward induction nor backward induction will work because either the value of Ut or xt is undetermined at t-th iteration. To resolve this dilemma, we develop heuristics that either provide an estimate of Ut to be used for forward induction or an estimate of xt to be used for backward induction: Algorithm 1 uses forward induction by estimating Ut with the corresponding value function Vt of unconstrained MDP. It is based on the assumption that x0 is known. Algorithm 2 [El Chamie et al., 2016] uses backward induction by considering worst case xt from safe density set X that minimizes x|t Ut but remains in safe density set X. It does not require knowing x0 itself, but assumes x0 2 X. In this way, it only seeks policies in C(X). Algorithm 3 improves Algorithm 2 via a projection technique, which finds the closest policy to the optimal policy of unconstrained MDP among the safe policies obtained from Algorithm 2. We use the Frobenius norm as a distance measure, but other norms produce similar results. Algorithm 4 improves over Algorithm 2 when x0 is given via both forward induction and backward induction by providing estimates to Ut and xt in succession. All these algorithms are based on LP and can be implemented using any standard LP solvers. A comparison of these algorithms is shown in Table 1.

X ⇡t 2 C(X)

Table 1: Algorithm assumptions and policy properties.

3.5 Heterogeneous Agents

The single class multi-agent model can be extended to a heterogeneous multi-agent system where agents can be categorized into l different classes. Agents' transition model, reward function, and optimal policies remain homogeneous within the same class but heterogeneous in different classes. An example of heterogeneity in DTA is when different size of vehicles contribute differently in traffic congestion. Note that all these heterogeneities can be addressed by simply extending the state space S. However, safety constraints (6) are usually imposed on the common environment shared by all agents and not on the extended state space S. We can handle this heterogeneity using a linear operator L 2 Rm⇥n where ml = n that maps the agent state space S to an environment state space where safety upper bounds are imposed. Then (6) can be generalized to:

The algorithms can still be implemented by a slightly modified LP with constraints (13) as they are still linear in xt.

Algorithm 1 SC-Forward Induction (SCF)

• 1: Let VT = ¯rT , for t = T - 1↪ · · · ↪ 1↪ 8s 2 S,

• 2: Given x0, for t = 0↪ · · · ↪ T - 1, compute policy and distribution at next time step

Algorithm 2 SC-Worst Case (SCWC)

and

Usually ˆ⇡t obtained from step 2 is not unique, let ˜ Ct(X ) denote the corresponding set of policies.

Algorithm 3 SC-Projection (SCPRO)

• 1: Run Algorithm 2 to get ˜ C(X )t↪ 8t 2 H ∩ ¶T ♦

• 2: Let VT = ¯rT , for t = T -1↪ · · · ↪ 0, compute the optimal policy for unconstrained MDP: 8s 2 S

Algorithm 4 SC-Backward-Forward Induction (SCBF)

• 1: Run Algorithm 2 to get an initial safe policy {⇡0 0 ↪ · · · ↪ ⇡0T-1
• 2: Let ˆ⇡t = ⇡0 t 8t 2 H∩ ¶T♦
• 3: Forward Induction: Given x0, for t = 0↪ · · · ↪ T - 1, compute xt+1 based on xt and ˆ⇡t

• 4: Backward Induction:

Let UT = ¯rT , for t = T - 1↪ · · · ↪ 0, re-compute the policy based on Ut+1 and xt,

• 5: Repeat steps 3 and 4 until ¶ˆ⇡0↪ · · · ↪ ˆ⇡T-1♦ converges.

4 Experiments and Results

4.1 Resource Collection

We first evaluate the algorithms using a simple 11-state MDP, as shown in Fig. 1. 100 agents are placed at home state initially. The other ten states each provides different amount of reward at every time step, with different capacity upper bound. If more agents than the upper bound capacity enter a state, the extra ones will not receive reward. The agents can stay or move from any state to any other state. An action succeeds with probability ▷75, and failure causes the agent to stay. Let C(si) denote the capacity upper bound of state si. Its density upper bound is di = min¶C(si)◁N↪ 1♦. We set γ = 0▷99.

Results We evaluate the safety and optimality performance. Safety is measured by the total number of times that an agent violates capacity upper bound. Optimality is measured by the total reward accumulated. The results are shown in Fig. 2. Comparison algorithms are centralized, random, safe, and greedy. The centralized algorithm starts from the state with the highest reward and allocates maximum number of agents that state allows, then moves to the state with second highest reward, etc. The random agents choose an action uniformly at random. The greedy agents choose a state with probability proportional to the state's reward. The safe agents choose a state with probability proportional to the state's density upper bound.

Overall, in terms of reward, SCBF and SCF perform closely to centralized algorithm. SCPRO and SCWC algorithms are conservative and results in collecting less reward, but they still perform better than or comparable to greedy, random, and safe algorithms. In terms of violation, all SC algorithms have significantly less violations comparing to random and greedy algorithms. SCWC algorithm resulted in the fewest violation count. Additional experiments were performed on other randomly generated density vectors and the conclusions are similar.

This experiment demonstrates one motivation of SC algorithms: it is not always trivial to achieve optimality while maintaining safety in distributed systems. SC algorithms balance optimality and safety better than the baseline distributed algorithms, and have close performance to the optimal centralized algorithm.

4.2 Dynamic Traffic Assignment

We apply our algorithm to a dynamic traffic assignment (DTA) problem in a multi-intersection environment

[Hausknecht et al., 2011] as shown in Fig. 3. The task is to direct agents (vehicles) to roads and intersections that have low usage to reduce congestion, while ensuring that all agents arrive at their destinations. For simplicity, all roads are twoway, and U-turns are allowed in all states. One-way roads and traffic rules can be introduced by changing the transition function of the MDP. The roads have different carrying capacities. Violating the capacity upper bound results in congestion modeled by the fundamental diagram [Greenshields et al., 1935]. The diagram maps the current traffic level to the average speed. This effect is simulated by the transition function in the MDP. Agents have two sizes: a large agent occupies ↵1 = 3 units of capacity, and a small one occupies ↵2 = 1 unit.

We discretized the state space as in Fig. 3, and implemented a discretized version of the Automatic Intersection Manager simulator [Dresner and Stone, 2008]. Note that a two-way road block is a single state, rather than two states for each direction, since [Hausknecht et al., 2011] introduces dynamic lane reversal hence a block's carrying capacity can be shared for both directions. Let N denote the total number of agents. The problem MDP with γ = 0▷99 is defined as:

• ÷ S: a state is a tuple hposition↪ destination↪ typei. position indicates the current position. type indicates whether an agent is large or small. destination is included to better define the reward function.
• ÷ A: ¶North, South, East, West, Stay♦.

• ÷ ⌧: we use the transition function to simulate the speed change according to the fundamental diagram. The slower the speed, the higher the probability that an agent will stay when trying to move from state s to s0 :
• ÷ R: an agent receives a reward of +1 at the state in which its position equals to destination. As mentioned before, this definition is to allow agents with different objectives to share a single MDP and reward function.
• ÷ L = [ ↵1I · · · ↵kI ], where I 2 Rn⇥n is the identity matrix, ↵i 2 R is the size for i-th type of agents.

At the beginning of the simulation, all agents broadcast their locations and destinations, hence each agent can define its SC-MDP problem and calculate the policy.

Results We compare SC algorithms with a shortest path (STP) and a Time-based A* (TB-A*) algorithm [Hausknecht et al., 2011]. An STP agent chooses the shortest path (break tie randomly), without considering other agents. The TB-A* agent estimates its expected shortest-time path given the traffic of every state (hence transition probability). TB-A* requires observation and path re-planning at every time step.

We test two maps. The first one has 6 roads and 9 intersections (Fig. 3). The capacity upper bound for each block is 500. We simulate one traffic flow: agents travel from the upper left corner to the lower right corner. Half of the agents are large agents and the other half are small. The planning horizon for SC algorithms is 50 time steps.

The results are shown in Fig. 4. The leftmost figure shows percentage of total capacities arrived over time steps. 1500 large and 1500 small agents (6000 total capacity) are placed at the starting state. All SCF agents quickly arrive at their destination, while SCBF, SCPRO agents arrive slower but still faster than STP and TB-A*. In runtime simulations, we observe that SC agents wait nicely in line to move through bottlenecks, without a centralized controller nor explicit coordination.

In the middle figure, we show the capacity arrived in 50 time steps while varying the total capacity. When the total capacity is low (< 7500), all algorithms except SCWC can ensure all agents arrive at their destination within 50 time steps. When total capacity is increased, STP and TB-A* suffer from congestion and only few agents arrived. SCF and SCBF both perform well. SCF has larger variance, because SCF agents move faster but are more likely to cause congestion due to their more aggressive randomized policy.

The second map is larger with 8 roads and 16 intersections. We simulate four traffic flows: a quarter of the agents start at each corner and travel to the diagonal corner. Road capacities are sampled from [800↪ 1200]. Results are shown by the rightmost plot in Fig. 4. The performance of SCPRO degrades to be the same as SCWC. Although SCBF and SCF still perform better than STP and TB-A*, the SCF policy is risky and leads to congestion, since it always pushes maximum number of agents towards their destinations. This is problematic with multiple traffic flows. The problem is alleviated by lowering the actual density upper bound in Algorithm 1, namely multiplying the actual bound by a β factor. The resulting policy is less likely to cause congestion, as indicated by the top red curve. When varying total capacity, the result is similar to the one of the small map: SCF and SCBF significantly outperform STP and TB-A* when total capacity grows large.

5 Conclusion and FutureWork

We extend the previous SC-MDP framework [El Chamie et al., 2016] to a distributed heterogeneous multi-agent system, where one aims to bound the agent density over a finite horizon. We develop three novel algorithms (SCPRO, SCBF, and SCF) that improve the performance of the original algorithm (SCWC). SCF and SCBF produce the best results in terms of safety and optimality, since additional information (initial distribution of agents) is available. However, since the guarantee is probabilistic, one might consider to be conservative (more safe), i.e., use SCBF or lower the β factor in SCF.

An alternative approach for multi-agent density control could be multi-agent reinforcement learning [Hu et al., 1998]. One can modify the reward function to achieve global objectives, such as taxation or toll [Bnaya et al., 2013; Xiao et al., 2014]. By assigning penalty to the congested states, vehicles can recalculate their policy using the updated reward function. However, it is non-trivial to determine the magnitude of the penalty, especially with rewards for reaching the destination. SC-MDP framework's advantage is that it defines a constrained optimization problem, hence clearly separating the constraints from the optimization objective.

An extension of our algorithm is to enforce a lower bound on agent density as well, i.e., d  Lxt  ¯d. Notice this can also be written in the form of (13) with proper choice of L. These extensions may be applied to multi-agent problems such as surveillance.

Although the algorithms assume an open-loop policy after the first episode, they can also observe the actual agent distribution xt at every episode or every several episodes. The agents can treat xt as a new x0 and recalculate their policies. This requires global observation but not explicit coordination.

Acknowledgments

We would like to thank Peter Stone for helpful comments and suggestions. This research was supported in part by Defense Advanced Research Projects Agency (DARPA) Grant No. D14AP00084 and the National Science Foundation (NSF) under Grant No. CNS-1624328.