Online Decision-Making for Scalable Autonomous Systems

1 Introduction

There has been substantial progress with planning under uncertainty in partially observable, but fully modeled worlds. However, few effective formalisms have been proposed for planning in open worlds with an unspecified, large number of objects. This remains a key challenge for autonomous systems, particularly for autonomous vehicles (AVs). AV research has advanced rapidly since the DARPA Grand Challenge [Thrun et al., 2006], which acted as a catalyst for subsequent work on low-level sensing [Sivaraman and Trivedi, 2013] and control [Dolgov et al., 2010], as well as high-level route planning [Wray et al., 2016a].

A critical missing component to enable autonomy in long-term urban deployments is the mid-level intersection decision-making (e.g., the second-to-second stop, yield, edge, or go decisions). As in many robotic domains, the primary challenges include the sheer complexity of real-world problems, wide variety of possible scenarios that can arise, and unbounded number of multi-step problems that will be actually encountered, perhaps simultaneously. These factors have limited the deployment of existing methods for mid-level decision-making [Ulbrich and Maurer, 2013; Brechtel et al.,

2014; Bai et al., 2015; Jo et al., 2015]. We present a scalable, realistic solution, with strong mathematical foundations, via decomposition into problem-specific decision-components.

Our primary motivation is to provide a general solution for AV decision-making at any intersection, including n-way stops, yields, left turns at green traffic lights, right turns at red traffic lights, etc. In this domain, the AV approaches the intersection knowing only the static features from the map, such as road, crosswalk, and traffic controller information. Any number of vehicles and pedestrians can arrive and interact around the intersection, all potentially relevant to decision-making and unknown a priori. The AV must make mid-level decisions, using very limited hardware resources, including when to stop, yield, edge forward, or go, based on all possible interactions among all vehicles including the AV itself. Vehicles can be occluded, requiring the use of information gathering actions based on belief over partial observability. Pedestrians can jaywalk, necessitating that motion forward is taken only under strong confidence they will not cross. Uncertainty regarding priority and right-of-way exists, and must be handled under stochastic changes. Vehicles and pedestrians can block one another's motion, and AV-related blocking conflicts must be discovered and resolved via motion-based negotiation.

We provide a general solution for domains concerning multiple online decision-components with interacting actions (MODIA). For the particularly difficult AV intersection decision domain, MODIA considers all vehicles and pedestrians as separate individual decision-components. Each component is a partially observable Markov decision process (POMDP) that maintains its own belief for that particular component problem and proposes an action to take at each time step. MODIA then employs an executor function to act as an action aggregator to determine the actual action taken by the AV. This decomposition enables a tractable POMDP solution, benefiting from powerful belief-based reasoning while only growing linearly in the number of encountered problems.

The primary contributions include: a formal definition of MODIA (Section 3), a rigorous analysis of the complexity and regret-minimization properties (Section 4), an AV intersection decision-making MODIA solution (Section 5), and an evaluation of the approach in simulation as well as integration with a real AV (Section 6). We begin with a review of POMDPs (Section 2), and conclude with a survey of related work (Section 7) and final reflections (Section 8).

2 BackgroundMaterial

A partially observable Markov decision process (POMDP) is represented by the tuple 〈S,A,Ω,T,O,R〉 [Kaelbling et al., 1998]. S is a finite set of states. A is a finite set of actions. Ω is a finite set of observations. T :S×A×S→[0, 1] is a state transition function such that T(s,a,s′ )=Pr(s′ |s,a). O:A×S×Ω→[0,1] is an observation function such that O(a,s′ ,ω)=Pr(ω|a,s′ ). R:S×A→R is a reward function. The agent does not observe the true state of the system, and instead makes observations while maintaining a belief over the true state denoted b∈△|S| . Given action a∈A and subsequent observation ω∈Ω, belief b is updated to b′ with: b′ (s′ )=ηO(a,s′ ,ω) ∑s T(s,a,s′ )b(s) for all s′ ∈S, with normalizing constant η. A policy maps beliefs to actions π:△|S| →A. (Note: △n is the standard n-simplex.) The value function V :△|S| →R for a belief is the expected reward given a fixed policy π, a discount factor γ∈[0,1], and a horizon h. Also, it is useful to define the Q-value of belief b given action a as Q:△|S| ×A→R with V (b)= Q(b,π(b)). Since V π is piecewise linear and convex, we describe it using sets of α-vectors Γ={α1, . . . ,αr} with each αi=[αi(s1), . . . ,αi(sn)]T and αi(s) denoting value of state s∈S. The objective is to find optimal policy π∗ that maximizes V denoted as V ∗ . Given an initial belief b0 , V ∗ can be iteratively computed for a time step t, expanding beliefs at each update resulting in belief b, by maximizing:

