# Contingencies from Observations: Tractable Contingency Planning with Learned
Behavior Models

Nicholas Rhinehart∗, Jeff He∗, Charles Packer, Matthew A. Wright
Rowan McAllister, Joseph E. Gonzalez, Sergey Levine  UC Berkeley

###### Abstract

Humans have a remarkable ability to make decisions by accurately reasoning
about future events, including the future behaviors and states of mind of
other agents. Consider driving a car through a busy intersection: it is
necessary to reason about the physics of the vehicle, the intentions of other
drivers, and their beliefs about your own intentions. If you signal a turn,
another driver might yield to you, or if you enter the passing lane, another
driver might decelerate to give you room to merge in front. Competent drivers
must plan how they can safely react to a variety of potential future behaviors
of other agents before they make their next move. This requires contingency
planning: explicitly planning a set of conditional actions that depend on the
stochastic outcome of future events. Contingency planning outputs a policy
that is a function of future timesteps and observations, whereas standard
model predictive control-based planning outputs a sequence of future actions,
which is equivalent to a policy that is only a function of future timesteps.
In this work, we develop a general-purpose contingency planner that is learned
end-to-end using high-dimensional scene observations and low-dimensional
behavioral observations. We use a conditional autoregressive flow model to
create a compact contingency planning space, and show how this model can
tractably learn contingencies from behavioral observations. We developed a
closed-loop control benchmark of realistic multi-agent scenarios in a driving
simulator (CARLA), on which we compare our method to various noncontingent
methods that reason about multi-agent future behavior, including several
state-of-the-art deep learning-based planning approaches. We illustrate that
these noncontingent planning methods fundamentally fail on this benchmark, and
find that our deep contingency planning method achieves significantly superior
performance.

##  I Introduction

The ability of humans to anticipate, probe, and plan to react to what other
actors could do or want is central to many social tasks that humans find
simple but AI systems find difficult [1]. Effectively driving a car, for
example, generally requires (1) predictive dynamics models of how cars move,
(2) predictive models of driver reactions, and (3) the ability to plan around
and resolve uncertainty about other drivers’ intentions. Autonomous systems
that operate in multi-agent environments typically satisfy 1–3 with separate
modules that decouple prediction and planning, yet in practice the modules are
highly dependent on accurate perception, an unsolved task [2, 3, 4]. Learning-
based end-to-end systems that navigate complex multi-agent environments from
raw sensory input have been the focus of recent work [5, 6, 7], but do not
satisfy (3), because they do not model the behaviors of the other agents.

A potential approach to building a system is to first build models to forecast
other agents’ behavior, and then construct “open-loop” action plans using
these models [8, 9]. However, this fails to account for the co-dependency
between robot actions and environment. Specifically, it ignores how other
agents would react to robot actions and how the robot’s future actions should
be different depending on what the other agents do. This can lead to
underconfident behavior, known as the “frozen robot problem” [10]. Thus, in
many real-world situations, decoupling the tasks of forecasting human behavior
and planning robot behavior is a poor modeling assumption. A resolution to
this problem can be achieved through _contingency planning_ [11, 12, 13, 14],
which produces a plan that is adaptive to future behaviors of other agents or
the environment. This is equivalent to planning a closed-loop policy.

Figure 1: A robot’s unprotected left, in which it does not have the right of
way in the intersection and must either wait for the oncoming car to either
pass or yield before turning. An unprotected left is a realistic multi-agent
scenario that requires contingent behavior in order to achieve optimal
outcomes, as the best _a priori_ robot trajectory suboptimally waits outside
the intersection (left branch), i.e. the best sequence of noncontingent future
decisions is (Wait Outside, Turn After Human), because the robot cannot be
guaranteed to be able to traverse a fixed spatiotemporal path due to
uncertainty about the human’s intention. However, a contingent planner can
achieve a better result: the optimal plan is to enter the intersection in
order to observe if the other driver will yield to the robot, and either turn
or wait contingent upon the other driver’s decision. Top: The decision tree of
robot and human behavior. Our approach, Contingencies from Observations, uses
behavioral observations sampled from decision trees as training data to learn
a behavioral model used in a contingent planning objective. Bottom: Conceptual
diagrams of the outcomes at each leaf. Videos, code, and trained models are
available at our website: https://sites.google.com/view/contingency-
planning/home.

(a) Robot leader planning. The planner does not model the human’s influence on
the robot, resulting in a deterministic noncontingent plan. Also known as MPC,
this plans action trajectories independent of future behaviors of the other
agents [15, 16, 17]

(b) Human leader planning. The planner does not model the robot’s influence on
the human, which means that the robot does not model how its future actions
can affect decisions of the other agents [11, 12]. This can result in
“underconfident” plans.

(c) Co-leader planning. This approach plans a policy modelled to both
influence and be influenced by the stochastic behavior of the human. In
contrast to our method, prior contingency planning methods do not use a
learned behavioral model [13, 14].

(d) Joint planning. The planner erroneously assumes that it can control all
agents, potentially resulting in “overconfident” behavior than can lead to
unrecoverable errors. We demonstrate this phenomenon in our experiments.

Figure 2: Various models of multi-agent interaction, based on different
assumptions, as probabilistic graphical models. Circles denote random
variables we can predict, square nodes denote robot decisions we can plan,
shading indicates known values, and thick arrows represent “carry-forward
dependencies” for visual simplicity (any two nodes connected by a chain of
thick nodes has an implicit directed edge).

In many partially-observed settings, optimal policies must gather information
about the state of the environment (e.g. the intentions of other agents) and
then act accordingly. Consider a common scenario encountered when driving on
public roads: an unprotected left-hand turn, in which the robot’s goal is to
turn left in the presence of another vehicle that may or may not yield, as
seen in Fig. 1. The other driver’s intention to yield must be revealed before
we (the robot) commit to turning left; we must _actively seek this information
to resolve the uncertainty in the other driver’s intention_. Using a turn-
signal indicator can provoke the other agent to reveal their intention, as can
edging the robot into the intersection. Not only must we plan to be contingent
upon the human, we must model the human as contingent upon us. Let us term
this “active contingency” to differentiate it from “passively contingent”
models that neglect the robot’s influence on the other agents. In this case,
we must plan to enter the intersection to indicate our desire to turn left
ahead of the other driver and have a contingency planned in case the driver
does not yield. Because the other driver may not stop, we cannot produce a
single state-space plan that is guaranteed to quickly cross the intersection
without potentially causing a crash, unless we wait outside the intersection.

We demonstrate that autoregressive normalizing flows can explicitly represent
a compact and rich space of contingent plans – forking paths of future
decisions necessary to operate successfully in environments with stochastic
outcomes. We use this model class to design a deep contingency planner that
scales to complex tasks with high-dimensional observations such as autonomous
driving. We designed a contingency planning benchmark of common driving tasks
in CARLA on which we compare our method to ablations and other methods. We
show that a single, general deep contingency planning model is quite effective
across several realistic scenarios, and that noncontingent planning methods
fundamentally fail at these common tasks.

##  II Related Work

Planning algorithms are central to robot navigation [18], and planning under
uncertainty is especially critical in uncontrolled environments like public
roads. Various choices exist for designing autonomous vehicle planning
algorithms that consider other vehicles (see Schwarting et al. [19] for a
thorough survey). We highlight some of the distinguishing concepts and design
choices below, and summarize the related work in Table I. In the following, we
refer to Fig. 2, which depicts various ways to model inter-agent dependencies.

Planning Method | Contextual |  | Learned | Contingency
---|---|---|---|---
| Behavior Model
Hardy and Campbell [11] | ✓ |  | ✗ | Passive
Bandyopadhyay et al. [20] | ✗ |  | ✗ | Active
Xu et al. [21] | ✗ |  | ✗ | None
Zhan et al. [12] | ✗ |  | ✗ | Passive
Sadigh et al. [15] | ✗ |  | ✗ | None
Galceran et al. [13] | ✓ |  | ✗ | Active
Schmerling et al. [16] | ✗ |  | ✓ | None
Rhinehart et al. [5] | ✓ |  | ✓ | None
Zhou et al. [22] | ✗ |  | ✗ | None
Fisac et al. [14] | ✗ |  | ✗ | Active
Zeng et al. [6] | ✓ |  | ✓ | None
Tang and Salakhutdinov [17] | ✓ |  | ✓ | None
Cui et al. [23] | ✓ |  | ✓ | Passive
Bajcsy et al. [24] | ✗ |  | ✓ | Passive
Contingencies from Observations | ✓ |  | ✓ | Active

Table I: Comparative summary of recent explicit planning methods for
autonomous navigation tasks (ordered by publication date).

Learned behavior model, noncontingent planning:

Recently, fully learned planning approaches have shown promising results on
autonomous navigation benchmarks and settings [5, 6, 7]. These approaches
resemble model-based reinforcement learning (MBRL) because they model some
aspect of environment dynamics in order to generate plans under reward
functions. However, these methods will fail on tasks that require explicit
contingency planning because they do not represent the future behavior of
other agents, and therefore cannot be explicitly contingent; we demonstrate
[5] failing in our experiments. In the terminology of Fig. 2, “robot leader”
methods, commonly referred to as MPC-shooting based methods, plan action
trajectories, which means that the actions will be fixed for all possible
future behaviors of the other agents [15, 16, 17].

Modular approaches such as those used in the DARPA Grand Challenge [2, 3] and
modern industry systems [4] have the potential to be contingent, but are
highly dependent on imperfect perception pipelines. We are not aware of a
published demonstration of contingency planning in a pipeline approach on a
realistic autonomous navigation task.

Passive contingency planning: While prior work has used contingency planning
for autonomous navigation, it has not used learned behavioral models. In
“human leader” approaches [11, 12, 23], the behavior prediction of the other
agents is independent of the future behavior of the robot, which means that
the robot does not model how its future actions can affect decisions of the
other agents, shown Fig. 2(b). Unlike the active “co-leader” (Fig. 2(c))
approach, “human leader” methods cannot plan to provoke other agents to reveal
their intentions. Galceran et al. [13] and Fisac et al. [14] perform co-leader
contingency planning with hand-crafted models (dynamics models, behavior
models, reward functions) rather than learned behavior models. Both Cui et al.
[23] and Bajcsy et al. [24] (a reachability analysis-based approach) only
consider single-forking contingencies, whereas our method considers
contingencies at every timestep, and therefore does not require determining a
‘branching time’.

