Failure-Scenario Maker for Rule-Based Agent using Multi-agent Adversarial Reinforcement Learning and its Application to Autonomous Driving

1 Introduction

If the decision-making algorithm in safety-critical applications does not work properly, the resulting failure may be catastrophic. To prevent such results occurring after deployment, we must determine as many failure cases as possible and then improve the algorithm in the development phase [Stanton and Young, 1998]. Autonomous driving and flight algorithms especially must work properly in a multi-agent environment [Urmson et al., 2008; Kim and Shim, 2003], which requires us to craft adversarial situations for the tested algorithm by incorporating the interactions with other agents.

Reinforcement learning (RL) has recently achieved significant results; examples range from robotics manipulation [Levine et al., 2016] to game playing [Mnih et al., 2015; Silver et al., 2016]. However, most of the software in the practical applications are still rule-based because of the explainability or backwards compatibility. This is true with autonomous driving algorithms as well; hence, we need the algorithms to craft adversarial situations for the rule-based algorithm.

As such, it makes sense to train adversarial RL-based agents (i.e., non-player characters, NPCs) such that the agent with the tested rule-based algorithm (i.e., player) fails. By training NPCs in RL frameworks, we create various adversarial situations without specifying the details of the NPCs' behaviors. We focus on the decision-making aspect rather than image recognition; hence, the failure means collisions in most cases. Figure 1 gives a conceptual image of the agents in our research. By training NPCs (red) in an adversarial manner, we aim to obtain the failure cases of the player (blue).

In this problem set, however, we encounter the following four problems. First, pure adversarial training often results in obvious and trivial failure. For example, if multiple NPCs intentionally try to collide with the player, the player will surely fail; however, such failure cases are useless for improving the rule-based algorithm. Second, when the player fails, it is not always clear which NPCs induce the failure. For efficient and stable learning, we should present the adversarial reward only for the NPCs that contribute to the player's failure. Third, the player does not have a notion of reward, and it is often possible to know only whether or not the player fails. That is, from the perspective of the NPCs, the reward for the player's failure is extremely sparse (e.g., if the player fails, NPCs get the adversarial reward of "1"; otherwise, they get "0"). 2 Finally, if the player rarely fails, NPCs are trained using the imbalanced past experience. The imbalanced experience, dominated by the player's success scenarios, prevents NPCs from acquiring a good policy.

2 We have an option to define a virtual reward for the player. However, it is often difficult to precisely define the (virtual) reward.

Contributions

We propose a novel algorithm, FAILMAKER-ADVRL; this approach trains the adversarial RL-based NPCs such that the tested rule-based player fails. In addition, to address the four problems discussed above, we present the following ideas.

Adversarial learning with personal reward. To train NPCs to behave in an adversarial but natural manner, we consider personal reward for NPCs as well as the adversarial reward. This is because we consider that, if it behaves unnaturally, an NPC itself loses the personal reward. When an NPC tries to collide with the player, the personal reward is lost. NPCs should have their own objective (e.g., safely arrive at the goal as early as possible), and we consider the loss of the personal reward to ensure natural behavior.

Contributor identification (CI) and adversarial reward allocation (AdvRA). To identify the NPCs that should be provided with an adversarial reward, we propose contributor identification (CI). This algorithm classifies all the NPCs into several categories depending on their degree of contribution by re-running the simulation with the subsets of NPCs. In addition, to handle sparse (episodic) adversarial reward, we propose adversarial reward allocation (AdvRA), which properly allocates the adversarial reward to the NPCs. This algorithm allocates the sparse adversarial reward among each state and action pair that contributes to the player's failures.

Prioritized sampling by replay buffer partition (PS-RBP). To address the problem caused by imbalanced experience, we partition the replay buffer depending on whether or not the player succeeds, and then train the NPCs using the experience that is independently sampled from the two replay buffers.

We demonstrated the effectiveness of FAILMAKERADVRL with two experiments using both a simple environment and a 3D autonomous driving simulator.

2 RelatedWork

This work is on adversarial multi-agent RL. We review previous work on adversarial learning and multi-agent RL.