3 ProblemFormulation

We begin with a general problem description that considers a single autonomous agent that encounters any number of decision problems online during execution. This paper focuses on collections of POMDPs primarily for their general form, self-consistency, and space limitations. It can be generalized to other decision-making models in the natural way. Finally, Figure 1 depicts a complete MODIA example for AVs, and is referenced throughout this section for each concept.

3.1 Decision-Making withMODIA

The multiple online decision-components with interacting actions (MODIA) model describes a realistic single-agent online decision-making scenario defined by the tuple 〈P,A〉. P ={P1, . . . ,Pk} are decision-problems (DPs) that could be encountered during execution. For this paper, each Pi∈P is a POMDP with Pi=〈Si,Ai,Ωi,Ti,Oi,Ri〉 (Section 2) starting from an initial belief b0i ∈△|Si| . We consider discrete time steps t∈N over the agent's entire lifetime. A={a1, . . . ,az} are z primary actions that are the true actions taken by the agent that affect the state of the external system environment. Importantly, only P and A are known offline a priori.

AV Example Figure 1 has two pre-solved intersection decision-components: single vehicle (P1) or pedestrian (P2).

Each are POMDPs with actions (recommendations) 'stop' or 'go'. Primary actions A for the AV are also 'stop' or 'go'.

Online, the DPs are instantiated based on what the agent experiences in the external system environment. Due to the nature of actually executing multiple decision-making models (e.g., POMDPs) in real applications, there is no complete model for which, when, or how many DPs are instantiated, or even how long they are relevant.

Formally, the online instantiations in MODIA are defined by the tuple 〈C,φ,τ〉. Over the agent's lifetime, there are n DP instantiations called decision-components (DCs) denoted as C={C1, . . . , Cn}, with both C and n unknown a priori. Let φ:C→P denote the DP for each instantiation. Let τ :C→N×N be the two time steps that each DC is instantiated and terminated. For notational convenience, for all Ci∈C, let τs(Ci) and τe(Ci) be the start and end times; we have τs(Ci)<τe(Ci). Without loss of generality, we also assume for i<j, τs(Ci)≤τs(Cj). We call a DC Ci∈C instantiated at time step t∈N if t∈[τs(Ci),τe(Ci)]. Any instantiated Ci ∈C includes POMDP φ(Ci), its policy πi :△|Si| →Ai, and its current belief state bti i ∈△|Si| with local POMDP time step ti =t-τs(Ci).

AV Example (Continued) Online, the AV encounters an intersection and immediately (at time step 1) observes two vehicles and one pedestrian. Three DCs are instantiated; C1 and C2 are for each vehicle (φ(C1)=φ(C2)=P1), and C3 is for the pedestrian (φ(C3)=P2). The start times for all Ci are τs(Ci)=1; the end times τe(Ci) are still unknown. Each POMDP Ci, with φ(Ci)=Pj: b0i =b0j , ti=1, and πi=πj.

3.2 The MODIA Executor

With DPs and primary actions 〈P,A〉 (known a priori), and online execution of DCs 〈C,φ, τ〉 (unknown a priori), the primary actions taken from A are determined by an action executor function ϵ: ¯ A→A with ¯ A=(⋃i Ai)∗ . (Note: X∗ is a Kleene operator on a set X, and Ai is the set of actions for the POMDP from DP Pi.) The executor takes DC action recommendations and converts them to a primary action taken by the agent in the external system environment. It also converts a primary action back to what that decision meant to individual DCs via their action sets. In this paper, we use the notation ϵ-1 :A→ ¯ A with ϵ-1 i (a) referring to an individual Ci's action from POMDP φ(Ci) for some a∈A.

It is important to note the requirement that the executor function ϵ must be able to map any tuple of actions taken from any combination of DPs, with any number of possible duplicates, to a primary action. MODIA is a class of problems that operates without any knowledge about which (or how many) DPs will be instantiated online.