Model-free methods: An alternative to using the model-based planning
approaches described above is to learn a model-free policy, which has the
capacity to implicitly represent contingent plans. Model-free imitation
learning (IL) and reinforcement learning (RL) have been used to construct
policies in autonomous driving environments with multi-agent interaction [25,
26, 27, 28, 29, 30]. Model-free approaches can be successful when the data and
task distribution shifts between train and test are small – a well-trained
policy will naturally mimic high-quality demonstration data exhibited by a
contingent expert or evoked by a well-crafted reward function. However, if
there is mismatch between the training and test rewards, the policy will
produce suboptimal behavior. While goal-conditioning methods can address the
suboptimality of adapting model-free methods to test-time data by serving as
the representation for the test-time reward function, the goal space of the
agents must be specified _a priori_ , requires goal labels, and precludes
adapting the learned system to new types of test-time goal objectives [27,
30]. Furthermore, in contrast to model-free methods, our method explicitly
represents the planned future behavior, which offers interpretability and
model introspection benefits.

Our proposed method is both contingent and uses a fully-learned behavior
model, unlike prior work that either had learned behavior models or was
actively contingent, but never both, as shown in Table I.

##  III Deep Contingency Planning

Below, we outline the deployment phase, planner design, and training phase.
Our method is depicted in Fig. 3.

Deployment: The following loop is executed during deployment: (1) the
contingency planner is given a learned behavioral model, goals, and high-
dimensional sensory observations as input, and outputs a multi-step plan in
the form of a robot policy. (2) The planned robot policy is executed for one
step to output a target position, which is (3) tracked by a proportional
controller that outputs a control that includes robot steering, throttle, and
braking controls. (4) The control is executed on the robot in the environment,
which produces a new observation.

Planner design: The future behavior of the robot is planned in terms of a
parametric policy; a _subset_ of the policy’s parameters are used to optimize
a planning criterion. Crucially, this policy is closed-loop – it reacts
differently to (i.e., is _contingent_ on) different possibilities of the
future behavior of all agents (Fig. 2(c)). When the policy is open-loop, it is
noncontingent, and represents the future positional trajectory of the robot,
which can result in underconfident behavior (Fig. 2(a)). The planning
criterion incorporates several components: (1) the learned behavioral model to
forecast a probability distribution of the likely behaviors of all agents in
terms of positional trajectories; the PDF of this distribution is used in the
planning criterion. The planning criterion also incorporates (2) goals
specified as positions, and optionally incorporates (3) hard or soft
constraints on joint behavior. The planner optimizes for a robot policy that
has a high expected probability of joint behavior, and a high expected
probability of satisfying the provided goal location and optional goal
constraints; the expectation is under the other agents’ sources of
uncertainty.

Model design and training: The behavioral model is trained with a dataset of
trajectories of multi-agent positions paired with high-dimensional sensory
observations of one of the agents. Training maximizes the likelihood of the
trajectories, similar to multi-step Behavioral Cloning [31]. Following prior
IL work, we sometimes call these positions _behavioral observations_ , in
contrast to _demonstrations_ (observations of state-action pairs). We assume
that the behaviors in this data are goal-directed, but we do not assume that
every behavior would score well under the planning criterion: some of these
behaviors require navigation to different goals than those seen in training,
and some of these trajectories exhibit behavior that may be undesirable. This
somewhat general assumption on the quality of the data behavior demands a
planning criterion that involves terms of multi-agent trajectories, which
necessitates modeling the likely trajectories of the other agents.

Figure 3: Flowchart that describes the components of our approach. A
behavioral model is trained to forecast multi-agent trajectories conditioned
on high-dimensional scene observations, and is used during deployment to
construct a contingency planner. The contingency planner receives goals
$\mathcal{G}$ from an outer navigator, as well as high-dimensional
observations $\mathbf{o}_{t}$ at timestep $t$ from the environment. The
contingency planner plans a policy, which predicts the immediate next target
position $\mathbf{x}_{t+1}^{r}$. This next position is passed to a
P-controller to produce the necessary action $\mathbf{a}_{t+1}^{r}$.

###  III-A Preliminaries

We consider multi-agent systems composed of $A\geq 2$ agents (e.g., vehicles).
We assume agent positions are fully observable by all agents, but the
intentions of each agent (e.g., intended destinations) are hidden from each
other. We consider continuous positions and discrete time, and define the
position of the $a$th vehicle at time $t$ by its location in a $d$-dimensional
Cartesian space as $\mathbf{x}^{a}_{t}\in\mathbb{R}^{d}$. The joint positions
of all vehicles are denoted by $\mathbf{x}_{t}\in\mathbb{R}^{A\times d}$,
where a lack of superscript indicates all vehicles. Let
$\mathbf{x}_{t}^{r}=\mathbf{x}_{t}^{1}\in\mathbb{R}^{1\times d}$ index the
position of the controlled robot vehicle, and
$\mathbf{x}_{t}^{h}=\mathbf{x}_{t}^{2:A}\in\mathbb{R}^{(A-1)\times d}$ index
the positions of other human-driven vehicles that the robot can influence but
has no direct control over. Let $t=0$ and $\mathbf{x}_{0}$ denote the current
timestep and joint position of the multi-agent system, and let
$\mathbf{x}_{\leq t}$ denote future joint positions $[1,\dots,t]$. Uppercase
denotes random variables (e.g. the stochastic sequence of all multi-agent
positions $\mathbf{X}_{\leq t}^{1:A}$), and lowercase denotes realized values.
The current observation of the robot is denoted
${\mathbf{o}}\doteq\\{\mathbf{x}_{0},\mathbf{i}_{0}\\}$; $\mathbf{i}_{0}$
provides high-dimensional information about the environment. In our
implementation, $\mathbf{i}_{0}\in\mathbb{R}^{H\times W}$ is a LIDAR range map
image [32].

###  III-B Model Design and Training Details

The planner requires a learned behavioral model that stochastically forecasts
multi-agent trajectories $\mathbf{X}_{\leq T}^{1:A}$ given context
$\mathbf{o}$, and captures co-dependencies between agents at all timesteps.
Let $q_{\theta}(\mathbf{X}|\mathbf{o})$ denote this model. The model
factorizes into a product of autoregressive distributions parameterized by
neural networks that receive observations and previous states:

$\displaystyle q_{\theta}(\mathbf{X}_{\leq T}^{1:A}=\mathbf{x}_{\leq
T}^{1:A}|{\mathbf{o}})=\mathop{\prod}_{t=1}^{T}\mathop{\prod}_{a=1}^{A}q^{a}(\mathbf{X}^{a}_{t}\\!=\\!\mathbf{x}^{a}_{t};\phi_{t}^{a}),$
(1)

where the parameters of $q^{a}$ are computed autoregressively in order to
model reactions dependent only on past data:
$\phi_{t}^{a}=f_{\theta}^{a}(\mathbf{x}_{<t}^{1:A},\mathbf{o})$. We restrict
$q^{a}$ to the family of distributions that can be sampled by transforming a
sample $\mathbf{z}_{t}^{a}\in\mathbb{R}^{d}$ from a fixed simple base
distribution chosen _a priori_ , $\bar{q}^{a}(\mathbf{z}_{t}^{a})$, to
$\mathbf{x}_{t}$, using a fixed invertible transformation of observations and
learned values $\mathbf{x}_{t}^{a}=m(\mathbf{z}_{t}^{a};\phi_{t}^{a})$. E.g.,
if
$q^{a}=\mathcal{N}(\cdot|\\{\boldsymbol{\mu}_{t}^{a},\boldsymbol{\sigma}_{t}^{a}\\})$,
then
$m(\mathbf{z}_{t}^{a};\phi_{t}^{a})=\boldsymbol{\mu}_{t}^{a}+\boldsymbol{\sigma}_{t}^{a}\mathbf{z}_{t}^{a}$,
and $\bar{q}^{a}(\mathbf{z}_{t}^{a})=\mathcal{N}(\mathbf{z}_{t}^{a};0,I)$.
Because the $\bar{q}^{a}$ are independent, the model represents multi-agent
behavior as a learned coupling of independent variables, $\mathbf{z}_{t}^{a}$.
Taken together, these conditions specify that the model is a (conditional)
autoregressive normalizing flow [33, 34].

Now we show how $q_{\theta}$ can be used to design a compact and rich space of
contingent policies that is amenable to fast optimization at planning time.
First, note that the process of generating agent $a$’s position at time $t$
with $q_{\theta}$ can be seen as generating a position from (state-space)
policy:
$q^{a}(\mathbf{X}_{t}^{a}\mid\mathbf{x}_{<t}^{1:A},\mathbf{o};\theta)$. Next,
note that given $\mathbf{z}_{t}^{a}$, $m$ can be written as the application of
a deterministic policy parameterized by both $\mathbf{z}_{t}^{a}$ and
$\theta$:
$\mathbf{x}_{t}^{a}=\pi^{a}(\mathbf{x}_{<t}^{1:A},\mathbf{o};\mathbf{z}_{t}^{a},\theta)$.
On the one hand, $q_{\theta}$ can be seen as a collection of stochastic
policies $\left\\{q^{a}\right\\}_{a=1}^{A}$. On the other hand, $q_{\theta}$
can be seen as a collection of deterministic policies and policy parameter
priors $\\{(\pi^{a},\bar{q}^{a})\\}_{a=1}^{A}$. At planning time, we can
specify a contingent robot plan by deciding values for the robot’s policy
parameters, $\mathbf{z}_{\leq T}^{r}\in\mathbb{R}^{2\times T}$, rather than
sampling each $\mathbf{z}_{t}^{r}$ from its prior $\bar{q}^{r}$. Doing so
results in a contingency plan that is reactive to each potential joint
behavior of the other agents, $\mathbf{X}_{\leq t}^{2:A}$, for $t\in[1,T]$.
Because the future behaviors of the other agents are unobserved at test-time,
the overall system is still stochastic given the contingency plan
parameterized by $\mathbf{z}^{r}$. This method of partially parameterizing a
policy is appealing because it requires no modifications to the model. Once
$q_{\theta}$ is trained, $\theta$ is fixed, and planning is a matter of
choosing the free parameters, $\mathbf{z}^{r}$, of $\pi^{r}$. Other
parameterizations could certainly be used, but we found this method efficient.
[5, 35] employ similar parameterizations in the noncontingent setting.