Adversarial learning. Adversarial learning can be frequently seen in computer vision tasks. For example, [Szegedy et al., 2013] and [Kurakin et al., 2016] aimed to craft adversarial images that make an image classifier work improperly. In addition, many previous works constructed a more robust classifier by leveraging generated adversarial examples, generative adversarial net (GAN) [Goodfellow et al., 2014] being a representative example of such work.

Multi-agent reinforcement learning (MARL). The relationship among multiple agents can be categorized into cooperative, competitive, and both. Most previous work on MARL addresses cooperative tasks, in which the cumulative reward is maximized as a group [Lauer and Riedmiller, 2000; Panait and Luke, 2005]. In particular, [Foerster et al., 2018] proposed a method with a centralized critic for a fully cooperative multi-agent task. Algorithms on MARL applicable with competitive settings have recently been proposed by [Pinto et al., 2017; Lowe et al., 2017; Li et al., 2019]. [Pinto et al., 2017] consider a two-player zero-sum game in which the protagonist gets a reward r while the adversary gets a reward -r.

In [Lowe et al., 2017], a centralized critic approach called multi-agent deep deterministic policy gradient (MADDPG) is proposed for mixed cooperative and competitive environments; MADDPG is a similar idea as that in [Foerster et al., 2018].

Other related work. Our proposed AdvRA and CI are varieties of credit assignment methods [Devlin et al., 2014; Nguyen et al., 2018]. Most existing methods allocate the proper reward to each agent by utilizing difference reward [Wolpert and Tumer, 2002] under the assumption that all agents are trained by RL. Also, prioritized experiencesampling techniques were previously proposed in [Schaul et al., 2016] and [Horgan et al., 2018]; these techniques enable efficient learning by replaying important experience frequently. For previous work on autonomous driving testing, we refer readers to [Pei et al., 2017] and [Tian et al., 2018]. Many previous studies have addressed test-case-generation problems related to image recognition rather than the decision making, which we address in this work.

3 Background

In this section, we briefly review the standard Markov games and previous studies that underline FAILMAKER-ADVRL. The definitions and notations follow [Lowe et al., 2017].

3.1 Markov Games

Partially observable Markov games are a multi-agent extension of Markov decision processes [Littman, 1994]. A Markov game for N agents is defined by a set of states S meaning all the possible configuration of all agents, a set of actions A1, . . . ,AN, and a set of observations O1, . . . ,ON. Agent i decides the action using a stochastic policy πθi : Oi×Ai → [0, 1], which produces the next state depending on the state transition function T : S×A1×. . .×AN → S. Each agent i obtains the reward of ri : S ×Ai →R in accordance with the state and agents' action and acquires a new observation oi : S → Oi. The initial states are determined by a probabilistic distribution ρ : S → [0, 1]. Each agent i tries to maximize the expected cumulative reward, Ri = ∑Tt=0 γ t rt i , where γ is a discount factor, and T is the time horizon.

3.2 Policy Gradient (PG) and Deterministic Policy Gradient (DPG)

Policy gradient (PG) algorithms are popular in RL tasks. The key idea of PG is to directly optimize the parameters θ of policy π to maximize the expected cumulative reward by calculating the policy's gradient with regard to θ.

Deterministic policy gradient (DPG) algorithms are variants of PG algorithms that extend the PG framework to deterministic policy, µθ : S → A. In the DPG framework, the gradient of the objective function J(θ) = Es∼ρµ[R(s, a)] is written as:

where D is the replay buffer that contains the tuple, (s, a, r, s′ ). Deep deterministic policy gradient (DDPG) approximates the deterministic policy µ and critic Qµ using deep neural networks.

3.3 Multi-Agent Deep Deterministic Policy Gradient (MADDPG)

MADDPG is a variant of DDPG for multi-agent settings in which agents learn a centralized critic on the basis of the observations and actions of all agents [Lowe et al., 2017].

More specifically, consider a game with N agents with policies parameterized by θ = {θ1, . . . , θN}, and let µ = {µ1, . . . ,µN} = {µθ1 , . . . ,µθN } be the set of all agents' policies. Then the gradient of the expected return for agent i ∈ [1, N] with policy µi, J(θi) = E[Ri] is written as:

where a1:N = {a1, . . . , aN}. For example, x is defined as x = (o1, . . . , oN). The replay buffer D contains the tuples (x, x′ , a1:N, r1, . . . , rN), recording the experiences of all agents. The action-value function Qµi is updated as:

where µ′ = {µθ′1 , . . . , µθ′N } is the set of target policies with delayed parameters θ′i .

4 Problem Statement

We consider a multi-agent problem with a rule-based player and single or multiple NPCs. 3 At every time step, the player chooses an action on the basis of the deterministic rule (i.e. tested algorithm). Our objective is to train the NPCs adversarially to create situations in which the player makes a mistake.

We model this problem as a subspecies of multi-agent Markov games. For a player and N NPCs, this game is defined by a set of states S meaning all the possible configuration of agents, a set of actions A0,A1, . . . ,AN, and a set of observations O0,O1, . . . ,ON. In the rest of this paper, the subscript "0" represents variables that are for the player. The player chooses an action on the basis of the deterministic rule µ0, which does not evolve throughout the training of NPCs. 4 Each NPC uses a stochastic policy πθi : Oi ×Ai → [0, 1]. The next state is produced depending on the state transition function T : S×A0×A1×. . .×AN →S. The player does not obtain a reward from the environment but receives a new observation o0 : S → O0. Each NPC i obtains a personal reward as the function ˆ ri : S ×Ai → R in accordance with the state and NPCs' action, and at the same time, receives a new observation oi : S → Oi. The initial states are determined by a probabilistic distribution ρ : S → [0, 1]. The ultimate goal of the NPCs is to make the player fail. At the end of each episode, NPCs obtain the binary information on whether or not the player failed.

5 Method

Algorithm 1 outlines FAILMAKER-ADVRL. At each iteration, the agents execute the actions on the basis of their policy

3 Some of the key ideas in this paper can be employed in problem settings where the player is an RL agent.

4 We assume that µ0 consists of the numerous number of such deterministic rules as "if the signal is red, then stop."

Algorithm 1 FAILMAKER-ADVRL

• 1: for e = 1 toM do
• 2: Initialize a random process N for action exploration; then, obtain the initial state x
• 3: for t = 1 to T do
• 4: The player executes the action a0 on the basis of the rule µ0.
• 5: For the adversarial NPC i, select the action ai = µθi (oi) + Nt
• 6: NPCs execute the actions a = (a1, . . . , aN) and observe their personal reward ˆ r and new state x′
• 7: Store (x, a, ˆ r, x′ ) in temporal replay buffer Dtmp 8: x←x′
• 9: end for
• 10: if the player succeeds then

11:

• 12: rt i ← ˆ rt i

Samples in Dtmp are moved to D+

• 13: else
• 14: After executing CI and AdvRA, the samples in Dtmp are moved to D15: rt i ← ˆ rt i +α · ¯ rt i
• 16: end if
• 17: for NPC i = 1 to N do
• 18: Randomly choose η(e)S samples fromD+ and (1η(e))S samples from D- and create a random minibatch of S samples with PS-RBP
• 19: Update the critic and actor
• 20: end for
• 21: Update the target network parameters for each NPC i
• 22: end for

(Line 2 - 9). If the player succeeds in the episode, the experience is stored in D+. If not, the experience is stored in Dafter identifying the contributing NPCs and allocating the appropriate adversarial reward (Line 10-16). Finally, the NPCs are adversarially trained using the experiences that are independently sampled from D+ and D- (Line 17 - 21). In this section, we first explain three key ideas and then describe the overall algorithm. The detailed pseudocode is given in the supplemental material.

5.1 Adversarial Learning with Personal Reward

When we simply train NPCs in an adversarial manner, they will try to make the player fail in whatever way they can. This often results in unnatural situations in which all NPCs try to collide with the player. Considering real applications, it is essentially useless to obtain such unnatural failure cases.