AV Example (Continued) In Figure 1, all three DCs produce an action 〈¯a1,¯a2,¯a3〉=¯a∈ ¯ A at each time step. The example states ¯a1=¯a3=stop and ¯a2=go. The executor ϵ decides from ¯a that stop∈A will be the primary action. It informs each DC Ci what the primary action means to Ci individually, simply ϵ-1 i (stop)=stop, for belief updates.

3.3 The MODIAObjective

The goal of the class of problems captured by MODIA is to design the DPs, primary action set, and executor so that it solves the online real-world problem (e.g., AVs). Prior work on single-POMDP online algorithms experimentally analyze their performance with simpler metrics such as average discounted reward (ADR) or run time [Somani et al., 2013; Kurniawati and Yadav, 2016], and richer metrics such as error bound reduction (EBR) or lower bound improvement (LBI) [Ross et al., 2008]. MODIA is an online multi-POMDP model that differs from these previous online single-POMDP solvers. We instead provide a concrete objective function to enable the analysis of this complex online problem within a theoretical context. Our problem domain does not contain a model for how DPs are instantiated as DCs, nor how long DCs remain active. Thus, the objective is to minimize regret experienced at each step for any given DC instantiations.

Formally, for 〈P,A,C,φ,τ,ϵ〉, let h≤τe(Cn) be a horizon, let I t ={i∈{1, . . . ,n}|τs(Ci)≤t≤τe(Ci)} denote the set of indexes for instantiated DCs, and let executor decision ϵ(¯a)= at at time t∈{1, . . . ,h} with primary action at ∈A and the tuple of all instantiated DC's actions ¯a∈ ¯ A, so for all i∈I t , ¯ai =πi(bti i ) with πi, ti, and bti i from instantiated DC Ci∈C. The total regret Rhϵ ∈R is:

We refer to the regret at time t for all instantiated DCs in I t as rtϵ . Informally, a DC's regret in MODIA is the expected reward following the DC's desired policy's action, minus the realized expected reward following the executor's action.

AV Example (Continued) Executor ϵ selected stop∈A, which has ϵ-1 i (stop)=stop for all Ci∈C. Following each DC's desired action, only C2 chose go instead. This induces regret equal to Q2(bt2 2 ,go)-Q2(bt2 2 ,stop)≥0; C1 and C3 have 0 regret. Rtϵ is updated accordingly.

3.4 LEAF for MODIA

So far we have described the general form of MODIA using a general executor. Now we examine a particular kind of executor with desirable regret-minimizing properties (shown in Section 4). Specifically, we can define a lexicographic preference over the individual actions suggested by each DC. Thus, each DC suggests an action, stored collectively as a tuple of action recommendations, and the executor only executes the best (in terms of preference) action from this set.

A lexicographic executor action function (LEAF) has two requirements regarding a MODIA's structure in 〈P,A〉. First, let the primary actions A be factored with the unique action sets from among the DPs; formally, A=×iΛi with Λ= ⋃j {Aj}. Second, let ≻i be a lexicographic ordering over actions in these unique action sets Λi ∈Λ. If a MODIA satisfies these two requirements, then for all ¯a=〈¯a1, . . . ,¯ax〉∈ ¯ A and a=〈a1, . . . , ay〉∈A, LEAF ϵ(¯a)=a is defined by:

for all Λi∈Λ, and ϵ(∅)=a for some fixed a∈A. Informally, ¯a are the current desired actions from DCs, Λi is the unique action set, a are the resulting actions, and each ai (from matching unique action set Λi) has the highest preference following ≻i from the available voted-upon actions. Similarly, the inverse executor extracts the relevant action factor taken by the system and distributes it to all DCs who have that action set; formally, for all Ci∈C, with φ(Ci)=Pℓ, there exists an action ¯aj ∈Λj =Aℓ such that for the primary action taken a∈A, ϵ-1 i (a)=¯aj. In summary, LEAF simply takes the most preferred action among those available.

AVExample (Continued) In the AV example, we have action sets {stop,go}=A1=A2=A=Λ1. Thus, it satisfies the first requirement: primary actions are composed of DP actions. For the second, we define a lexicographic preference ≻1 (encouraging safety) over Λ1 with stop≻go. Now ϵ in Figure 1 is actually LEAF. Namely, the action stop is the most preferred action desired among only the actions selected by the DCs. Thus, stop is the result of the executor.

3.5 Risk-Sensitive MODIA