A natural question that arises from this discussion is: which contingent plans
can such a scheme actually represent? While analyzing this in the continuous
case is difficult, we can provide a detailed analysis of this question in the
case where all variables ($\mathbf{x}$ and $\mathbf{z}$) are discrete. In this
case, we show in the Appendix that likely contingent plans can be expressed in
terms of $\mathbf{z}^{r}$ and can represent sequences of $n$-th best responses
under the model $q_{\theta}$ (i.e., first-best, second-best, etc.). Key to
this analysis and the general richness of the planning space is the
invertibility of $m$ in $\mathbf{z}_{t}^{a}$, which ensures that all
$\mathbf{x}_{t}^{a}\in\mathbb{R}^{d}$ are realizable outputs of $\pi^{a}$. In
the Appendix (Fig. 6), we also give example visualizations of a single
$\mathbf{z}^{r}_{\leq T}$ resulting in high-quality plans contingent on
plausible futures of other agents.

We train the model, $q_{\theta}$, with a dataset $\\{(\mathbf{x}_{\leq
T}^{1:A},\mathbf{o})_{n}\\}_{n=1}^{N}$, depicted in Fig 3. As previously
mentioned, we assume that these behaviors are goal-directed to diverse goals,
which allows the model to represent many modes of plausible behavior (e.g.,
turning left, turning right, traveling passively, traveling aggressively). We
defer implementation details of constructing and training $q_{\theta}$ to
Section IV-B.

###  III-C Planner Design Details

Primary planning objective: Having described our learned behavioral model and
a method to parameterize a contingent plan as a closed-loop policy, we turn to
constructing a planning objective in order to evaluate the _quality_ of the
planned policy in terms of how plausible its behavior is and how well it
satisfies goals at test time. In our application, goals
$\mathcal{G}=(\mathbf{g},\mathbb{G})$ are provided to the robot in terms of
coordinate destinations $\mathbf{g}\in\mathbb{R}^{2}$, as well as a set of
constraints, $\mathbb{G}$, on the joint trajectory specified as an indicator
function $\delta_{\mathbb{G}}(\mathbf{x})$, which is $1$ where
$\mathbf{x}\in\mathbb{G}$ and $0$ otherwise. To evaluate the quality of a
plan, we take inspiration from the single-agent (non-contingent) imitative
model planning objective [5] by formulating planning with the model as maximum
_a posteriori_ (MAP) estimation. Instead of MAP estimation of a robot
trajectory (non-contingent plan), we perform MAP estimation of the subset of
policy parameters $\mathbf{z}_{\leq T}^{r}$ with posterior $p(\mathbf{z}_{\leq
T}^{r}|\mathcal{G},{\mathbf{o}})$. The resulting lower-bound objective,
derived on the supplementary website, is:

$\displaystyle\mathcal{L}_{\text{{CfO}}}(\pi^{r}_{\mathbf{z}_{\leq T}})=$ (2)
$\displaystyle\mathop{\mathbb{E}}_{\mathbf{z}^{h}\sim\mathcal{N}(0,I)}\Big{[}\log\underbrace{q_{\theta}(\bar{\mathbf{x}}_{\leq
T}|{\mathbf{o}})}_{(1)~{}\text{prior}}\\!+\\!\log\underbrace{\mathcal{N}\big{(}\bar{\mathbf{x}}^{r}_{T};\mathbf{g},I\big{)}}_{(2)~{}\text{destination}}\\!+\\!\log\underbrace{\delta_{\mathbb{G}}(\bar{\mathbf{x}}_{\leq
T})}_{(3)~{}\text{constraint}}\Big{]}.$

Eq. 2 consists of several terms: the (1) behavioral prior encourages the
planned policy to result in joint behavior that is likely under the learned
model; (2) the destination likelihood encourages the policy to end near a goal
location; (3) an optional goal constraints penalizes the policy if it does not
satisfy some desired constraint. The expectation results from the uncertainty
due to the presence of other (uncontrolled) agents. In practice, we perform
stochastic gradient ascent on Eq. 2 w.r.t. $\mathbf{z}_{\leq T}^{r}$ and
approximate a violated constraint ($\log\delta_{\mathbb{G}}(\mathbf{x}_{\leq
T})\\!=\\!-\infty$ when $\mathbf{x}_{\leq T}\notin\mathbb{G}$) with a large
negative value.

Alternative planning objectives: Consider instead directly planning
$\mathbf{x}_{\leq T}^{r}$ under uncertain human trajectories
$\hat{\mathbf{x}}_{\leq T}^{h}$:

$\displaystyle\mathcal{L}^{\text{r}}(\mathbf{x}_{\leq T}^{r})$
$\displaystyle=\mathop{\mathbb{E}}_{\hat{\mathbf{x}}\sim
q}\log\mathcal{N}(\mathbf{x}_{T}^{r};\\!\mathbf{g},\\!I)\\!+\\!\log\delta_{\mathbb{G}}([\mathbf{x}^{r}\\!,\\!\hat{\mathbf{x}}^{h}])\\!+\\!\log
q([\mathbf{x}^{r}\\!,\\!\hat{\mathbf{x}}^{h}]|{\mathbf{o}}).$

Planning with ${\mathcal{L}^{\text{r}}}$ will result in a noncontingent plan
that is _underconfident_ , because the criterion fails to account for the fact
that $\mathbf{x}^{r}_{t}$ affects $\mathbf{x}^{h}_{>t}$. This is illustrated
in Fig. 2(b). For example, we show in our experiments how an underconfident
planner leads to a _frozen robot_ that prefers not to enter the intersection
and indicate that it intends to turn left, because the plan – a single fixed
trajectory – is not affected by whether or not the human driver yields to it.
The best trajectory under this criterion is a passive waiting trajectory that
stays outside the intersection until the human has passed. Finally, consider
planning _both_ $\mathbf{x}^{r}$ and $\mathbf{x}^{h}$ (Fig. 2(d)), i.e.,
assuming control of both the robot and the human trajectories:

$\mathcal{L}^{\text{joint}}(\mathbf{x})=\log\mathcal{N}(\mathbf{x}_{T}^{r};\mathbf{g},I)+\log\delta_{\mathbb{G}}(\mathbf{x})+\log
q_{\theta}(\mathbf{x}|{\mathbf{o}}).$

This is an _overconfident_ planner, because it assumes that the other agents
will obey the robot’s plan for them. Thus, this planner is acceptable when the
human behaves as planned, but risky when the human does not. In the left-turn
scenario, $\mathcal{L}^{\text{joint}}$ causes the robot to assume that the
human will always yield to it, resulting in dangerous behavior when the human
sometimes does not. Instead, if the prior of joint behavior is the only
component of the planning criterion (i.e. just the final term of
$\mathcal{L}^{\text{joint}}$), then the planner simply optimizes for the mode
of the prior, which will result in an undirected likely joint behavior.

##  IV Experiments

Our main experimental hypothesis is that _(i)_ some common driving situations
that require multi-agent reasoning can be nearly solved with our deep
contingency planning approach. This hypothesis is related to the following
secondary hypotheses, which state that various noncontingent planning methods
cannot solve these situations: _(ii)_ a noncontingent learning-based
underconfident planner will lead to a frozen robot in some situations, _(iii)_
a noncontingent learning-based planner of joint trajectories will lead to an
unsafe robot in some situations, _(iv)_ online model-free methods will incur a
significant cost of failed behaviors before learning to succeed, in contrast
to our method, and _(v)_ oblivious planning (unable to adapt to cost function)
will lead to an unsafe robot in some situations. To evaluate these hypotheses,
we developed a set of common driving scenarios in which contingency planning
matters.

###  IV-A Benchmark Scenarios

Figure 4: Overhead images for each scenario. The circles denote decision
points; blue paths being robot, orange paths being “human”. _Left and Right_ :
The robot tries to turn. At (1), robot decides if to enter the intersection as
turning signal to human. At (2), robot decides if to aggressively turn or
wait. At (3), if robot previously entered the intersection, human may or may
not yield. Again at (2), if robot is waiting, it decides when to turn based on
if human yielded. At (4), if robot turned aggressively and human didn’t yield,
a near-collision occurs. _Middle_ : Robot tries to overtake. At (1), robot
decides if to enter the left lane. At (2), robot decides if to overtake
aggressively. At (3), human decides if to yield. Again at (2), if robot wasn’t
aggressive, it decides if to overtake. At (4), if robot was aggressive and
human didn’t yield, a near-collision occurs.

We evaluate our method and several others on three multi-agent driving
scenarios that we built in the CARLA simulator [25]: a left-turn scenario
similar to the one discussed in Fig. 1 and conceptually similar to that in
[11], a highway overtaking scenario conceptually similar to that used in prior
work [15, 14], and a right turn at a stop sign scenario. Images from each
scenario are shown in Fig. 4. For each scenario, we identified 4 suitable
locations, and used 1 of them as training locations and 3 as test locations.
At test time, we evaluate each method 10 times in each test location,
resulting in a total of 90 evaluation episodes per method
($3~{}\frac{\mathrm{scenarios}}{\mathrm{method}}\cdot
3\frac{\mathrm{locations}}{\mathrm{scenario}}\cdot
10\frac{\mathrm{episodes}}{\mathrm{location}}$). The testing episodes use a
fixed set of random seeds in the simulator.

In the left turn scenario, the robot car needs to execute a left turn, but the
oncoming vehicle may or may not yield. In the highway overtaking scenario, the
robot car must pass the car in front of it, but this requires entering the
left lane. Similar to how, in the left turn scenario, the other vehicle may or
may not yield, the leading car in the overtaking scenario may slow down or
maintain a constant speed to facilitate the robot car’s overtaking, or it may
accelerate to prevent it. In the right turn scenario, the robot car needs to
execute a right turn into a lane that contains a vehicle that may or may not
yield.