We obtain the player's failure cases by considering a personal reward for NPCs as well as the adversarial reward. For, we consider unnatural situations to be ones in which NPCs themselves lose a large personal reward. Therefore, we train the NPCs while incentivizing them to maximize the cumulative personal and adversarial reward. Let ˆ rt i and ¯ rt i denote the NPC i's personal and adversarial reward. The reward is written as

where α ∈ R is the scaling factor. In Section 5.2, we will explain how to design the adversarial reward, ¯ rt i .

5.2 Contributors Identification (CI) and Adversarial Reward Allocation (AdvRA)

When the player fails in an episode, the NPCs receive the adversarial reward. How, though, should we reward each NPC? For efficient and stable training, we should reward the state and action pairs that contribute to the player's failure.

Contributors identification (CI). First, to restrict the NPCs that obtain the adversarial reward, we identify the NPCs that contributed to the player's failure. More precisely, for K ∈ N, we classify NPCs into class k contributors (k = 1, 2, . . . ,K). Specifically, class 1 contributors can foil the player alone, and class 2 contributors can foil the player with another class 2 contributor (though they are not class 1 contributors). To identify the class 1 contributors, we re-run the simulation with the player and a single NPC. If the player fails, the NPC is classified as a class 1 contributor. Next, to identify class 2 contributors within the NPCs excluding for the class 1 contributors, we re-run the simulation with the player and two NPCs while seeding the randomness of the simulation. The above steps are continued until we identify the class K contributors. In the rest of the paper, we denote Ck as the set of class k contributors and C as the set of contributors; that is, C = C1 ∪ . . . ∪ CK. When identifying the class k contributors, the number of simulations is NCk; hence, K should be small for a large N. Practically, since traffic accidents are caused by the interaction among a small number of cars, setting small K does not usually affect the practicality.

Adversarial reward allocation (AdvRA). After identifying the contributors, we assign the adversarial reward to each state and action pair. Let g denote the measure of the contribution to the player's failure, which we will call the contribution function. Suppose NPC i∗ is the biggest contributor to the player's failure. The biggest contributor is identified by:

where kmin = min{k ∈ [1,K] | Ck ̸= ∅}. Here, we allocate the adversarial reward to each state and action pair of the NPCs as follows. First, the adversarial reward of "1" is allocated to each state and action pair of NPC i∗ depending on the contribution function g:

The adversarial reward is then allocated to the all contributors, C in accordance with their contributions. For NPC i ∈ Ck, we set

where w(k) ∈ [0, 1] is the monotone non-increasing function with regard to k, which represents the weight between the classes of the contributors. Empirically, to prevent NPCs from obstructing other NPCs, w should not be too small. In our simulation, the contribution function gt i is simply defined using the distance between the player and NPC i; that is,

where β is a positive scalar, and st0 and sti are the positions of the player and NPC i, respectively. Intuitively, this contribution function is based on the consideration that the action inducing the player's failure should be taken when NPC i is close to the player. An alternative would be to define the contributor function using commonly used safety metrics such as headway and time-to-collision [Vogel, 2003].

5.3 Prioritized Sampling by Replay Buffer Partition (PS-RBP)

In the case that the player rarely fails, most of the experiences in the replay buffer are ones in which the player succeeds. As a result, we are required to train adversarial NPCs with imbalanced experiences. To address this problem, we propose PS-RBP. We partition the replay buffer into two parts to separate the experience according to whether or not the player succeeds. During an episode, the experience is temporally stored in Dtmp. After finishing the episode, the experiences in Dtmp are transferred to D+ if the player succeeds and to Dif the player fails. A conceptual image is shown in Figure 2.

Let e denote the episode number. In training the NPCs, we employ η(e) · S samples from D+ and (1 - η(e)) · S samples from D-, where η(e) ∈ [0, 1] is the coefficient between the number of samples from D+ and D-. S is the number of samples employed in the training of the neural network.

5.4 Overview of FAILMAKER-ADVRL

An overall structure of FAILMAKER-ADVRL is shown in Figure 3. As a framework for training multiple agents, we employ the MADDPG algorithm proposed in [Lowe et al., 2017]. As reviewed in Section 3, the MADDPG algorithm is a type of multi-agent PG algorithm that works well in both cooperative and competitive settings. MADDPG is a decentralized-actor-and-centralized-critic approach, which allows the critic to know the observations and policies of all agents. In this paper, we also allow the critic to know the observations and policies of the player and all NPCs. We consider applying FAILMAKER-ADVRL in the development of the player's rule; hence, this assumption is not restrictive.