Now we also consider a specific kind of MODIA, with a form of monotonicity in an ordered relationship over actions and Q-values. Informally, we require DP's Q-values to be monotonic over actions with a penalty for selecting policy-violating high-risk actions. Formally, a MODIA is risk-sensitive with respect to a preference ≻i, if for all j, b, a, and a′ : (1) if a≻i a′ ⪰i πj(b) then Qj(b,a)≤Qj(b,a′ ), (2) if πj(b)≻i a then Qj (b, a)≤Q for sufficient penalty Q.

AV Example (Continued) Action stop makes no progress towards the goal while go does, so long as go is optimal, resulting in (1). Conversely, performing go when stop is optimal produces a severe expected cost, resulting in (2).

4 Theoretical Analysis

Given DPs and primary actions 〈P,A〉, MODIA requires the selection of an executor to minimize regret accumulated over time, in addition to solving the DPs themselves. With n unknown a priori, as well as which and when DPs are instantiated as DCs, it is impossible to perform tractable planning techniques entirely offline; again, MODIA is an category of online decision-making scenarios. Assume, however, that a prescient oracle provided 〈C,φ,τ〉 a priori. While this is an impossible scenario, it is useful to understand the worst-case complexity of exploiting this information in the underlying problem of selecting a regret-minimizing executor given this normally unobtainable information. Proposition 1 formally proves this complexity.

Proposition 1. If 〈C,φ,τ〉 is known a priori, then the complexity to compute the optimal executor ϵ∗ is O(n2 zmh) with z=|A|, m=maxi |Ai|, and h=maxi τe(Ci).

Proof. Must determine the worst-case complexity to fully define executor ϵ∗ : ¯ A→A to minimize regret Equation 1. In the worst-case, we must explore all relevant executors, and compute the regret for each, resulting in the optimal solution.

By executor definition in Section 3.2, ¯ A=(⋃i Ai)∗ and z=|A|. Given n=|C|, the maximum realizable set size of ¯ A is all unique potential actions, multiplied by the maximal number of unique DCs instantiated simultaneously. In the worst-case, Ai ̸=Aj for all i̸=j, so all possible actions must be considered for each; this order bound is m=maxi |Ai|. Also, all combinations of instantiated DCs must be realized, so all τ(Ci)̸=τ(Cj) for all i̸=j. In any order, n births, n deaths, and time no DCs instantiated; thus there are 2n+1 in total. Hence, the number of potential executors is O(znm).

In the worst-case scenario, Ri(bti i ,πi(bti i )) differs for every time step for all Ci∈C. Equation 1 requires O(hmaxt I t ) operations. Given C, h=maxi τe(Ci). By definition of I t , maxt I t ≤n. Thus, the worst-case complexity to compute an optimal ϵ∗ is O(znm)·O(hn)=O(n2 zmh).

With Proposition 1, we know this impossible oracular scenario's complexity is relatively high, but not exponential. This suggests a method for computing an optimal executor, under more realistic assumptions. Thus, let ˆ ρ be a given model for the hardest feature of MODIA: online instantiation. Let ˆ ρ: ˆNn× ˆ Tn× ˆEn× ˆNn× ˆ Tn →[0, 1]

define the probability that a particular set of instantiated DCs 〈ˆn, ˆ τ〉∈ ˆNn× ˆ Tn, and executor selection ˆ ϵ∈ ˆEn, results in a successor DC instantiation state 〈ˆn′ , ˆ τ ′ 〉∈ ˆNn× ˆ Tn. Here, ˆNn={1, . . . ,k}n are instantiation indexes (defining φ), ˆ Tn ={ˆ τ ∈{α, {1, . . . , h}2 , ω}n |∀i ∈N, ˆ τis < ˆ τie} are the instantiation start and end times (defining τ) including noninstantiated α and completed ω demarcations, and ˆEn={ϵ: ¯ A→A|| ¯ A|≤n} are all valid executors (defining ϵ). Additionally, we must assume knowledge of a maximum number of DCs n and horizon h for decidability. Given this model, Proposition 2 proves the resulting MDP's optimal policy minimizes expected regret, and that the problem is unfortunately computationally intractable in practice.

Proposition 2. If n, h, and model ˆ ρ are known a priori, then: (1) the resulting MDP's optimal policy π∗ minimizes expected regret, and (2) its state space is exponential in n and k.

Proof. We must show the construction of an MDP whose optimal policy minimizes expected regret and show its complexity in the necessity of an exponential state space.