These scenarios, while common and easily negotiated by human drivers, have
features that make them difficult for many learning-based autonomous
navigation methods. The optimal outcomes (making the turns quickly and safely,
and successfully overtaking the other car) require cooperation from the human
agent, but the intent of the human to cooperate is unknown. This calls for
contingent planning. However, in order to infer the human’s intent, we (the
robot) must first act in a way that signals our own desire (entering the
intersection or the opposite lane) and evaluate their response.

###  IV-B Implementation Details

We designed these scenarios in suitable locations in the CARLA simulator [25].
We generated training data from hand-crafted policies designed to generate
each of the outcomes in each scenarios: first, the robot chooses whether to
begin its maneuver (enter the intersection or the opposite lane). If the robot
begins the maneuver, the other vehicle decides whether to accommodate the it
(yield to it or allow passing). Then, the robot decides whether to attempt to
complete the maneuver. The robot’s policy can be considered a suboptimal
expert, as it sometimes generates expert paths, but other times, it generates
conservative paths (by sometimes not entering the intersection or opposite
lane) and risky paths (by sometimes attempting to complete the maneuver
despite the other agent not yielding). Examples are given in the Appendix
(Fig. 7).

We adapted the ESP model from [36], which uses $q_{t}^{a}=\mathcal{N}$ and we
used $1.5$s of past at $10$Hz and $8$s of future at $3.75$Hz, resulting in
pasts of length $15$ and futures of length $30$. In contrast to the LIDAR
featurization in [36], we instead use $\mathbf{i}_{0}\in\mathbb{R}^{H\times
W}$ as a LIDAR range map image [32]. Whereas [36] performed _passive
forecasting_ of behaviors of agents, and was not used to decide controls of a
robot, our work focuses on building and executing actively contingent plans.

Method and baselines: We trained a _single_ global CfO model, which forces the
method to generalize across scenarios and locations. For comparison, we use
[17] (MFP) by following the shooting-based planning method described therein.
We experimented with a global model for MFP, but were unable to achieve good
performance, instead, we trained separate _per-scenario MFP models_. We use
the CfO model with the contingent planning objective (Eq. 2) as well as with
the “overconfident” noncontingent planner with criterion
$\mathcal{L}^{\textrm{joint}}$ from Section III-B. For the “underconfident”
planner, we used the suboptimal expert to create the set of per-agent paths
available at each timestep, and used $\mathcal{L}^{\textrm{r}}$ without the
prior term, which serves as a best-case underconfident planner (in the case of
a perfect model). To measure the importance of multi-agent planning vs. an
oblivious planner, we apply [5] by constructing a single-agent version of our
model, which cannot incorporate terms that involve predicted positions of
other agents. For this baseline, like MFP, we trained separate per-scenario
models. Further details are given in the Appendix.

###  IV-C Results

| Left Turns |  | Overtaking |  | Right Turns
---|---|---|---|---|---
Method | RG | RG* |  | RG | RG* |  | RG | RG*
Single-agent [5] | ${\scriptstyle 30}/{\scriptstyle 30}$ | $16/30$ |  | ${\scriptstyle 10}/{\scriptstyle 30}$ | $8/30$ |  | ${\scriptstyle 15}/{\scriptstyle 30}$ | $2/30$
Noncontingent, $\mathcal{L}^{\textrm{r}}$ | ${\scriptstyle 30}/{{\scriptstyle 30}}$ | $0/30$ |  | ${\scriptstyle 30}/{\scriptstyle 30}$ | $0/30$ |  | ${\scriptstyle 30}/{\scriptstyle 30}$ | $0/30$
Noncontingent, $\mathcal{L}^{\textrm{joint}}$ | ${\scriptstyle 30}/{\scriptstyle 30}$ | $9/30$ |  | ${\scriptstyle 29}/{\scriptstyle 30}$ | $12/30$ |  | ${\scriptstyle 23}/{\scriptstyle 30}$ | $9/30$
MFP [17] | ${\scriptstyle 30}/{\scriptstyle 30}$ | $9/30$ |  | ${\scriptstyle 16}/{\scriptstyle 30}$ | $9/30$ |  | ${\scriptstyle 9}/{\scriptstyle 30}$ | $9/30$
CfO (Eq. 2) (ours) | ${{\scriptstyle 29}}/{{\scriptstyle 30}}$ | $\mathbf{28}/\mathbf{30}$ |  | ${\scriptstyle 27}/{\scriptstyle 30}$ | $\mathbf{27}/\mathbf{30}$ |  | ${\scriptstyle 27}/{\scriptstyle 30}$ | $\mathbf{27}/\mathbf{30}$

Table II: Comparison of learning-based planning for control: Our co-Influence
model (CfO) learns how agents behave together, and is able to control a
vehicle to negotiate multi-agent driving scenarios safely and efficiently.
Ablations show that alternative non-contingent planners lead to either overly
conservative or unsafe trajectories.

Prior navigational planning work uses a variety of metrics to measure the
quality of a planned or predicted trajectory [17, 36]. In this work, we
evaluate our different planners in terms of closed-loop control metrics: the
ability of a method to reach a goal (1) successfully, and (2) safely and
efficiently. In Table II, we report results in terms of the goal-reaching
success rate (“RG”), which simply means that the robot vehicle eventually
reached the goal region, and _near-expert_ success rate (“RG*”), which we
define as the vehicle reaching the goal as quickly as an expert would, without
any near-collisions.

Examining Table II, we see evidence that supports the hypotheses mentioned at
the beginning of the section. First, _(i)_ the CfO planner (i.e., the one that
uses Eq. 2) has near perfect success rate in both scenarios, as well as a
nearly perfect rate of near-expert success. The high rate of completing the
maneuver in a near-expert way suggests that contingency planning is helpful
for efficiently navigating these complex scenarios, which is possible only by
probing the human’s intentions and reacting accordingly. Next, _(ii)_ our
“underconfident” noncontingent planner, while having a high success rate, has
a much lower count of near-expert successes than the contingent CfO planner.
The reason is that the underconfidence leads to “frozen robot” behavior that
slowed down the underconfident planner. In the left turn scenario, for
example, the underconfident planner will always wait for the oncoming vehicle
to pass through the intersection before beginning its own left turn. This
means the underconfident planner missed any opportunity to negotiate the
intersection as quickly as the expert did in the trials where the human
vehicle would have yielded.

For _(iii)_ , note that the “overconfident” noncontingent planner always
reaches the goal, but sometimes engages in unsafe behavior. Its aggressive
planning means that it will try to solve the scenario quickly every time,
which leads to near-collisions every time that the other vehicle does not
yield.

For _(iv)_ , we observe the “oblivious” planner [5] indeed performs
suboptimality across scenarios, leading to more near-collisions than the other
planners. Due to the suboptimality present in the training data, its planner,
which reasons solely about the ego-vehicle’s behavior, is insufficient in
these scenarios. Finally, for _(v)_ , we compare our approach to a model-free
reinforcement learning (RL) baseline, Proximal Policy Optimization (PPO), on
the left turn scenario.

As seen in Fig. 5, online model-free methods are capable of learning an
optimal policy. However, the RL agent incurs a significant number of
collisions before reaching a reasonable success rate (in contrast, since CfO
learns entirely offline, it need not experience collisions before learning how
to complete the task). Additionally, learning a successful policy with PPO
requires careful reward shaping on top of the cost model used in CfO. Further
details about the RL experimental setup, as well as example qualitative
results of contingent and noncontingent plans, are given in the Appendix.

Figure 5: Left: Reward vs steps of experience on the left turn scenario
(mean/std/min/max over three runs, best policy plotted in solid). Middle:
Collision rate vs steps. PPO is the only baseline that requires online
training (all other methods are horizontal lines). PPO (acceleration only,
similar to [17]) achieves a 0% collision rate. Right: Success rate vs steps.
PPO (acceleration only) achieves a 100% success rate. PPO (throttle, steering
and braking) is unable to exceed a 60%.

##  V Discussion

We present a deep contingent planning method for control in multi-agent
environments, and demonstrate its efficacy in common scenarios encountered in
the urban driving setting in comparison to several alternative methods for
data-driven planning, including a single-agent planner and a deep MPC-based
trajectory shooting method. Our method is quite tractable to apply – it is
learned entirely from demonstrations of plausible multi-agent behavior and
efficiently represents contingent plans in terms of components of the learned
model.

Acknowledgements: This research was supported by the Office of Naval Research,
ARL DCIST CRA W911NF-17-2-0181, JP Morgan, the Berkeley DeepDrive industry
consortium, and the supporters of the Berkeley RISELab.