Suppose that the policies of N NPCs are parameterized by θ = {θ1, . . . , θN}. Also, let µ = {µ1, . . . ,µN} = {µθ1 , . . . , µθN } be the set of all agent policies. The gradient of the expected cumulative reward for NPC i, J(θi) = E[Ri] is written as:

where a0:N = {a0, . . . , aN}. D± represents the replay buffer partitioned into D+ and D-; that is, the experience is sampled from the two replay buffers using PS-RBP. Note that the experiences in D- contains the reward after executing CI and AdvRA.

Using the reward function in (1) characterized by the personal and adversarial reward, the action-value function Qµi is updated for all NPC i as follows:

where µ′ = {µ0,µθ′1 , . . . ,µθ′N } is the set of target policies with delayed parameters θ′i . Practically, we employ a soft update as in θ′i ← τθi +(1-τ)θ′i , where τ is the update rate.

6 Experiments

We present empirical results from two experiments. The first is in a multi-agent particle setting, and the second is in an autonomous driving setting.

6.1 Simple Multi-agent Particle Environment

We first tested FAILMAKER-ADVRL using simple multiagent environments [Mordatch and Abbeel, 2017]. In this simulation, we consider a player and N NPCs with N = 1 and 3. Put simply, the player attempts to approach the goal on the shortest path. The player's goal is set as (0, 0.7). However, when the player gets close to any NPCs, the player acts to maintain its distance from the NPC. In contrast, NPCs get the adversarial reward at the end of the episode if the player collides with another agent or a wall (i.e. a boundary) in at least one time step. At the same time, NPCs receive the personal reward by staying close to the goals. NPCs also try to avoid losing their personal reward; we do this to maintain the NPCs' natural behavior. More specifically, the personal reward decreases when arriving at the goal late or colliding with another agent or wall. For the N = 1 case, the goal of the NPC is set as (0.5, 0). For the N = 3 case, the goals are set as (±0.5, 0) and (0, -0.5).

We implemented FAILMAKER-ADVRL. Our policies are parameterized by a two-layer ReLU multi-layer perceptron with 64 units per layer. In our experiment, we used the Adam optimizer with a learning rate of 0.01. The sizes of D+ and D- are both 1 × 106 , and the batch size is set as 1024 episodes. In addition, the discount factor, γ is set to 0.95. For N = 1 and 3, K is set to K = 1 and 2, respectively. The contribution function g is defined as in (3) with β = 2.0. The weight w in (2) is set as w(k) = 0.9k-1 . In our simulation, through trial and error, η(e) in PS-RBP is set as η = 0.5 for e < 2500 and η = 0.25 otherwise.

Figure 4: Comparing performance in simple multi-agent particle environment with one NPC. The player's failure rate is measured over the previous 100 episodes.

Baselines. We compared FAILMAKER-ADVRL with the following six baselines.

• Good Agent: Good NPCs that maximize their cumulative personal reward (i.e. only ˆ r is considered).
• Attacker: Pure adversaries that maximize the cumulative adversarial reward (i.e. only ¯ r is considered).
• P-Adv: Adversaries with the personal reward.
• P-Adv AdvRA: Adversaries with the personal reward using AdvRA (without PS-RBP and CI).
• P-Adv AdvRA CI: Adversaries with the personal reward using AdvRA and CI (without PS-RBP).
• P-Adv PS-RBP: Adversaries with the personal reward using PS-RBP (without AdvRA and CI).

We used the same parameters as in FAILMAKER-ADVRL for the above baselines. For the baselines without PS-RBP, the size of the replay buffer was 1 × 106 .

Metrics. We used the following as the metrics: 1) the number of the player's failures, and 2) the number of NPCs' failures. The first metric measures the quality of being adversarial, and the second measures the naturalness (i.e. usefulness) of the adversarial situations.