Let 〈 ˆ S, ˆ A, ˆ T, ˆR〉 be a finite horizon MDP with horizon ˆh=h+1. States are ˆ S ={ˆ s0 }∪ ˆEn× ˆBn× ˆ Tn with ˆ s0 denoting the initial executor selection state and ˆBn={ ˆB∈ (⋃i ˆBh i )∗ || ˆB|=n} be all possible reachable beliefs for Pi in horizon h (denoted ˆBh i ) for all possible instantiations. For notation, we use ˆ s= 〈ˆ ϵ,ˆb, ˆ τ 〉, each containing instantiated values ˆ ϵi, ˆbi, ˆ τsi, and ˆ τei, as well as ˆ θ : ˆBn→ ˆNn mapping beliefs to their original POMDPs' indices. Actions are executor selection ˆ A= ˆEn. State transitions ˆ T : ˆ S× ˆ A× ˆ S→[0,1] have two cases. First, ˆ T (ˆ s0 , ˆa, ˆ s′ ) = [ˆ s′ =〈ˆa, ∅, ∅〉] captures executor selection. Second, for ˆ s ̸= ˆ s0 we have:

with j=ˆ θi(ˆb). This captures executor state assignment, the instantiation model ˆ ρ, the proper initialization of belief, the belief update for active DCs, and the termination of a DC. Rewards ˆR: ˆ S× ˆ A→R describe the negative regret, ˆR(ˆ s, ˆa) = ∑i Qj (ˆbi, ˆ ϵ-1 i (at ))-Qj(ˆbi,πj(ˆbi))[ˆ τi ∈ N] with R(ˆ s0 ,ˆa)=0. By construction, this is MODIA, assuming ˆ ρ, n, and h were provided. By assigning ϵ∗ =π∗ (ˆ s0 ), we minimize expected regret. In the worst-case, it necessitates modeling all n DC instantiation permutations (with replacement) of the k DPs, which is O(kn ).

This illustrates the importance of the original MODIA formulation. Even with the instantiation model of Proposition 2, the problem is still unscalable. And the knowledge needed to bound the number of active DCs (e.g., n and h) is generally unavailable a priori. This intrinsic lack of information motivated our formulation that minimizes the regret at each time step. Hence, the agent is guided by the optimal DC policies from each instantiated DP, selecting the regretminimizing action at each time step. Proposition 3 proves that LEAF minimizes the regret in risk-sensitive MODIA at each time step, enabling a tractable solution to MODIA.

Proposition 3. If aMODIA is risk-sensitive, then LEAFminimizes regret rtϵ for all t.

Proof. By definition of regret rtϵ for LEAF ϵ at time step t: rtϵ = ∑i Qj (bti i ,πj(bti i ))-Qj(bti i ,ϵ-1 i (at )) with φ(Ci)=Pj. We must show for all ˜ ϵ, rtϵ ≤˜ rt˜ ϵ . For readability, hereafter, let ai=ϵ-1 i (at ), ˜ai=˜ ϵ-1 i (˜at ), a∗j =πj(bti i ), and bi=bti i . By definition of risk-sensitive, there always exists action a∗j such that Qj(bi,a∗j )≥Q. Thus, it is sufficient to show that for all i∈I t , Qj(bi,ai)≥Qj(bi,˜ai), or there exists a Ci∈C with φ(Ci)=Pj such that Qj(bi,˜ai)≤Q. By risk-sensitivity and LEAF, consider 3 cases for ϵ and ˜ ϵ.

Case 1: ai=x ˜ai for ai,˜ai∈Λx=Aj. Trivially, we have Qj (bi, ai) =Qj (bi, ˜ai).

Case 2: ai≻x ˜ai has two cases. Case 2.a: If ai=a∗j , then by definition πj's optimality, for any ˜ai∈Aj, Qj(bi,ai)= Qj(bi,a∗j )≥Qj(bi,˜ai). Case 2.b: If ai ̸=a∗j , then by LEAF Equation 2, ai∈{a∈Λx|∃u s.t. ¯au=a}. Thus, by definition of ¯a∈ ¯ A, there exists this u̸=i such that ai=au=a∗v with φ(Cu)=Pv. By risk-sensitivity, a∗v =au=ai≻x ˜ai that implies Qv(bu, ˜ai)≤Q.

Case 3: ai≺x ˜ai. By definition of risk-sensitivity, we have ˜ai≻xai⪰xa∗j and consequently Qj(bi,˜ai)≤Qj(bi,ai).