## References

  * Russell [2019] S. Russell, _Human compatible: Artificial intelligence and the problem of control_. Penguin, 2019.
  * Thrun et al. [2006] S. Thrun, M. Montemerlo, H. Dahlkamp, D. Stavens, A. Aron, J. Diebel, P. Fong, J. Gale, M. Halpenny, G. Hoffmann _et al._ , “Stanley: The robot that won the DARPA Grand Challenge,” _Journal of field Robotics_ , vol. 23, no. 9, pp. 661–692, 2006.
  * Urmson et al. [2008] C. Urmson, J. Anhalt, D. Bagnell, C. Baker, R. Bittner, M. Clark, J. Dolan, D. Duggins, T. Galatali, C. Geyer _et al._ , “Autonomous driving in urban environments: Boss and the urban challenge,” _Journal of Field Robotics_ , vol. 25, no. 8, pp. 425–466, 2008.
  * Paden et al. [2016] B. Paden, M. Čáp, S. Z. Yong, D. Yershov, and E. Frazzoli, “A survey of motion planning and control techniques for self-driving urban vehicles,” _IEEE Transactions on intelligent vehicles_ , vol. 1, no. 1, pp. 33–55, 2016\.
  * Rhinehart et al. [2020] N. Rhinehart, R. McAllister, and S. Levine, “Deep imitative models for flexible inference, planning, and control,” in _International Conference on Learning Representations (ICLR)_ , 2020. [Online]. Available: https://openreview.net/forum?id=Skl4mRNYDr
  * Zeng et al. [2019] W. Zeng, W. Luo, S. Suo, A. Sadat, B. Yang, S. Casas, and R. Urtasun, “End-to-end interpretable neural motion planner,” in _Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 8660–8669.
  * Filos et al. [2020] A. Filos, P. Tigas, R. McAllister, N. Rhinehart, S. Levine, and Y. Gal, “Can autonomous vehicles identify, recover from, and adapt to distribution shifts?” in _International Conference on Machine Learning (ICML)_ , 2020\.
  * Thompson et al. [2009] S. Thompson, T. Horiuchi, and S. Kagami, “A probabilistic model of human motion and navigation intent for mobile robot path planning,” in _2009 4th International Conference on Autonomous Robots and Agents_. IEEE, 2009, pp. 663–668.
  * Ziebart et al. [2009] B. D. Ziebart, N. Ratliff, G. Gallagher, C. Mertz, K. Peterson, J. A. Bagnell, M. Hebert, A. K. Dey, and S. Srinivasa, “Planning-based prediction for pedestrians,” in _2009 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2009, pp. 3931–3936.
  * Trautman and Krause [2010] P. Trautman and A. Krause, “Unfreezing the robot: Navigation in dense, interacting crowds,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_. Taipei: IEEE, Oct. 2010, pp. 797–803.
  * Hardy and Campbell [2013] J. Hardy and M. Campbell, “Contingency Planning Over Probabilistic Obstacle Predictions for Autonomous Road Vehicles,” _IEEE Transactions on Robotics_ , vol. 29, no. 4, pp. 913–929, 2013.
  * Zhan et al. [2016] W. Zhan, C. Liu, C.-Y. Chan, and M. Tomizuka, “A non-conservatively defensive strategy for urban autonomous driving,” in _International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2016, pp. 459–464.
  * Galceran et al. [2017] E. Galceran, A. G. Cunningham, R. M. Eustice, and E. Olson, “Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction: Theory and experiment,” _Autonomous Robots_ , vol. 41, no. 6, pp. 1367–1382, 2017.
  * Fisac et al. [2019] J. F. Fisac, E. Bronstein, E. Stefansson, D. Sadigh, S. S. Sastry, and A. D. Dragan, “Hierarchical Game-Theoretic Planning for Autonomous Vehicles,” in _International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 9590–9596.
  * Sadigh et al. [2016] D. Sadigh, S. Sastry, S. A. Seshia, and A. D. Dragan, “Planning for autonomous cars that leverage effects on human actions,” in _Robotics: Science and Systems (RSS)_ , 2016.
  * Schmerling et al. [2018] E. Schmerling, K. Leung, W. Vollprecht, and M. Pavone, “Multimodal probabilistic model-based planning for human-robot interaction,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 3399–3406.
  * Tang and Salakhutdinov [2019] Y. C. Tang and R. R. Salakhutdinov, “Multiple futures prediction,” in _Neural Information Processing Systems (NeurIPS)_ , vol. 32, 2019, pp. 15 424–15 434.
  * LaValle [2006] S. M. LaValle, _Planning algorithms_. Cambridge University Press, 2006.
  * Schwarting et al. [2018] W. Schwarting, J. Alonso-Mora, and D. Rus, “Planning and decision-making for autonomous vehicles,” _Annual Review of Control, Robotics, and Autonomous Systems_ , 2018.
  * Bandyopadhyay et al. [2013] T. Bandyopadhyay, K. S. Won, E. Frazzoli, D. Hsu, W. S. Lee, and D. Rus, “Intention-aware motion planning,” in _Algorithmic foundations of robotics X_. Springer, 2013, pp. 475–491.
  * Xu et al. [2014] W. Xu, J. Pan, J. Wei, and J. M. Dolan, “Motion planning under uncertainty for on-road autonomous driving,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 2507–2512.
  * Zhou et al. [2018] B. Zhou, W. Schwarting, D. Rus, and J. Alonso-Mora, “Joint multi-policy behavior estimation and receding-horizon trajectory planning for automated urban driving,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 2388–2394.
  * Cui et al. [2021] A. Cui, A. Sadat, S. Casas, R. Liao, and R. Urtasun, “LookOut: Diverse multi-future prediction and planning for self-driving,” _arXiv preprint arXiv:2101.06547_ , 2021.
  * Bajcsy et al. [2021] A. Bajcsy, A. Siththaranjan, C. J. Tomlin, and A. D. Dragan, “Analyzing human models that adapt online,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, 2021.
  * Dosovitskiy et al. [2017] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An Open Urban Driving Simulator,” in _Conference on Robot Learning (CoRL)_ , Mountain View, USA, Nov. 2017.
  * Chen et al. [2019] J. Chen, B. Yuan, and M. Tomizuka, “Deep imitation learning for autonomous driving in generic urban scenarios with enhanced safety,” _arXiv preprint arXiv:1903.00640_ , 2019.
  * Codevilla et al. [2019] F. Codevilla, E. Santana, A. M. López, and A. Gaidon, “Exploring the limitations of behavior cloning for autonomous driving,” in _International Conference on Computer Vision (ICCV)_. IEEE, 2019, pp. 9329–9338.
  * Tang [2019] Y. C. Tang, “Towards learning multi-agent negotiations via self-play,” in _International Conference on Computer Vision Workshops_ , 2019.
  * Palanisamy [2019] P. Palanisamy, “Multi-agent connected autonomous driving using deep reinforcement learning,” _arXiv preprint arXiv:1911.04175_ , 2019.
  * Hawke et al. [2020] J. Hawke, R. Shen, C. Gurau, S. Sharma, D. Reda, N. Nikolov, P. Mazur, S. Micklethwaite, N. Griffiths, A. Shah _et al._ , “Urban driving with conditional imitation learning,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 251–257.
  * Pomerleau [1989] D. A. Pomerleau, “ALVINN: An autonomous land vehicle in a neural network,” in _Neural Information Processing Systems (NeurIPS)_ , 1989, pp. 305–313.
  * Caccia et al. [2018] L. Caccia, H. Van Hoof, A. Courville, and J. Pineau, “Deep generative modeling of lidar data,” _arXiv preprint arXiv:1812.01180_ , 2018.
  * Dinh et al. [2017] L. Dinh, J. Sohl-Dickstein, and S. Bengio, “Density estimation using real NVP,” in _International Conference on Learning Representations (ICLR)_ , 2017. [Online]. Available: https://openreview.net/forum?id=HkpbnH9lx
  * Papamakarios et al. [2017] G. Papamakarios, T. Pavlakou, and I. Murray, “Masked autoregressive flow for density estimation,” in _Neural Information Processing Systems (NeurIPS)_ , 2017, pp. 2338–2347.
  * Singh et al. [2020] A. Singh, H. Liu, G. Zhou, A. Yu, N. Rhinehart, and S. Levine, “Parrot: Data-driven behavioral priors for reinforcement learning,” _arXiv preprint arXiv:2011.10024_ , 2020.
  * Rhinehart et al. [2019] N. Rhinehart, R. McAllister, K. Kitani, and S. Levine, “PRECOG: PREdiction CONditioned on Goals in Visual Multi-Agent Settings,” in _International Conference on Computer Vision (ICCV)_. IEEE, 2019, pp. 2821–2830.
  * Hill et al. [2018] A. Hill, A. Raffin, M. Ernestus, A. Gleave, A. Kanervisto, R. Traore, P. Dhariwal, C. Hesse, O. Klimov, A. Nichol, M. Plappert, A. Radford, J. Schulman, S. Sidor, and Y. Wu, “Stable baselines,” https://github.com/hill-a/stable-baselines, 2018.
  * Tran et al. [2019] D. Tran, K. Vafa, K. Agrawal, L. Dinh, and B. Poole, “Discrete flows: Invertible generative models of discrete data,” in _Neural Information Processing Systems (NeurIPS)_ , 2019, pp. 14 719–14 728.

##  Appendix A Appendix

###  A-A Implementing the MFP baseline

We were required to make several key changes to the publicly released MFP
codebase to create a usable MFP baseline for our contingency planning
scenarios in CARLA:

  1. 1.

The MFP codebase only includes code for the NGSIM dataset, so we added support
for training (and visualizing) models on CARLA datasets, in addition to adding
support for deploying the model in the CARLA simulator. Since MFP is a model
for prediction (not planning), the latter required implementing a planning
procedure to turn predictions from the MFP model into control for the ego
vehicle (see Appendix A-B).

  2. 2.

We added rotation of model inputs based on the each vehicle’s yaw as an
additional preprocessing stage, such that the reference frame for prediction
always starts with the ego vehicle at (0,0) and pointing in the +X direction
(the existing repository only shifts the inputs to (0,0)). We observed that
rotation of inputs was necessary for training on the left and right turn
scenarios.

  3. 3.

We removed the attention stage of the model architecture which significantly
improved model performance on our CARLA datasets (recall that the scenarios we
consider in this paper only include two agents).

  4. 4.

We removed the pretraining stage during model training (where the RNN/decoder
output sequence is generated in a non-interactive fashion) which also
significantly improved model performance.

A repository containing a version of the MFP codebase with the aforementioned
changes can be found on the project website.

An important difference between CfO and MFP is that with CfO, we can train a
single model on multiple scenarios, whereas with MFP, we are limited to
training a single model for each individual scenario. We were unable to train
MFP models on multiple scenarios that generated reasonable predictions (usable
for planning): we found that the mixed-scenario models would often generate
trajectories from the wrong scenario (e.g., a left turn on the right turn
scenario). Additionally, we found it necessary to tune hyperparameters per-
scenario, e.g., preprocessing with rotation is critical for the left and right
turn scenarios, but degrades performance significantly on the overtake
scenario.

###  A-B Planning with MFP

Similar to our behavior model described in Section III-B, MFP’s forward pass
(used during inference) generates predicted trajectories for $\mathbf{X}_{\leq
T}$. Moreover, MFP generates $K$ different trajectories for each vehicle,
where each trajectory $\mathbf{x}_{\leq T}^{a,k}$ pertains to a different
“mode” $k$ ($k\in 1,\dots,K$). According to the MFP authors, modes are meant
to represent semantically different types of driving behavior such as
intentions (e.g., left/right/straight) or behaviors (e.g.,
aggressive/conservative).