Results. The left half in Table 1 compares the test performance of FAILMAKER-ADVRL and that of the baselines. Each value indicates the percentage of failure in 1000 episodes. For both N = 1 and 3, FAILMAKER-ADVRL outperforms the other baselines except for Attacker in terms of its ability to make the player fail. Attacker has a larger percentage for the player's failure, but this is because Attacker intentionally tries to collide with the player. Figure 4 represents the percentage of the player's failure over the number of episodes. Observe that FAILMAKER-ADVRL and Adversary achieve stable and efficient learning. Also note that P-Adv AdvRA and P-Adv AdvRA CI execute relatively late convergence compared with FAILMAKER-ADVRL.

6.2 Autonomous Driving

We then applied FAILMAKER-ADVRL to the multi-agent autonomous driving problem using Microsoft AirSim [Shah et al., 2017]. We consider a rule-based player and N adversarial RL-based NPCs. We tested for N = 1 and 2. In this simulation, the objective of the NPCs is to make the player cause an accident or arrive at the goal destination very late.

In this simulation, we assumed that the player and NPCs have reference trajectories, which are denoted as Ξi = {ξ1 i , . . . , ξT i }, where ξt i is the reference position and orientation (i.e. yaw angle) at time t for agent i. In our experiment, the reference trajectory is obtained through manual human demonstration. We used the coastline environment in the AirSim simulator, so all the agents drive on a two-lane, one-way road. For simplicity, we assumed that 1) the reference trajectories of all agents are identical (i.e., Ξ0 = . . . = ΞN) and that 2) all agents can observe the true state at every time step.

The player aims to follow the reference trajectory, Ξ0 using PD feedback control. Depending on the difference between the actual state ζ t0 and the reference state ξt0 , the player chooses its own action. Therefore, the player follows the reference trajectory by feed-backing ζ t0 - ξt0 . The player also avoids colliding with NPCs. When the player gets closer to NPCs than a threshold, the player acts to keep its distance from the closest NPC. NPCs act to optimize their personal reward (i.e., ˆ r) and adversarial reward (i.e., ¯ r). The NPCs' personal reward is defined using 1) the distance with the reference trajectory and 2) the velocity. In other words, NPCs are trained to keep to the center of the read and arrive at the destination in a short time. Also, NPCs are trained to behave in an adversarial way on the basis of the adversarial reward.

The FAILMAKER-ADVRL algorithm is implemented as follows. Our policies are parameterized by a three-layer ReLU multi-layer perceptron with 256 units per layer. We used the Adam optimizer with a learning rate of 0.01. The sizes of D+ and D- are both 1×106 , and the batch size is set as 1024 episodes. Also, for the discount factor, γ is set to be 0.95. We used the same baselines and metrics as in Section 6.1 to evaluate FAILMAKER-ADVRL.

Results. The right half in Table 1 compares FAILMAKERADVRL and the baselines. Each value indicates the failure rate of the player and NPCs in 1000 episodes. FAILMAKERADVRL outperforms the other baselines except for Attacker in terms of its ability to make the player fail. Figure 5 shows an example of the simulation results using the 3D autonomous driving simulator. An adversarial NPC successfully induces the player's collision with a rock. Note that the NPC does not collide with the player or any obstacles. A sample video is in the supplemental material.

7 Conclusion and FutureWork

We introduced a MARL problem with a rule-based player and RL-based NPCs. We then presented the FAILMAKERADVRL algorithm, which trains NPCs in an adversarial but natural manner. By using the techniques of CI, AdvRA, and PS-RBP, FAILMAKER-ADVRL efficiently trains adversarial NPCs. We demonstrated the effectiveness of FAILMAKERADVRL through two types of experiments including one using a 3D autonomous driving simulator.

For future work, it will be important to apply our method to more realistic environments that include pedestrians or traffic signs. The first step to accomplishing this would be to craft an adversarial environment (e.g., the shape of the intersection). Also, in this work, we do not consider computer vision aspects. It will be significant to create an integrated adversarial situation while incorporating perception capabilities.

Acknowledgements

We deeply appreciate the anonymous reviewers for helpful and constructive comments.