All cases proven. LEAF minimizes regret rtϵ for any t.

5 Application to Autonomous Vehicles

We apply MODIA and LEAF to this concrete problem of AV decision-making at intersections. The formulation expands on the numerous AV examples described in Section 3. Due to space considerations, we focus our attention strictly on defining vehicle-related DP (POMDP); however, pedestrian and other DPs follow in a similar manner. Overall, this AV robotic application serves to both ground our theoretical work and simultaneously present an actual solution to intersection decision-making in the real world.

The MODIA AV 〈P,A〉 defines P by converting intersection types (and pedestrian types) into POMDP DP. These types capture the static abstracted information. For example, intersection types contain features such as the number of road segments, lane information (incoming and outgoing), crosswalk locations, and traffic controller information. A DP is created for all lanes within all intersection types (and pedestrian types). Formally, for each such vehicle and intersection type, we define the DP POMDP 〈Si,Ai,Ωi,Ti,Oi,Ri〉= Pi∈P. Si=Sℓav ×Stav ×Sℓov ×Stov ×Sb ov ×Sp ov describes the AV's location (approaching/at/edged/inside/goal) and time spent at location (short/long), as well as the other vehicle's location (approaching/at/edged/inside/empty), time spent at location (short/long), blocking (yes/no), and priority at intersection in relation to AV (ahead/behind), respectively. Actions are simply Ai={stop,edge,go}, and encode movement by assigning desired velocity and goal points along the AV's trajectory within the intersection. Lower-level nuances in path planning [Wray et al., 2016b] are optimized by other methods. Ωi=Ωtav ×Ωbav ×Ωtov ×Ωbov primarily encode the noisy sensor updates in blocking detection (yes/no) but also if the time spent was updated (yes/no) for both the AV and other vehicle. Ti :Si×Ai×Si→[0,1] multiply the probabilities of a wide range of situations quantifiable and definable in the state-action space described. This includes multiplying probabilities for: (1) vehicle kindly lets AV have priority, (2) vehicle cuts AV off, (3) AV's success or failure of motion to an abstracted state based on its physical size, (4) a new vehicle arrives at an intersection lane, (6) time increments, (7) vehicle actually stops at stop sign or does a rolling stop, (8) vehicle is blocking the AV's path following the static intersection type's road structure, etc. Additionally, a dead end state (an absorbing non-goal self-loop) is reached when the AV and other vehicle both have state factor "inside" while also "blocking" each other. Oi :Ai×Si×Ωi→[0,1] captures the sensor noise (e.g., determined via calibration and testing of the AV's sensors). This includes successful detections of: (1) other vehicle's crossing of physical locations mapped to abstracted states, (2) determining the blocking probability based on the location of the other vehicle, etc. Ri :Si×Ai→R is defined as unit cost for all states, except the goal state.

The primary actions are A={stop,edge,go} and simply describe the AV's movement along the desired trajectory. We define a lexicographic preference ≻1 over this action set stop≻1 edge≻1 go. This preference formalizes the notion that if even one DC said to stop, then the AV should stop. Similarly, if at least one DC said to edge but none said stop, then the AV should cautiously edge forward. Otherwise, the AV should go. This enables us to apply LEAF because Ai =A for all Ai (even the pedestrian DPs) and we have lexicographic preference ≻1. Lastly, the defined MODIA produces Q-values that satisfy risk-sensitivity.

6 Experimentation

We begin with experiments on six different intersections in an industry-standard vehicle simulation developed by Realtime Technologies, Inc. that accurately simulates vehicle dynamics with support for ambient traffic and pedestrians. We evaluated MODIA on real map data at six different intersections, each highlighting a commonly encountered real-world scenario. Table 1 describes each scenario by name and provides details regarding the road segments, vehicles, and pedestrians that exist. The number of potential incidents describes how many risks exist, which MODIA perfectly obviates. We compare a MODIA AV with ignorant and naive AV baseline algorithms. The ignorant AV follows the law but ignores the existence of all vehicles and pedestrians, acting as if the intersections are empty. The naive AV follows the law and cautiously waits until all others have cleared the intersection beyond 15 meters before attempting to go. These two baselines implement extremes of rule-based AVs [Jo et al., 2015] and serve as a form of bound for AV behavior to understand MODIA AV's performance. We evaluate each by their time to complete an intersection, which includes the observations while approaching, decisions at the intersection, and travel within the intersection. In Table 1, we observe the MODIA AV successfully completes intersections faster than the cautious naive AV. While the MODIA AV takes longer than the ignorant AV, the ignorant AV encounters each potential incident and the MODIA AV safely avoids them.

Figure 2 depicts a common 4-way intersection with our fully-operational AV prototype, which operates on real public roads and contains an implementation of MODIA and LEAF. This real-world scenario illustrates MODIA's success in addressing scalability concerns while simultaneously handling the nuanced aspects of online decision-making. Each described vehicle DP POMDP has 400 states (265 with additional pruning), with a rich well-structured belief space. In MODIA AVs, the POMDP's size is constant and applies to any intersection. In comparison, a single all-encompassing POMDP with these state factors quickly becomes utterly infeasible, and will vary greatly among intersections. For example, the 4-way stop from Figure 2 that only considers the AV and 3 other vehicles (no pedestrians) would the state space S=Sℓav ×Stav ×3i=1 (Sℓovi ×Stovi ×Sb ovi ×Sp ovi ). This has |S|=640,000 states, exemplifying notions from Proposition 2. Conversely, MODIA AVs scale linearly with the number of vehicles, and would only be 795 states evenly distributed over three POMDPs. On modest hardware, a DP can take <1 minute to solve using nova [Wray and Zilberstein, 2015]. Monolithic POMDPs, like the one described, are unequivocally intractable; however, MODIA enables the now realized POMDP solution for AV decision-making.

7 RelatedWork

Previous work on an general models related to MODIA include architectures for mobile robots [Brooks, 1986; Rosenblatt, 1997] or other systems [Decker, 1996], and contain decision-components that produce actions, aggregated to a system action. They do not, however, naturally model uncertainty or have a general theoretical grounding. Forms of hierarchicies include action-based execution of child problems with multi-options [Barto and Mahadevan, 2003] and abstract machines [Parr and Russell, 1998]. Action-space partitioning that execute smaller MDPs [Hauskrecht et al., 1998] and POMDPs [Pineau et al., 2001] also exists. These do not model the online execution of an unknown number of decision-components for use in robotics. More applicationfocused work on action voting for simple POMDPs to solve intractable POMDPs have been used successfully [Yadav et al., 2015]. Robotic applications of hierarchical POMDPs for an intelligent wheelchair decompose the problem into components [Tao et al., 2009], or with two POMDP levels for vision-based robots [Sridharan et al., 2010]. These practical methods work well but lack generalized mathematical foundations. Also, none of these present AV-specific solutions.

Previous work specific to AV decision-making includes simple rule-based or finite-state controller systems [Jo et al., 2015], which are simple to implement but are brittle, difficult to maintain, and were unable to handle the abundant uncertainty in AV decision-making. Initial attempts using deep neural networks map raw images to control [Chen et al., 2015] are slow to train and tend to fail rapidly when presented with novel situations. Mixed-observability MDPs for pedestrian avoidance also successfully use a decision-component approach (AV-pedestrian pairs) but provide limited theoretical work and do not extend to intersections [Bandyopadhyay et al., 2013]. Using a single POMDP for all decision-making has been explored, including continuous POMDPs using raw spacial coordinates for mid-level decision-making [Brechtel et al., 2014], online intention-aware POMDPs for pedestrian navigation [Bai et al., 2015], and POMDPs for lane changes that use online approximate lookahead algorithms [Ulbrich and Maurer, 2013]. These approaches do not address the exponential complexity concerns (scalability), provide generalizable theoretical foundations, or enable simultaneous seamless integration of multiple different decision-making scenarios on a real AV, all of which are provided by MODIA.

8 Conclusion

MODIA is a principled theoretical model designed for direct practical use in online decision-making for autonomous robots. It has a number advantages over the direct use of a massive monolithic POMDP for planning and learning. Namely, it remains tractable by growing linearly in the number of decision-making problems encountered. Its component-based form simplifies the design and analysis, and enables provable theoretical results for this class of problems. MODIA is shown to successfully solve a challenging AV interaction problem. Future work will explore more executors and models beyond LEAF and risk-sensitive MODIA, develop additional AV-related DPs, and tackle other intractable robotic domains such as humanoid service robots using MODIA as a scalable online decision-making solution.

Acknowledgments

We thank the reviewers for their helpful comments, Liam Pedersen for valuable discussions, and Nissan Motor Co., Ltd. for supporting this work.