MFP’s multimodal prediction is implemented by using $K$ RNN decoders (one for
each mode, with the total numbers of modes fixed during training), which model
the future trajectories for all agents, conditioned on the past trajectories
of all agents, the context view (the trajectories and visual context both
processed by an encoder), and the mode:
$p(\mathbf{Y}^{a}|\mathbf{X},\mathcal{I},k)$, paramaterized by a 2D Gaussian
distribution over xy coordinates for each agent at every predicted timestep
$t$, i.e., $\mathcal{N}_{2}(\mu,\rho)$ represented by the 5-tuple
$(\mu^{a,t}_{X}$, $\mu^{a,t}_{Y}$, $\sigma^{a,t}_{X}$, $\sigma^{a,t}_{Y}$,
$\rho^{a,t})$. A given agent $a$’s history $\mathbf{X}^{a}$ and an attention-
based encoding of the history of other agents $Attn(\mathbf{X}^{i\neq{}a})$
are concatenated in a vector
$[\mathbf{X}^{a},Attn(\mathbf{X}^{i\neq{}a}),\mathcal{I}]$ and passed as input
to the encoding RNN, which produces a latent encoding and a Multinoulli
distribution over modes per-agent,
$p(K^{a}|\mathbf{X}^{a},Attn(\mathbf{X}^{i\neq{}a}),\mathcal{I})$. The latent
encoding is then input to each decoding RNN (one per mode) to generate $K$
predicted trajectories per agent. All agents share the same set of (encoder
and decoder) RNNs, so parameters scale linearly with modes, whereas the number
of agents scales the batch/input dimension.

To summarize, the outputs of the trained MFP model represent the following
distributions:

$p(\mathbf{Y}^{a}|\mathbf{X},\mathcal{I},k)$, a distribution over future
coordinates, per-agent, per-mode, generated by the decoding RNNs, and
$p(K^{a}|\mathbf{X},\mathcal{I})$, a distribution over modes per-agent,
generated by the encoding RNN. This means the model generates $K$ futures for
each agent, i.e., $K\times A$ total trajectory distributions.

Note that the MFP model outputs do not include an explicit joint trajectory
distribution $p(\mathbf{Y}|\mathbf{X},...)$; the conditional joint future is
factorized across agents, and across time (using the autoregressive decoder):

$p(\mathbf{Y}^{a}|\mathbf{X},\mathcal{I},k)=\prod_{t=1}^{T}\prod_{a=1}^{A}p(\mathbf{y}_{t}^{a}|\mathbf{Y}_{\leq
t},\mathbf{X},\mathcal{I},k^{a})$ (3)

We note that in Eq. 3 (and its original formulation in [17]), the joint is
conditioned on the (ego) agent’s own $k$, but not on the $k$s of other agents.
However, in the reference implementation of MFP111https://github.com/apple/ml-
multiple-futures-prediction/commit/402f82d (and our own code), the joint is
conditioned on all agents having the same $k$ value.

Planning using the same cost model as CfO requires explicit joint
trajectories. Since the MFP model outputs a distribution of $K$ trajectories
for each of the $A$ agents, to generate candidate joint trajectories
$\hat{\mathbf{Y}}$ in a two-agent setting, we can simply consider the set of
all $K\times K$ possible combinations of individual ego and actor
trajectories:

$\displaystyle\hat{\mathbf{Y}}$
$\displaystyle=[(\mu_{\mathbf{Y}^{ego}},\mu_{\mathbf{Y}^{actor}})~{}\text{for}~{}k^{ego},k^{actor}\in
K]$ (4)
$\displaystyle=[(\mu^{ego}_{X},\mu^{ego}_{Y},\mu^{actor}_{X},\mu^{actor}_{Y})~{}\text{for}~{}k^{ego},k^{actor}\in
K]$

In our MFP experiments we used 5 modes, so we consider 25 total candidate
joint trajectories. To select the best ego trajectory to use for planning, we
can select the ego portion of the joint with the lowest cost (highest reward),
weighted by the probability of each trajectory:

$\displaystyle{\mathbf{Y}^{ego}}^{\ast}=\operatorname{argmin}_{(\mu^{ego}_{X},\mu^{ego}_{Y})}{}$
$\displaystyle(Cost(\mu^{ego}_{X},\mu^{ego}_{Y},\mu^{actor}_{X},\mu^{actor}_{Y})$
(5) $\displaystyle\times p(K^{ego}=k^{ego}|\mathbf{X},\mathcal{I})$
$\displaystyle\times p(K^{actor}=k^{actor}|\mathbf{X},\mathcal{I}))$

Instead of weighting candidate joint trajectories by individual trajectory
probabilities, alternatively we can filter out unrealistic joint trajectories
by ignoring those with individual trajectory probabilities below a certain
threshold, e.g.:

$P(K^{ego}=k^{ego}|\mathbf{X},\mathcal{I})<0.01$

Assuming a perfect prediction model, both of these methods will naturally
create an _overconfident_ planner since we consider every possible combination
of ego and actor trajectories. To create an _underconfident_ planner (assuming
a perfect MFP model), we can choose the ego trajectory with the best worst-
case joint trajectory, i.e., we assume an adversarial actor that chooses the
actor trajectory leading to the worst performing joint, conditioned on the
choice of ego trajectory:

$\displaystyle{\mathbf{Y}^{ego}}^{\ast}=$
$\displaystyle\operatorname{argmin}_{(\mu^{ego}_{X},\mu^{ego}_{Y})}~{}max_{(\mu^{actor}_{X},\mu^{actor}_{Y})}~{}$
(6) $\displaystyle
Cost(\mu^{ego}_{X},\mu^{ego}_{Y},\mu^{actor}_{X},\mu^{actor}_{Y})$

Finally, the form of the MFP model is amenable to contingent planning, in
contrast to the action shooting originally described in [17].

Once we have selected an optimal ego trajectory, we input the chosen ego
trajectory to a PID controller to generate controls for the vehicle. In
practice we found the outputs of MFP trained on the CARLA dataset to be
imperfect, and observed that the underconfident planner is highly sensitive to
noisy predictions and would often generate control that lead to out-of-
distribution prediction. Therefore in our experiments we report results using
the (weighted probability) overconfident planner.

###  A-C Implementing the model-free RL baseline

For our model-free reinforcement learning baseline, we use the implementation
of Proximal Policy Optimization provided in the Stable Baselines repository
[37] (“PPO2”), and build on the OATomobile [7] repository to wrap each
scenario in an OpenAI Gym environment. The reward function used to train the
RL agent is a linear combination of a collision penalty (to penalize risky
behavior), constant timestep penalty (to encourage the agent to complete the
turn as fast as possible), and “lane-tracking” reward (to encourage the agent
follow a standard arc maneuver while turning). In practice we found the lane-
tracking reward to be critical for learning realistic driving behavior. We
experiment with two different action spaces, one where the agent only controls
the acceleration (steering is provided with an auto-pilot) which mirrors the
RL experimental setup in [17], and another more realistic setting where the
agent is also responsible for controlling steering and braking. Each episode
has a horizon of 200 steps but is terminated early if the agent completes the
turn (i.e., reaches a target location).

We had to make several significant changes to the OATomobile codebase to
enable RL training on our suite of contingency planning scenarios. Most
importantly, the original codebase only allows control of a single agent in
the CARLA simulator, i.e., the ego vehicle. However, our scenarios are multi-
agent: the actor vehicle has to dynamically respond to the ego vehicle’s state
in order to implement the scenario behavior trees (e.g., Figure 1). To allow
for training on a two-agent scenario, we modified the OATomobile API to take
actor actions (in addition to ego actions) at each timestep, which are
determined by the same behavior script described in Section IV.

Although we were able to train an agent with PPO that manages to achieve a 0%
collision rate and 100% success rate (using the restricted action space), we
observe that training is highly unstable: safe policies were quick to diverge
to degenerate solutions exhibiting highly overconfident behavior. We
hypothesize that additional reward shaping and hyperparameter tuning may be
able to stabilize training.

We were unable to learn a reasonable policy with RL using the larger (more
realistic) action space, where the agent controls steering and braking in
addition to acceleration. RL agents trained using the full action space
generally exhibit erratic and unrealistic driving behavior. We hypothesize
that additional reward shaping, post-processing of actions (e.g., smoothing in
action space), and a pre-training stage (e.g., using expert data, or the
restricted action space) may help in learning a more realistic policy.

###  A-D Visualizations of plans

Figure 6: Examples of contingent plans in the left turn and overtake task.
Each row corresponds to a contingent plan – a single robot $\mathbf{z}_{\leq
T}^{r}$ – and yields different joint trajectories when forward-simulated by
the model with an accompanying sample of $\mathbf{z}_{\leq T}^{h}$. Blue
denotes the forecasted robot trajectory; orange denotes the forecasted human
trajectory.

Figure 7: Examples of overconfident (left half) and underconfident (right
half) planning. In the left-turn and overtaking scenarios, the overconfident
planner believes the human (orange) will always yield to the robot (blue). The
underconfident planner believes that the robot cannot influence the human and
plans a suboptimal determinstic path.

###  A-E Representing contingencies

