{'fraction_non_alphanumeric': 0.04541755473745398, 'fraction_numerical': 0.0074791707033520635, 'mean_word_length': 4.2091239402503025, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
How Shall I Drive? Interaction Modeling and Motion Planning towards Empathetic and Socially-Graceful Driving

While intelligence of autonomous vehicles (AVs) has significantly advanced in recent years, accidents involving AVs suggest that these autonomous systems lack gracefulness in driving when interacting with human drivers. In the setting of a two-player game, we propose model predictive control based on social gracefulness, which is measured by the discrepancy between the actions taken by the AV and those that could have been taken in favor of the human driver. We define social awareness as the ability of an agent to infer such favorable actions based on knowledge about the other agent's intent, and further show that empathy, i.e., the ability to understand others' intent by simultaneously inferring others' understanding of the agent's self intent, is critical to successful intent inference. Lastly, through an intersection case, we show that the proposed gracefulness objective allows an AV to learn more sophisticated behavior, such as passive-aggressive motions that gently force the other agent to yield.


I. INTRODUCTION
While intelligence of autonomous vehicles (AVs) has significantly advanced in recent years, accidents involving AVs suggested that these autonomous systems lack gracefulness in driving. In one incident, Waymo reported that its AV (denoted by "M" hereafter) was stuck at an intersection because human drivers (denoted by "H") coming from the other road never stopped fully while approaching the intersection, making M believe that H wanted the right of way and causing it to stop indefinitely [1]. The first claim against an AV manufacturer has been filed against General Motors in 2018, following a collision between a Cruise Automation 2016 Chevrolet Bolt and a motorcyclist, who alleged that the car swerved into his path without his agreement [2].
Both incidents can be attributed to M's lack of understanding of H's intent and thus its failure to predict H's future motion. In interactions that involve both agents as decision makers, M's inference of H's intent depends on not only observations from H, but also knowledge about H's understanding of M. In other words, M needs to be empathetic in order to understand what leads to H's behavior. To elaborate, consider that an agent's intent is defined as parameters of its control objective. The interaction between M and H from the perspective of M can be modeled as Building upon this, this paper further introduces a motion planning strategy that incorporates social gracefulness, which is defined as the discrepancy between the actions taken by M and those that could have been taken in favor of H. Take the intersection case in Fig. 1 for example. When H moves slowly, an empathetic M knows that he is expected to take the right of way. A socially-aware M, in addition, knows that himself driving slowly to allow H to pass would do H a favor. Note that to acquire social awareness, M would need to understand H's intent, and thus be empathetic in the first place. We will show that considering the gracefulness objective in planning allows M to learn more sophisticated behavior, such as passive aggressive motions that gently force H to yield.
The technical approaches of the paper can be summarized in two steps: In Sec. III, we formulate the intent inference problem where the intents of both agents are jointly inferred, based on the assumption that the both agents model each other to adopt a baseline planning strategy where the agent plans motions based on the set of Nash equilibria of the game perceived by the others. In Sec. IV, we explore more sophisticated planning strategies enabled by the inferred Fig. 2. Summary of the intent inference and motion planning algorithms of M. To perform intent inference, M needs to model H's motion planning hypothetically. The highlighted modeling elements include (1) the game-theoretic intent inference algorithm that enables empathy, (2) the incorporation of inference uncertainty in motion planning, and (3) more sophisticated motion planning objectives enabled by intent inference.
intents, and evaluate how these strategies influence the actual social gracefulness and social efficiency of an interaction between H and M. Three driving strategies will be explored: (1) A reactive M plans based on the inferred distribution of future motions of H. (2) A proactive M exploits the fact that H's future motion are dependent on M's. (3) A socially-aware M is built upon the proactive model, with the additional gracefulness loss. The proposed intent inference and motion planning models are summarized in Fig. 2.
The intellectual contributions of this paper are two-fold: First, we propose mechanistic intent inference and motion planning algorithms for two-agent interactions. Our approach is different from existing studies where the control policy or objective of either M or H is learned offline through data. The introduction of empathy was previously discussed in Liu et al. [12]. This idea is extended to non-collaborative scenarios with non-quadratic control objectives. Second, we introduce the definition of social gracefulness as a performance measure for human-machine interactions. The idea of measuring risk through the difference between the driver's actions and what he is expected to do according to traffic rules was introduced in [7]. We take a parallel approach by defining the nominal actions as shaped by others' intents (i.e., tacit social norms), rather than by explicit traffic rules.
II. RELATED WORK AV has been an active and fast developing research topic in the past few years. Scenarios such as lane changing, lane merging, and traffic intersections, where AVs closely interact with human-driving vehicles, are widely investigated [11], [21], [8]. Human drivers are often modeled as rational and intelligent decision makers in these studies. Pentland and Liu proposed a dynamic Markov models to recognize and predict human driving actions [15]. Levine et al. adopted an inverse reinforcement learning method to explore human drivers' reward functions based on human demonstration recorded through a driving simulator [9]. Machine learning is used to predict the lateral motions and braking actions of human driver [19], [14], [17]. These data-driven approaches require a large amount of data for model training. Wang et al. discussed the appropriate amount of data to achieve sufficient understanding of human driving behavior [18].
Based on proper human driver models, an essential question remains as how to achieve safe and efficient humanmachine interactions. Nikolaidis et al. [13] proposed a mutual adaptation algorithm where human's willingness to adapt is inferred and incorporated into the robot's motion planning. In a similar two-agent collaborative setting, Liu et al. [12] proposed a "Blame-all strategy" for intent inference. Much like this paper, "Blame-all" performs inference of others' intents by taking into account others' inference of the agent's intent, with the limited scope of quadratic control objectives. For dynamically changing agent parameters (such as intents), Foerster et al. [5] proposed Learning with Opponent-Learning Awareness (LOLA), a method for agents to incorporate the anticipated learning of other agents during its own adaptation (similar to [16] and the proactive vs. reactive case of this paper). LOLA, however, had limited discussion on scenarios where opponent parameters and parameter tuning schemes need to be inferred in a higher level game (e.g., proactive vs. proactive as in this paper). Specific to AVs, various game theoretic models have been constructed to describe different interactions between human drivers and AVs [20], [3]. In a setting of partially observable Markov decision process, Li et al. introduced a "Level-k" reasoning model to evolve the strategies that agents adopt in driving interactions [10]. Nonetheless, their solution requires an iterative search through reinforcement learning. In contrast, mechanistic models (e.g., [12], [13] and this paper) are oneshot and are more suitable for scenarios where agents are required to learn and adapt in real time.

III. INTENT INFERENCE
This section introduces the motion planning game and the inverse problem of intent inference. For simplicity, we focus on an interaction between two agents, M and H. The extension to multi-agent settings will be left as future work. The inference by M is based on the assumptions that H uses a baseline motion planning strategy (see Sec. III-B), and that H believes that M uses the same strategy.

A. The motion planning game
Let s i (t) and u i (t) be the state and action at time t, with the subscript i ∈ {H, M } specifying the agent. We consider deterministic state transition: s(t) = s(t − 1) + u(t − 1), and define i's planned motion at t as a sequence of actions where T is a predefined finite time horizon. The dependency on t will be omitted for brevity. The planning game is formulated as follows: The instantaneous loss of agent i is (1) where l safety measures the safety loss, l task the fulfillment of a task, e.g., "lane changing" or "crossing the intersection" (see Sec. V), and the intent parameter c i governs the behavior of the vehicle. Note that l safety involves the distance between i and j, and thus requires ξ i , ξ j , s i , and s j as inputs. The dependency on s i and s j will be omitted for brevity. The payoff for i in the game is defined as the accumulative loss for ξ i that satisfies g i (ξ i ) ≤ 0, which represents boundaries on future states. For infeasible ξ i , f = ∞. Each agent chooses its motion from a finite candidate set Ξ i . Under this setting, the game is guaranteed to have at least one Nash equilibrium (Theorem 23 in [6]). Denoteĉ j as i's estimation of j's intent (see Sec. III-C for the inference ofĉ j ). The game at time t yields a Nash For example, at an intersection without a stop sign, either M or H yielding to the other will satisfy Eq. (3) when both M and H are non-aggressive (i.e., with small c). It is important to note that for i to understand j, i needs to put himself in the shoes of j and derive the equilibrium set from j's perspective. Since j does not know c i , a necessary correction is to replace c i withc i , i.e., i's estimation of j's estimation of i's intent, and similarly, ξ * i withξ * i .

B. The baseline driving strategy
Agent i is modeled to believe that j plans its motion at t by sampling uniformly from Q(c i ,ĉ j , t), i.e., j's motion follows the probability mass function:

C. Inference of intent and motion
Eq. (4) formulates the inference problem where we estimate the intents (c i andĉ j ) and the planned motions (ξ * i and ξ * j ) at time t based on the states and actions of i and j at t−1.
The idea is that the estimated intents should be such that j's planned motion at t − 1 with the highest probability mass (denoted byξ † j (t − 1)) should have its first action (denoted byû † j (t − 1)) matching the observed action of j at t − 1 (u j (t − 1)), or verbally, what j should have done should match with what it actually did. miñ We use a finite intent set C for both agents to represent different levels of aggressiveness in driving. Since both C and Ξ i,j are finite, the inference is done through an enumeration over the solution space C × C. The outcome of the enumeration is a set S(t) = (c * i ,ĉ * j ) k K k=1 , where each element is a global solution to Eq. (4). To quantify the uncertainty in inference and later incorporate it into motion planning, we assign equal probability mass (1/K) to each solution, based on which we can compute the empirical joint distribution p(c i ,ĉ j ; t) and the marginals p(c i ; t) and p(ĉ j ; t), by counting the appearances of all elements of C in S(t). From the joint distribution p(c i ,ĉ j ; t), we can infer j's planned motion. From each (c * i ,ĉ * j ) ∈ S(t) we can compute a conditional distribution of j's motion starting from t − 1, denoted by p(ξ j ;c * ,ĉ * j , t − 1), through Q(c * i ,ĉ * j , t − 1). We can then calculate the marginal p(ξ j ; t − 1) using p(ξ j ;c * ,ĉ * j , t − 1) and p(c i ,ĉ j ; t − 1). Note that this is the distribution of j's motion at t−1 rather than t since we formulated the game at t − 1. Although one can formulate a new game at t to derive p(ξ j ; t), in this paper we will approximate p(ξ j ; t) using p(ξ j ; t−1). Similarly, we can also infer i's planned motion as expected by j, denoted by p(ξ i ; t). We shall emphasize that p(ξ i ; t) is not the distribution of motion that i will follow, rather, it represents i's awareness of what j expects it to do.

D. Leveraging past observations
Note that if we consider c j to be time invariant during the interaction, then all previous observations can be leveraged to infer c j , leading to a modified problem: We allowc i to freely change along time since j may change its mind about i. Solutions to Eq. (5), denoted byS(t), can be found in a recursive way based on solutions to Eq. (4).
Consider an intent candidateĉ j that exists in bothS(t − 1) and S(t). Let solutions inS(t − 1) that containĉ j be in the form of (a,ĉ j ), where a = [a 1 , · · · , a t−1 ] ∈ A ⊂ C t−1 is an array of intents of i. Similarly, let solutions in S(t) that containĉ j be in the form of (b,ĉ j ), where b ∈ B is an intent of i. Also denote the operation of appending element b to the array a as [a, b]. Then ([a, b],ĉ j ) for all a ∈ A and b ∈ B is a solution to Eq. (5) at t. Following this property, we havep(ĉ j ; t) ∝p(ĉ j ; t−1)p(ĉ j ; t). The update ofp(ĉ j ; t) will trigger that of the joint probability p(c i ,ĉ j ; t) and the marginal p(ξ j ; t). Their updated counterparts are denoted bȳ p(c i ,ĉ j ; t) andp(ξ j ; t), respectively.
IV. MOTION PLANNING We introduce three planning strategies that incorporate the inferred intents and motions. Note that in this paper, agents are only modeled to infer others' intents rather than their planning strategies, i.e., they are assumed to use the baseline strategy but may in fact use different ones (see Fig. 2). Potential formulations of higher-level inference algorithms will be discussed in Sec. VI.

A. Reactive motion
Given the distribution of j's future motionsp(ξ j ; t), a reactive agent plans its motion by minimizing the expected loss within a time window: min

B. Proactive motion
A proactive agent i plans by taking into consideration the dependency of j's planning on i's next action. Specifically, i calculates the conditional distributionp(ξ j ; ξ i , t) based on ξ i andp(ĉ j ; t), assuming that j will quickly respond to ξ i . To do so, i first finds the set of optimal motions of j for everyĉ j ∈ C given ξ i . This set is denoted by where 1(·) is an indicator function. Forξ j ∈ Ξ j /Q j (ξ i ), we setp(ξ j ; ξ i , t) = 0. We can now develop the planning problem for a proactive agent: min

C. Socially-aware motion
To develop the planning problem for a socially-aware agent i, we will first find the set of motions {ξ j i } ⊂ Ξ i that are wanted by j at time t. By definition, ξ j i belongs to motion tuples (ξ i , ξ j ) ∈ Q(c i ,ĉ j , t) that minimizes f (ξ j , ξ i ,ĉ j ). This set is denoted by Q j (c i ,ĉ j , t). Based on Q j (c i ,ĉ j , t) andp(c i ,ĉ j ; t), we can calculate the conditional probability p(ξ j i ;c i ,ĉ j , t) and the marginalp(ξ j i ; t). A socially-aware agent solves the following problem where the difference between i's planned motion and the wanted motion from j is added to the proactive loss: The weight β ≥ 0 tunes the importance of social awareness in the objective: A large β will make i follow what it believes that j wants it to do, while a small β will convert i to a proactive agent.

V. SIMULATION CASES AND ANALYSES
In this section we will empirically answer two questions: (1) How do planning strategies influence interaction dynamics, and (2) why empathy is important for intent inference? We base all experiments on a simulated intersection case introduced as follows.

A. Simulation setup
The intersection case is summarized in Fig. 1, where M moves up (along y-axis) and H moves left (along x-axis). Motion representation: With minor abuse of notation, we define ξ i as a scalar that determines the distance covered by an agent in T = 100 steps, and assume that each agent moves at a uniform speed and a predefined direction: M is the state of M in the x direction. The safety loss is defined as l safety = exp(a(−D 2 + b)), where D = ||s M − s H || 2 2 when both cars are in the interaction area Ω as shown in Fig. 1, and otherwise D = ∞; a = 5.0 so that the safety penalty increases significantly as the two cars approach each other; b = 1.5w 2 where w = 1.33 is the length of the car. This setting creates a safe zone for an agent since the penalty diminishes when D 2 > b. For the socially-graceful agent, β is set to 0.1 for the following experiments. A parametric study on β will be discussed later in this section. Performance metrics: We measure the performance of a pair of motion planning strategies, denoted by P i ∈ {reactive, proactive, social} for i ∈ {M, H}, using two metrics, namely, social gracefulness and social efficiency. Gracefulness, denoted by q grace , is defined as where T s is the time horizon for the entire simulation, u P M M (t) is the action taken by M at t using strategy P M , and u M is the action that H actually wants M to perform, which can be different from what M believes that H wants it to perform. We only measure gracefulness of M (the AV). Social efficiency, denoted by q eff , is defined as the time required for the agents to reach an agreement. An agreement is reached at time t when what j expects i to do matches with what i actually does, i.e., p(ξ i = ξ i (t); t) = 1. Therefore we can define q eff = arg min t={0,··· ,Ts},p(ξi=ξi(t);t)=1,i∈{M,H} t.
Experiment setup: The experiments will enumerate over P i × P j ∈ {reactive, proactive, social} 2 and c M × c H ∈ {1, 10 9 } 2 . c i = 1 represents a non-aggressive agent that will try to avoid being in Ω with the other agent; c i = 10 9 an extremely aggressive agent that is willing to collide with the other agent. To test whether an agent can handle unexpected intents, the candidate intent set for decoding is set to C = {1, 10 3 }. c i = 10 3 represents an aggressive agent that avoids collision. Conflict in inference: It is worth mentioning that since the agents do not follow the baseline algorithm for choosing a motion, their motions do not necessarily belong to an equilibrium set. This causes occasions where the probability mass of the true intent of j becomes zero as inferred by i, or where the updated probability distribution, e.g.,p(ĉ j ; t), has all zero entries when all candidate intents have been eliminated during the inference process. In the implementation, we setp(ĉ j ; t) back to a uniform distribution when the latter happens. B. Influence of planning strategy on the interaction We use Table I to summarize gracefulness and efficiency under all combinations of planning strategies and intent settings. Due to page limit, we highlight two key findings.
(1) The socially-aware strategy balances efficiency and gracefulness, provided that human drivers are reactive [4] and non-aggressive (c H = 1). In particular, a socially-aware M takes advantage of a non-aggressive agent, and thus it makes the interaction more efficient than a reactive agent (which leads to a stagnation as seen in Fig. 3a), while at the same time in a more graceful way than a proactive agent (comparison between Fig. 3b and c). (2) In comparison with proactive planning, the socially-aware M avoids "panic reactions" when facing unexpectedly aggressive H during an interaction. As seen in Fig. 3d, a proactive M realizes that it needs to back off after it enters the interaction zone, forcing itself to make large change in its motion. In comparison, a socially-aware M avoids this as it has been partially complying to H's intent all along the way, thus creating a smoother negotiation with H, see Fig. 3e.

C. Parametric study on β
We performed a parametric study on the gracefulness weight β to examine its influence on the gracefulness and efficiency of the interaction. Results are summarized in Table II. In all cases, H is reactive and non-aggressive. As β increases, M improves its gracefulness by taking actions closer to what is wanted by H. The efficiency, however, becomes worse towards β = 0.5 as the interaction becomes similar to that of reaction vs. reaction. Verbally, being graceful but not enough graceful will cause confusion in interactions. As β further increases, M converges to follow a motion that is in favor of H, and thus improves the efficiency.

D. The importance of empathy in intent inference
We now investigate the importance of empathy in intent inference using a similar experimental setting as above. We show that if agent i is modeled to believe that agent j already knows its true intent, then i will create false estimation of j's intent. Experiment setup: In the same intersection scenario, we use a reactive M vs. a reactive H setting with c M = 1 and c H = 10 3 . In the non-empathetic case, we fixc M = 1 for M's inference processes, and keep H as an empathetic agent. Analysis: Fig. 4 summarizes the differences between the non-empathetic and empathetic cases. In the physical space, we observe that M in the non-empathetic case iterates between a high and a low speed, similar to the reactive vs. reactive case with c M = c H = 1, until t = 37 when M realizes that H might be more aggressive than it thought, and starts to back off. In the empathetic case, this abrupt Both agents take the same actions at every time step since they share the same settings. After the initial action at t = 0, both take the smallest step ξ = 1 at t = 1 due to the concern that the other agent will take ξ = 5. This iteration between two action values continues indefinitely. This deadlock can be broken when the agents have significantly different cs.  This difference in the physical space is caused by that of the intent inference, see Fig. 4b. We will focus the discussion at t = 17 where the two cases starts to depart from each other. At this time step, H takes ξ H = 1 and M chooses to stop for both cases. The equilibrium sets for all intent combinations are summarized in Table III. In the empathetic case, based on Eq. (4), we have p(c M = 10 3 ,ĉ H = 10 3 , t = 18) = 1 since this is the only combination that explains ξ H = 1. This leads to p(ĉ H = 10 3 , t = 18) = 1. For the non-empathetic case, since M believes that H knows about its non-aggressiveness, we have p(c M = 1,ĉ H = 1, t = 18) = 1. This is because withc M = 1, the only equilibrial motions of H are ξ H = 0 and ξ H = 5, between which the former is closer to the observation. This misinterpretation led to p(ĉ H = 1, t = 18) = 1, and M's more advantageous motion in the following steps. The above analysis showed that by fixingc M , the agent excludes plausible explanations of others' behavior.

VI. CONCLUSION AND FUTURE WORK
This paper investigated an empathetic intent inference algorithm for a non-collaborative interaction between two agents, and evaluated motion planning formulations that are enriched by the inference, with respect to social gracefulness and efficiency.
We now discuss limitations of the presented study and propose future directions.
a) The inconsistency between intent decoding and motion planning: One may notice that during motion planning, i incorporates the uncertainty of the inference of j's future motion. However, in intent decoding, i assumes that j uses a one-hot estimation of i's intent (c M ) in its planning. To fix this inconsistency, i would need to model j to have considered a distribution of intents of i in j's planning, leading to an inference of the distribution of the distribution (ofc i ) by i. b) Provable necessity and sufficiency of empathy: We demonstrated in Sec. V a case where non-empathetic inference leads to false estimation of others' intent. However, we have not yet investigated the necessary and sufficient conditions under which empathy will be necessary for the inference to achieve correct convergence. Or mathematically, what are the necessary and sufficient conditions to have p(c i = c i ,ĉ j = c j ; t) = 0 and p(c i = c i ,ĉ j = c j ; t) > 0 for some c i = c i ? c) Inference of planning strategy: The above discussion suggests that due to the variation of planning strategies, intent inference at a parametric level may not be effective when one has a wrong guess of the others' strategy. The question is then how the inference of strategies can be incorporated, for example to differentiate a proactive agent that pretends to be aggressive and an aggressive agent. In the discrete setting as presented in this paper, the inference can be done by enumerating over all candidate strategies. This, however, will not elegantly accommodate the estimation of hyper-parameters such as β. Another potential approach is to introduce a meta-objective as a weighted sum of loss functions collected from all strategies, and to infer the strategy by estimating the weights of this meta-objective, in addition to the intent parameters. d) Computational challenges: Last but not least, extending the proposed decoding and planning algorithms to continuous domains will be necessary for their scalability in multi-vehicle coordination scenarios. However, doing so will introduce computational challenges due to the non-convexity of the inference and planning problems. In addition, the incorporation of a high-dimensional distribution of inferred motions in motion planning can be intractable. We expect scenario-specific solutions to these challenges.