The model in Eq. 1 can be equivalently represented as an _autoregressive flow_
$q_{f}$, composed of learned bijections
$f=[f_{0}^{0},\dots,f_{0}^{A},\dots,f_{T}^{0},\dots,f_{T}^{A}]$ and base
distributions $\bar{q}(\mathbf{Z})=\bar{q}_{\leq T}^{1:A}(\mathbf{Z}_{\leq
T}^{1:A})$. Consider the discrete setting. Discrete flows learn both the
probability mass function $\bar{q}$ and $f$, and satisfy
$q_{f}(\mathbf{X}=\mathbf{x})\\!=\\!\bar{q}(\mathbf{Z}\\!\\!=\\!\\!f^{-1}(\mathbf{x}))$
[38]; in our multi-agent autoregressive case,
$\bar{q}(\mathbf{Z})\\!=\\!\prod_{t=1}^{T}\prod_{a=1}^{A}\bar{q}_{t}^{a}(\mathbf{Z}_{t}^{a})$.
This implies that by using $\mathbf{z}^{r}$ to parameterize contingency plans,
the space of contingency plans that this can represent is the set of sequences
of $n_{t}$-th “best responses” under the model. To see this fact, let
${}^{n_{t}}\mathbf{z}_{t}^{r}=\operatorname{argmax}_{\mathbf{z}^{t}_{r}\in\mathbb{Z}^{d}\setminus\\{{}^{1}\mathbf{z}_{t}^{r},\dots,{}^{n_{t}-1}\mathbf{z}_{t}^{r}\\}}\bar{q}_{t}^{r}$.
When $n_{t}=1$, ${}^{1}\mathbf{z}_{t}^{r}$ is the first best response at time
$t$, as judged by $\bar{q}_{t}^{r}$. When $n_{t}>1$,
${}^{n_{t}}\mathbf{z}_{t}^{r}$ is the $n_{t}$-th best response at time $t$.
Thus, at every time step $t$, a choice of $\mathbf{z}_{t}^{r}$ is identified
with the $n_{t}$-th best response ${}^{n}\mathbf{z}_{t}^{r}$. Thus, the space
of contingent plans is
$\\{{}^{n_{1}}\mathbf{z}_{1}^{r},\dots,{}^{n_{T}}\mathbf{z}_{T}^{r}:n_{t}\in\mathbb{N}\\}$;
the best contingency plan under the model is
${}^{1,\dots,1}\mathbf{z}^{r}_{\leq T}$. Therefore, the space of contingent
plans that a discrete autoregressive flow model can represent is relatively
flexible, as the contingent plans that this parameterization does not
represent are just those that have values of $n_{t}$ that are contingent on
the possible futures $\mathbf{X}_{1:t-1}$ (e.g. policies that perform the
first best response to partial future $X$ and the second best response to
partial future $Y$). Although our model is not discrete, these observations
lead us to speculate that there generally will exist $\mathbf{z}_{\leq T}^{r}$
for each scene that represent high-quality contingent plans; evidence from our
experiments support this speculation. An illustration of the contingencies
that a binary autoregressive flow can represent with $\mathbf{z}_{\leq T}^{r}$
is shown in Fig. 8.

Figure 8: A discrete autoregressive flow can represent contingency plans when
provided with a subset of all base distribution values; the provided values
represent the decisions that can be controlled/planned in a partially-
controlled system. The represented contingencies include the most-likely
responses at every time-step. In this case, the discrete autoregressive flow
model is
$q(\mathbf{X}=\mathbf{x})\\!=\\!\prod_{t=1}^{T=2}\prod_{i=1}^{A=2}\bar{q}_{t}^{i}(\mathbf{Z}_{t}^{i}=f_{t}^{-1,i}(\mathbf{x}_{t}^{i},\mathbf{x}_{<t}))$.
Agent $i$’s action at time $t$ is a random variable $\mathbf{X}_{t}^{i}$ that
assumes a value $\mathbf{x}_{t}^{i}\in\\{a_{t}^{i},b_{t}^{i}\\}$, with $i=r$
denoting the robot (controlled agent), and $i=h$ denoting the human
(uncontrolled agent). Blue nodes represent robot actions, orange nodes
represent human actions, and dark blue nodes represent the likelier of two
robot actions. Thick arrows denote the likelier of two actions under the
model. Colored edges denote specific contingency plans; solid colored edges
denote the representable contingencies, whereas gray-dashed colored edges
denote the unrepresentable contingencies. By choosing the base-space reactions
ahead of time ($\mathbf{z}_{t}^{r}$), this parameterization represents
reactions ordered by their probabilities
${}^{1}\mathbf{z}_{t}^{r}=\operatorname{argmax}\bar{q}_{t}^{r}$,
${}^{2}\mathbf{z}_{t}^{r}=\operatorname{argmax}\bar{q}_{t}^{r}~{}\mathrm{s.t.}~{}{{}^{2}\mathbf{z}_{t}^{r}\neq{}^{1}\mathbf{z}_{t}^{r}}\implies\bar{q}_{t}^{r}({}^{1}\mathbf{z}_{t}^{r})>\bar{q}_{t}^{r}({}^{2}\mathbf{z}_{t}^{r})$.
Thus it cannot represent contingencies with model probability ordering that
depend upon future data, but this is not a significant limitation. Note again
that the representable contingencies include the n-most-likely responses at
every timestep.

###  A-F Planning criterion derivation

We derive the planning criterion of Eq. 2 as a MAP estimation of a scene-
conditioned posterior of policy parameters, $p(\mathbf{z}_{\leq
T}^{r}|\mathcal{G},{\mathbf{o}})$.

$\displaystyle\operatorname{argmax}_{\mathbf{z}_{\leq
T}^{r}}p(\mathbf{z}_{\leq T}^{r}|\mathcal{G},{\mathbf{o}})$
$\displaystyle=\operatorname{argmax}_{\mathbf{z}_{\leq
T}^{r}}\log\,p(\mathcal{G},\mathbf{z}_{\leq T}^{r}|{\mathbf{o}})\,-\,{\log
p(\mathcal{G}|{\mathbf{o}})}$ (7)
$\displaystyle=\operatorname{argmax}_{\mathbf{z}_{\leq
T}^{r}}\\!\\!\log\\!\\!\int\\!\\!p(\mathcal{G}|\mathbf{z}_{\leq
T}^{r},\\!\mathbf{z}^{h}\\!\\!\\!,{\mathbf{o}}\\!)p(\mathbf{z}_{\leq
T}^{r},\\!\mathbf{z}^{h}|{\mathbf{o}}\\!)p(\mathbf{z}^{h}\\!|{\mathbf{o}}\\!)\mathrm{d}\mathbf{z}^{h}$
(8) $\displaystyle=\operatorname{argmax}_{\mathbf{z}_{\leq
T}^{r}}\log\mathbb{E}_{p({\mathbf{z}}^{h}|{\mathbf{o}})}p(\mathcal{G}|\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h},{\mathbf{o}})p(\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h}|{\mathbf{o}})$ (9)

where between Eq. 7 and Eq. 8 we drop the term $\log
p(\mathcal{G}|{\mathbf{o}})$ since it is independent of $\mathbf{z}_{\leq
T}^{r}$. Now, we incorporate the learned prior of expert behavior
$q_{\theta}(\mathbf{X}\\!=\\!\mathbf{x}|{\mathbf{o}})$ by defining the prior
over policy parameters and human stochasticity $p(\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h}|{\mathbf{o}})\\!\doteq\\!q_{\theta}(\mathbf{X}\\!=\\!f(\mathbf{z}^{r}_{\leq
T},\mathbf{z}^{h})|{\mathbf{o}})$. We incorporate the goals $\mathcal{G}$ in
terms of two distributions: $p(\mathcal{G}|\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h},{\mathbf{o}})\doteq p(\mathbf{g}|\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h},{\mathbf{o}})\delta_{\mathbb{G}}(\mathbf{x})$, with
$p(\mathbf{g}|\mathbf{z}_{\leq
T}^{r},\mathbf{z}^{h},{\mathbf{o}})\doteq\mathcal{N}(f(\pi^{r}_{\mathbf{z}_{\leq
T}},\mathbf{z}^{h})_{T}^{r};\mathbf{g},I)$ – this favors
$\pi^{r}_{\mathbf{z}_{\leq T}^{r}}$ that tend to end near $\mathbf{g}$.
Finally, we use $p(\mathbf{z}^{h}|{\mathbf{o}})\doteq\mathcal{N}(0,I)$, which
is the model’s prior over human stochasticity. In practice, we perform
stochastic gradient ascent on a numerically version of the criterion in Eq. 9
that swaps the ordering of $\log$ and $\mathbb{E}$ (by Jensen’s inequality) to
arrive at a lower-bound, and approximates a violated constraint
($\log\delta_{\mathbb{G}}(\mathbf{x})\\!=\\!-\infty$) with a large negative
value. This final planning criterion is used to implement Contingencies from
Observations (CfO), and is reproduced in Eq. 10.

$\displaystyle\mathcal{L}_{\text{{CfO}}}(\pi^{r}_{\mathbf{z}_{\leq T}})=$ (10)
$\displaystyle\mathop{\mathbb{E}}_{\mathbf{z}^{h}\sim\mathcal{N}(0,I)}\Big{[}\log\underbrace{q_{\theta}(\bar{\mathbf{x}}_{\leq
T}|{\mathbf{o}})}_{(1)~{}\text{prior}}\\!+\\!\log\underbrace{\mathcal{N}\big{(}\bar{\mathbf{x}}^{r}_{T};\mathbf{g},I\big{)}}_{(2)~{}\text{destination}}\\!+\\!\log\underbrace{\delta_{\mathbb{G}}(\bar{\mathbf{x}}_{\leq
T})}_{(3)~{}\text{constraint}}\Big{]}.$

###  A-G Theoretical Justification for Contingency Planning

Here we demonstrate why value increases if our planning considers
contingencies, rather than only planning a single state sequence. We
additionally show the benefit of active planning, where the robot is known to
affect other agents. Consider planning just two time steps into the future as
visualized in Fig. 2. Both the “No leader” and “Robot leader” methods plan
full state trajectories open-loop, with associated value functions
$Q^{\text{NL}}$ and $Q^{\text{RL}}$. By contrast, the contingent planners
(“Human leader” and “Co-leaders”, with values $Q^{\text{HL}}$ and
$Q^{\text{CL}}$) understand that future decisions like $\mathbf{x}^{r}_{2}$
depend on future information, like the value of $\mathbf{x}^{h}_{1}$, which is
not yet known. Below we show the value functions corresponding to each
planner. We use the hat symbol $\hat{Q}$ to reflect the estimated value
function that each planner optimizes, an estimate which is based on different
modelling assumptions about how multi-agent interaction occurs:

$\displaystyle\hat{Q}^{\text{NL}}({\mathbf{o}},\mathbf{x}^{r}_{1})$
$\displaystyle\doteq\max_{\mathbf{x}^{r}_{2}}\,{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}|{\mathbf{o}}}}\,{\color[rgb]{1,.5,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1},{\mathbf{o}}}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1,2})\Big{]},$ (11)
$\displaystyle\hat{Q}^{\text{RL}}({\mathbf{o}},\mathbf{x}^{r}_{1})$
$\displaystyle\doteq\max_{\mathbf{x}^{r}_{2}}\,{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}|{\mathbf{o}}}}\,{\color[rgb]{0,0.88,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{r}_{1},\mathbf{x}^{h}_{1},{\mathbf{o}}}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1,2})\Big{]},$ (12)
$\displaystyle\hat{Q}^{\text{HL}}({\mathbf{o}},\mathbf{x}^{r}_{1})$
$\displaystyle\doteq{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}|{\mathbf{o}}}}\,\max_{\mathbf{x}^{r}_{2}}\,{\color[rgb]{1,.5,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1},{\mathbf{o}}}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1,2})\Big{]},$ (13)
$\displaystyle\hat{Q}^{\text{CL}}({\mathbf{o}},\mathbf{x}^{r}_{1})$
$\displaystyle\doteq{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}|{\mathbf{o}}}}\,\max_{\mathbf{x}^{r}_{2}}\,{\color[rgb]{0,0.88,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{r}_{1},\mathbf{x}^{h}_{1},{\mathbf{o}}}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1,2})\Big{]}.$ (14)

#### Case for contingency planning

For any $({\mathbf{o}},\mathbf{x}^{r}_{1})$, we have
$\hat{Q}^{\text{NL}}\leq\hat{Q}^{\text{HL}}$ and
$\hat{Q}^{\text{RL}}\leq\hat{Q}^{\text{CL}}$ due to Jensen’s inequality,
noting the maximum operator is convex. More intuitively, by moving a max
operator after the blue expectation operator, the value function can realize
the “best of all worlds”, by planning optimal contingencies for each future
outcomes. By contrast, a max operator before the expectation computes
evaluates the single best “compromise” decision $\mathbf{x}^{r}_{2}$ that is
common to all possible values of the preceding human state
$\mathbf{x}^{h}_{1}$.

#### Case for active contingency planning

Note $\hat{Q}$ denotes the value function that each planner aims to optimize,
but is not necessarily the “true value” of such a planner (denoted $Q$) if
$\hat{Q}$ was based on erroneous assumptions. In Eqs. 11, 12, 13 and 14 the
orange expectation operator is based on a incomplete behavior model that
predicts $\mathbf{x}^{h}_{2}$ given $(\mathbf{x}^{h}_{1},{\mathbf{o}})$, even
though $(\mathbf{x}^{h}_{1},{\mathbf{o}})$ is not the Markov state, since it
omits the robot’s influence on the human. The full Markov state to predict the
next human state is featured in the green expectation operator, which assumes
a behavior model to predict $\mathbf{x}^{h}_{2}$ given all the information:
$(\mathbf{x}^{r}_{1},\mathbf{x}^{h}_{1},{\mathbf{o}})$. We thus consider the
green operator to reflect a behavior model that is more complete, and faithful
to how reality will progress, compared to the orange operator. Thus, we have
$\hat{Q}^{\text{RL}}=Q^{\text{RL}}$ and $\hat{Q}^{\text{CL}}=Q^{\text{CL}}$,
but the same cannot generally be said for $\hat{Q}^{\text{NL}}$ and
$\hat{Q}^{\text{HL}}$.

With respect to the random variable of the orange expectation, we can expand
it:

$\displaystyle p(\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1},{\mathbf{o}})$
$\displaystyle=\int\\!p(\mathbf{x}^{h}_{2},\mathbf{x}^{r^{\prime}}_{1}\\!|\mathbf{x}^{h}_{1},{\mathbf{o}})\text{d}\mathbf{x}^{r^{\prime}}_{1}$
$\displaystyle=\int\\!p(\mathbf{x}^{h}_{2}|\mathbf{x}^{r^{\prime}}_{1}\\!,\mathbf{x}^{h}_{1},{\mathbf{o}})p(\mathbf{x}^{r^{\prime}}_{1}\\!|{\mathbf{o}})\text{d}\mathbf{x}^{r^{\prime}}_{1}$
$\displaystyle=\,\mathbb{E}_{\mathbf{x}^{r^{\prime}}_{1}\\!|{\mathbf{o}}}\\!\left[p(\mathbf{x}^{h}_{2}|\mathbf{x}^{r^{\prime}}_{1}\\!,\mathbf{x}^{h}_{1},{\mathbf{o}})\right].$

Thus we can represent
${\color[rgb]{1,.5,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1},{\mathbf{o}}}}={\color[rgb]{1,0,0}\mathbb{E}_{\mathbf{x}^{r^{\prime}}_{1}\\!|{\mathbf{o}}}}{\color[rgb]{0.83,0.69,0.22}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{r^{\prime}}_{1}\\!,\mathbf{x}^{h}_{1},{\mathbf{o}}}}$
where $\mathbf{x}^{r^{\prime}}_{1}$ represents the robot state that was
implicitly integrated-out at training time, instead of being explicitly
conditioned on. This implicit variable $\mathbf{x}^{r^{\prime}}_{1}$ is
distinct from the robot-state at test-time $\mathbf{x}^{r}_{1}$ which the
planner optimizes. This way of re-framing Eq. 13 frames the human-leader model
as omitting the known (planned) value of $\mathbf{x}^{r}_{1}$ at test-time
when predicting $\mathbf{x}^{h}_{2}$ during planning, and instead reverting to
the prior distribution of robot states seen at training times:
$p(\mathbf{x}^{r^{\prime}}_{1}\\!|{\mathbf{o}})$. Omitting known information
reduces the value of such a planner. The “true” value of the human-leader
planner can be computed using $Q^{\text{CL}}$ given $Q^{\text{CL}}$’s
definition assumes the correct process (green operator) of how
$\mathbf{x}^{h}_{2}$ is generated:

$\displaystyle V^{\text{HL}}({\mathbf{o}})$
$\displaystyle=Q^{\text{CL}}\big{(}{\mathbf{o}},\,\operatorname{argmax}_{\mathbf{x}^{r}_{1}}\hat{Q}^{\text{HL}}({\mathbf{o}},\mathbf{x}^{r}_{1})\big{)}$
(15) $\displaystyle\leq
Q^{\text{CL}}\big{(}{\mathbf{o}},\,\operatorname{argmax}_{\mathbf{x}^{r}_{1}}Q^{\text{CL}}({\mathbf{o}},\mathbf{x}^{r}_{1})\big{)}=V^{\text{CL}}({\mathbf{o}}),$

where we define a corresponding $V$-function for each $Q$-function in Eqs. 11,
12, 13 and 14:

$\displaystyle V({\mathbf{o}})\;$
$\displaystyle\doteq\;\max_{\mathbf{x}^{r}_{1}}\,Q({\mathbf{o}},\mathbf{x}^{r}_{1}).$
(16)

By analogous reasoning, $V^{\text{NL}}({\mathbf{o}})\leq
V^{\text{RL}}({\mathbf{o}})$, meaning active planning is beneficial among non-
contingent planners too: whenever the robot considers how its actions affect
the world, and those effects have relevant repercussions in the form of
objective rewards, the planner can simulate how robot actions can such
repercussions to achieve a higher return.

#### Summary

The benefit of (1) contingency planning, and (2) active planning discussed
above, results in a partial ordering of the true values of each planning
category seen in Fig. 2:

$\displaystyle
V^{\text{NL}}\;\;\leq\;\;\\{V^{\text{RL}},V^{\text{HL}}\\}\;\;\leq\;\;V^{\text{CL}},$
(17)

noting the value of active contingency planning is greater-or-equal to all
other planning methods.

#### T-step $Q$-values

In a more general horizon of $T$ time-steps, the various $Q$-values are below.
For brevity, we do not show the conditioning on $\mathbf{o}$, and treat it as
implicit.

$\displaystyle\hat{Q}^{\text{NL}}(\mathbf{x}^{r}_{1})$
$\displaystyle\doteq\max_{\mathbf{x}^{r}_{2}}\max_{\mathbf{x}^{r}_{3}}\cdots\max_{\mathbf{x}^{r}_{T}}\,{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}}}{\color[rgb]{1,.5,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1}}}\cdots\mathbb{E}_{\mathbf{x}^{h}_{T}|\mathbf{x}^{h}_{1:T-1}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1:T})\Big{]},$
$\displaystyle\hat{Q}^{\text{RL}}(\mathbf{x}^{r}_{1})$
$\displaystyle\doteq\max_{\mathbf{x}^{r}_{2}}\max_{\mathbf{x}^{r}_{3}}\cdots\max_{\mathbf{x}^{r}_{T}}{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}}}{\color[rgb]{0,0.88,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{r,h}_{1}}}\cdots\mathbb{E}_{\mathbf{x}^{h}_{T}|\mathbf{x}^{r,h}_{1:T-1}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1:T})\Big{]},$
$\displaystyle\hat{Q}^{\text{HL}}(\mathbf{x}^{r}_{1})$
$\displaystyle\doteq{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}}}\max_{\mathbf{x}^{r}_{2}}{\color[rgb]{1,.5,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{h}_{1}}}\max_{\mathbf{x}^{r}_{3}}\cdots\max_{\mathbf{x}^{r}_{T}}\mathbb{E}_{\mathbf{x}^{h}_{T}|\mathbf{x}^{h}_{1:T-1}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1:T})\Big{]},$
$\displaystyle\hat{Q}^{\text{CL}}(\mathbf{x}^{r}_{1})$
$\displaystyle\doteq{\color[rgb]{0,0,1}\mathbb{E}_{\mathbf{x}^{h}_{1}}}\max_{\mathbf{x}^{r}_{2}}{\color[rgb]{0,0.88,0}\mathbb{E}_{\mathbf{x}^{h}_{2}|\mathbf{x}^{r,h}_{1}}}\max_{\mathbf{x}^{r}_{3}}\cdots\max_{\mathbf{x}^{r}_{T}}\mathbb{E}_{\mathbf{x}^{h}_{T}|\mathbf{x}^{r,h}_{1:T-1}}$
$\displaystyle\Big{[}\text{return}(\mathbf{x}^{r,h}_{1:T})\Big{]}.$