Hierarchical Approach to Transfer of Control in Semi-Autonomous Systems

1 Introduction

Autonomous systems have been deployed in a wide variety of applications such as space exploration [Zilberstein et al., 2002], reservoir control [Castelletti et al., 2008], energy conservation [Kwak et al., 2012], and autonomous driving [Wray and Zilberstein, 2015; Wray et al., 2015]. These systems, however, almost universally require human intervention or interaction at some point in order to achieve their objectives (e.g., the Mars rovers), or recover from failure (e.g., the Roomba vacuum cleaner). Within the proposed automated planning solutions to these problems, few if any approaches take full advantage of this collaboration. Instead, they commonly resort to default hard-coded behaviors instead of integrating human capabilities into the planning process [Biswas and Veloso, 2013]. Semi-Autonomous Systems (SAS) capture explicitly this collaborative process in which a human and an agent-or any number of actors-work together to achieve a goal, smoothly transferring control over the system back and forth, while proactively considering each actor's capabilities and the human's preferences [Zilberstein, 2015].

New challenges arise in semi-autonomous systems because the overall plan must factor the inherent uncertainty and unpredictability associated with human behavior. We consider a semi-autonomous driving domain where the vehicle can operate autonomously only on well-mapped roads under ideal conditions. To reach a distant destination, the vehicle may require the human to occasionally take control. This transfer of control process requires second-to-second monitoring as various messages are conveyed to the driver. It is also not always successful given an allotted time window and the driver's state (e.g., distracted). These factors must be taken into consideration as the system is planning its long-term route. Additionally, this process of transfer of control must incorporate these factors to provide a measure of safety for the system. Car companies are already developing nascent semi-autonomous capabilities and user interfaces to support transfer of control [Nissan Motor Company Ltd, 2016], but research has been sparse on generalized planning models.

Previous work on semi-autonomous systems has focused on preventing or reacting to human error [Anderson et al., 2009], for example, automatically correcting an undesired lane change [Jung and Kelber, 2004] or human-reactive implementations of adaptive cruise control [Rajamani and Zhu, 2002]. While a long line of research exists on collaboratively controlling a system [Connell and Viola, 1990], planning with the explicit consideration of the human in the plan execution cycle has been lacking [Fong et al., 2003]. No existing algorithm explicitly tackles the transfer of control problem.

Our proposed collaborative multiagent framework is quite distinct from existing approaches for collaboration such as Shared Plans [Grosz and Kraus, 1996], Teamwork [Tambe, 1997], and Dec-POMDP [Bernstein et al., 2002]. First, a SAS requires exactly one actor to be in control of plan execution at any given time. Second, this fact requires explicit mechanisms for transferring control among the actors. Finally, a SAS must proactively plan to leverage each actor's capabilities (or lack thereof) as it efficiently moves in the state space.

Our primary contributions are: (1) a formal definition of a SAS and its key properties, (2) a general transfer of control model, (3) a hierarchical approach for integrating domain action planning with transfer of control, and (4) an analysis showing the hierarchical model is a strong SAS. Finally, we provide semi-autonomous driving experiments for 10 cities using real road data that show the benefits of the method.

2 Semi-Autonomous Systems

Semi-Autonomous Systems (SAS) rely on collaboration between a human and an agent in order to achieve some goals while maintaining a measure of safety [Zilberstein, 2015]. We consider semi-autonomy within the context of automated planning, extending a Markov Decision Process (MDP) to support semi-autonomy, as formally defined below.

Definition 1. A semi-autonomous system is represented by a tuple xA↪ S`↪ A`↪ T`↪ C`↪ G↪ Ly.

• ÷ S`"SˆA is a set of factored states: a standard state set S and the current controlling actor A.
• ÷ A is a set of actors (controlling entities).
• ÷ A`"AˆA is a set of factored actions: a standard action set A and the next desired actor A.
• ÷ C` : S`ˆA`ÑR` is a cost function.
• ÷ T` : S`ˆA`Ñ4|S`| is a transition function, comprised of a state transition Ta : SˆAÑ4|S| for each actor a P A, and control transfer function ⇢ : S`ˆAÑ4|A| .
• ÷ GÑS` is a set of goal states.

The actors A of the system describe controlling entities, which include at a minimum a human λ and an autonomous agent ⌫; we focus in this paper on situations involving these specific two actors. The states must record who is in control at any given time, and the actions must record intentions to switch control to new actors. In SAS, we cannot always assume that transfer of the control has a flawless execution. Hence our T` (Definition 4) is factored into two components: Ta and ⇢ (Definitions 2 and 3).

• ÷ LÑS` is a set of live states, such that for actor capability function : SÑ2A, L"txs↪ ay P S`|a P psqu.

Definition 2. An actor state transition function, denoted Ta : SˆAÑ4|S| , describes how an actor a P A can operate in the world when in control (n-simplex 4n ).

Definition 3. A control transfer function, denoted ⇢ : S`ˆAÑ4|A| , describes the result of attempting to transfer control from the current actor in a given state.

Definition 4. The SAS state transition function for s` " xs↪ ay, a` " xa↪ ˆay, and s1` " xs1 ↪ a1 y is:

In Equation 1, the first component corresponds to keeping the current actor, which simply follows the actor's state transition. The second component describes the actor still in control but seeking to switch to a different actor at the next state. The third component indicates that it is impossible to take control from an actor without the desire to transfer.

We develop a hierarchical approach to transfer control that treats each decision of the high-level planning process as a macro-action or an option [Sutton et al., 1999], which involves micro-actions to support the successful transfer of control. This hierarchical design seems particularly suited for our target domain of semi-autonomous driving. Here, we perform path planning on large, world-scale roads in time scales of minutes or hours. Transfer of control, however, requires much more care, and is done in time scales of seconds. If we were to path plan with transfer of control at full detail everywhere along the route, the state spaces would be astronomically large. For example, for the smallest problem instance in our experiments (Pittsburgh), this would blow up the state space by a factor of 387, resulting in a POMDP with approximately 7▷6ˆ104 states. Instead, we take advantage of the fact that transfer of control is a generic process that depends on a handful of context variables such as the time remaining to complete the transfer and some general driving conditions (e.g., transferring control on a straight road, turns, low-speed, and high-speed). Apart from that, the way in which the transfer of control is performed is largely independent of the remaining route and destination. This enables us to generalize the transfer process, and model it as a compact state transition at the higher level following ⇢ in the form of an option.

Following Zilberstein [2015], a SAS of type I (SAS-I) does not explicitly model the human in the execution loop, whereas a SAS of type II (SAS-II) does. Thus, we have presented a SAS-II as we explicitly model the human within our set of actors (λ P A). We proceed with additional properties.

Within a SAS, we define two types of histories. Definition 5 formalizes the meaning of any trajectory over states and actions, given the limits of the stochastic state transition.

Definition 5. A realizable history is a sequence of the form ~ " xs0`↪ a0`↪ ▷ ▷ ▷ ↪ s``y such that for all si`, ai`, and si`1 ` , T`psi`↪ ai`↪ si`1 ` q ° 0. The set of all realizable histories starting at s0` P S` with horizon ` P N is denoted ¯Hps0`↪ `q.

Next, we define a more constrained history with respect to a specific policy in Definition 6. A policy ⇡ : S`ÑA` is a mapping from factored states to factored actions.

Definition 6. Given policy ⇡, a policy realizable history, is a realizable history ~ such that @i↪ ai` "⇡psi`q. We denote the set of all policy realizable histories starting at state s0` P S` with horizon ` P N as ¯H⇡ps0`↪ `q.

Given a policy ⇡, the agent incurs a cost per time step given by C` : S`ˆA`ÑR` as it tries to reach a goal state from G Ñ S`. A policy is optimal if it minimizes the expected cost over time, also called the value of a state V` : S`ÑR. For initial state s0 P S`, the optimal policy ⇡˚ minimizes:

Given an initial state, this defines a Stochastic Shortest Path (SSP) MDP. Bellman's optimality equation for state s is:

Following Bertsekas and Tsitsiklis [1991], this equation produces an optimal policy ⇡˚ under two assumptions. First, a proper policy must exist that can reach a goal with probability 1 from s. Second, all improper policies must incur infinite cost at states that cannot reach a goal with probability 1. Such SSPs can be solved using search methods such as LAO* [Hansen and Zilberstein, 2001] as well as conventional value iteration.

So far we have described a concrete model that explicitly represents the current actor (controlling entity) and the dynamics for attempting to transfer control among actors. We now introduce actor capability constraints for SAS, which specify limits on the abilities of actors to control the system under certain conditions, through the function in Definition 7.

Definition 7. An actor capability function (ACF) : SÑ2A maps states to the actors capable of acting in that state.

For example, in the semi-autonomous driving domain, the autonomous agent may not be able to drive on every road, but only on well-mapped roads or under certain weather conditions. Thus, the planner must incorporate the limited capabilities of the autonomous agent, as well as the uncertainty regarding transfer of control between the human and agent, in order to construct a route from a starting location to a destination. Definition 8 formalizes the notion of live state in which an actor can control the system.

Definition 8. Live states L"txs↪ ay P S`|a P psqu are states which satisfy the ACF .

Live states are states in which the system is considered active or safe, because the controlling entity can act there. Definition 9 states constraints that must be satisfied for all SAS.

Definition 9. The live state constraints for SAS are:

1. G Ñ L

Unlike general dead ends [Kolobov et al., 2012], which are states from which the goal becomes unreachable, our live state constraints form a particular structured type of dead end that is easier to analyze (largely because these conditions are explicitly captured by L). In fact, we will show that our semiautonomous vehicle formulation produces policies that guarantee avoidance of non-live states. In general, this requires us to prove that the given transfer of control model produces a ⇢ that never enters a non-live state. This key mechanism is described in the following section. We now formalize this.

Our objective is to characterize policies and systems in terms of their ability to maintain live state. Definitions 10, 11, and 12 present three key properties of policies.

Definition 10. A policy ⇡ is strong if for all s0` P L and ` P N, and for all ~ P ¯H⇡ps0`↪ `q and i P t0↪ ▷ ▷ ▷ ↪ `u, si` P L.

Definition 12. A policy ⇡ is weak if it is not strong or conditionally strong.

Definition 11. A policy ⇡ is conditionally strong if there exists an s0` P L and ` P N, such that for all ~ P ¯H⇡ps0`↪ `q and i P t0↪ ▷ ▷ ▷ ↪ `u, si` P L.

Next, we extend these terms from policies to an entire SAS. A SAS is said to be strong (conditionally strong) if there exists a strong (conditionally strong) policy ⇡˚ that is optimal. Otherwise, the SAS is said to be weak.

3 Transfer of Control

Transfer of Control (TOC) is the critical method that enables effective and safe transference of the controlling entity within the stochastic decision-making process. TOC both to and from a human requires the optimal selection of various messages (e.g., visual or auditory) in order to prompt the human to reengage and ensure smooth transference. Each message type presents a trade-off between the efficacy of alerting the human to the agent's intention and the human's amiable perception of the agent (e.g., aggregated annoyance). For example, a continuous alarm is effective but undesirable, and a blinking light is not as effective but more favorable. Additionally, the system receives noisy observations of the human's state of engagement due to the limited sensing capabilities available. Thus, it instead must make decisions based on a belief regarding the engagement level. Finally, this is a time-sensitive sequential optimization problem due to the limited time window in which control may be transferred. For example, in semi-autonomous driving, the vehicle may not be able to operate on insufficiently mapped roads and must seamlessly relinquish control before reaching these roads. We model this process using a POMDP. First, we formally define the TOC problem, then POMDPs, and finally construct the POMDP model of TOC.

3.1 The Transfer of Control Problem

The Transfer of Control (TOC) Problem is a tuple xH↪M↪ O↪ T ↪ Ph↪ Pc↪ Po↪ Cy. H is a set of human states. M is a set of available messages to inform the user of the desire to transfer control. The absence of a message is indicated by H P M (i.e., no operation or 'NOP') and is always available. O is the set of observations made by sensors, which provide partial information about the human's state. T "t1↪ ▷ ▷ ▷ ↪ ⌧u is a set of limited time steps for the transfer of control to complete (e.g., ⌧ seconds). Ph :HˆMˆT Ñ4|H| is the probability of the human state transitioning from h to h1 given message m was sent t time steps ago, such that we have Phph↪m↪ t↪ h1 q"Prph1 | h↪m↪ tq. Pc :HˆMÑ4|T | is the probability that control will be transferred given the human state h and that message m was sent t time steps ago. If control is transferred, then the process terminates; the agent knows when this occurs. Po :HÑ4|O| is the probability of making a sensor observation o given the human state is h, such that Poph↪ oq"Prpo|hq. C :HˆMˆT ÑR` is the cost of sending message m given human state h and t time steps since sending the last message (i.e., Cph↪m↪ tq). The agent can always abort, ending the transfer attempt.

The human has a true hidden state h P H. This changes over time as the agent selects a message mt P M for each t P T , forming sequence m " xm1↪ ▷ ▷ ▷ ↪m⌧ y. The objective is to minimize the total sum of message costs; however, failing to transfer control without safely aborting should strictly be avoided. Thus, the agent must also decide when to abort.

Importantly, control can be transferred either way in this model. That is, it captures requesting control to be both taken from and given to the agent. Furthermore, different TOC problems may be defined, each encoding a different environment or scenario in which control must be transferred. For example, a vehicle taking control on a highway turn, or a human taking control on a quiet suburban road, are both different transfer of control instances.

3.2 Background on POMDPs

A Partially Observable Markov Decision Process (POMDP) is defined by a tuple x ¯ S↪ ¯ A↪ ¯⌦↪ ¯ T↪ ¯O↪ ¯Ry [Kaelbling et al., 1998]. ¯ S is a set of n states. ¯ A is a set of m actions. ¯⌦ is a set of z observations. ¯ T : ¯ Sˆ ¯ AÑ4| ¯ S| is a state transition function such that ¯ T ps↪ a↪ s1 q " P rps1 |s↪ aq. ¯O : ¯ Aˆ ¯ SÑ4|¯⌦| is an observation function such that ¯Opa↪ s1 ↪ !q"Prp!|a↪ s1 q. ¯R: ¯ Sˆ ¯ AÑR is a reward function denoted ¯Rps↪ aq. Actions are performed at each time step, up to the horizon ` P N, discounting the reward obtained by γ P p0↪ 1q. The agent, however, must select actions without knowing the true state of the system. Instead, it maintains a belief over the true state b P 4n , or a collection of r beliefs ¯B Ñ 4n (standard n-simplex). Given belief b, action a, and subsequent observation !, for each state s1 , the belief updates (normalizing constant ⌘ " Prp!|b↪ aq´1 ) via: b1 ps1 q " ⌘ ¯Opa↪ s1 ↪ !q ∞sP ¯ S ¯ T ps↪ a↪ s1 qbpsq.

The goal is to find a policy ⇡ : ¯BÑ ¯ A that maximizes the expected reward over time, i.e., value function ¯ V : ¯BÑR. This function is piecewise linear and convex [Kaelbling et al., 1998], so we use a set of ↵-vectors Γ" t↵1↪ ▷ ▷ ▷ ↪ ↵ru with each vector ↵i " r↵ips1q↪ ▷ ▷ ▷ ↪ ↵ipsnqsT . Each ↵ipsj q denotes the value of state sj P S. The optimal value (resulting in an optimal policy ¯⇡˚ ) at time t for belief b is:

3.3 Transfer of Control POMDP Formulation

with ¯ V t sa!↵ " γ ∞s1 P ¯ S ¯Opa↪ s1 ↪ !q ¯ T ps↪ a↪ s1 q↵ps1 q.

We model the control transfer problem as a POMDP called a TOC POMDP. The state space is ¯ S "T ˆHˆMˆT Y E with a set of 'end result' states E "t'↪ a↪ mu denoting 'success,' 'failure,' and 'aborted,' respectively. Each state captures the time remaining, current human state, the previous message sent, and how long it has been since that message was sent, as well as the outcome of the transfer of control. The action space ¯ A"M Y tmu is the messages to send and the 'abort' action (denoted m). The observation space ¯⌦"O Y E represents the observations, and lets the model know the end result, as per the problem definition. The state transition function needs to encapsulate the notions of human state, as well as the success or failure of transferring control. We break this into two scenarios.

The first scenario examines transitions only among nonend result states such that s↪ s1RE, with state factors denoted s"xt↪ h↪m↪ tmy and s1 "xt1 ↪ h1 ↪m1 ↪ t1my. This scenario has two non-zero cases each with the same probability. In both, control has not successfully transferred yet, so we always update the human state and count down the timer (via constraint t1"t´1 · 0). The first case encodes the effect of sending a message fromMztHu. The second case encodes the effect of a 'NOP' message H. Formally, for any s, a, and s1 :

The second scenario examines transitions to an end result state: successor s1 PE. This scenario has four non-zero cases. The first case is simply the absorbing states E. The second case is immediate termination via the abort action m. The third case captures the ever-possible chance of successful control transfer ('). The fourth case handles a failure (a) transition by running out of time. Thus, for a state s, action a, and successor s1 we have:

The observation transition function only needs to model two components. First, the agent always has perfect knowledge of the final outcome state. Second, the agent makes noisy observations from sensors which hint at the true human state (e.g., a face or eye tracker in a vehicle). Formally, for action a, successor state s1 , and observation !:

with s " xt↪ h↪ m↪ tmy above provided sRE .

with states s1 " xt1 ↪ h1 ↪ m1 ↪ t1my above provided s1 R E.

The reward function has four components. First, there are costs associated with all normal messages, as defined by the TOC problem. Second, an arbitrarily small ✏ ° 0 cost is given for a NOP H. Third, there is a large penalty for unnecessary aborting. Fourth, failure repeatedly incurs the maximal cost. Thus, for state s and action a:

with s"xt↪ h↪m↪ tmy and a non-success penalty C ˚ (e.g., let C ˚ " `Cmax with Cmax " maxh↪m↪tm Cph↪ m↪ tmq).

Within a TOC POMDP, the end result terminal states are fully observable, as well as each state factor except for the true human state H. Thus, all beliefs, including initial belief b0 , only contain uncertainty regarding these human states.

4 Application to Semi-Autonomous Driving

The TOC formulation as a POMDP enables us to incorporate semi-autonomy into stochastic path planning problems. Again, our main motivation is the semi-autonomous driving domain. Route decisions are made at intersections of roads; however, only well-mapped main roads are capable of autonomy. While the driver can drive on any road, the longer, uninteresting, boring highways are assumed to be roads in which the human prefers autonomy, meaning that control should be transferred to the vehicle. All costs are proportional to the time spent on the road. The uncertainty stems from the transfer of control, also decided at road intersections. We first formally define the problem, then describe the full model of a specific SAS called a Semi-Autonomous VEhicle (SAVE).

4.1 ProblemDefinition

The Semi-Autonomous VEhicle (SAVE) Problem begins with a strongly connected weighted directed graph xV↪ E↪ wy. V is a set of vertices forming intersections. E Ñ VˆV is a set of pairs of vertices (intersections) defining edges which form roads. w :EÑR` defines a positive weight for each edge (road) which captures the time spent on the road. There are initial and goal vertices v0 ↪ vg P V .

Additionally, the system may be driven by the human or the agent (vehicle) itself; however, given the allotted time between each vertex (intersection), there is uncertainty if control transfer will be successful. This micro-level behavior is modeled using TOC POMDPs. (These may be solved offline for different scenarios, as described in the previous section.) We label edges (roads) Ec Ñ E as autonomycapable, meaning the set of roads in which the vehicle is capable of driving autonomously. Similarly, Ep Ñ Ec are autonomy-preferred roads in which the human prefers autonomous driving. Thus, at each intersection the agent must decide if control should be maintained or transferred as well as which road to take next, in order to minimize the sum of traversed weights (travel time). If control transfer is required, fails to succeed, but the agent aborted, then the system is assumed to safely pause at the vertex, i.e., the vehicle safely pulls over to the side of the road. Otherwise, the SAS will enter an unsafe state in which the vehicle is in control but cannot drive on the road; this should be avoided at all costs.

4.2 Semi-Autonomous Vehicle Formulation

A Semi-Autonomous VEhicle (SAVE) is a SAS with xA↪ S`↪ A`↪ T`↪ C`↪ G↪ Ly. Actors A" tλ↪ ⌫↪ σu encode the current controlling agent of the vehicle: either the human λ, the vehicle itself ⌫, or no active actor as it safely waits on the side of the road σ. S`"VˆA have standard states V corresponding to the vertices (intersections) of the map. A`"DˆA is the action set with D denoting the possible directions (roads) to take at a vertex (intersection) (e.g., D " t-↪ Ò↪ Ñu). This notation is commonly overloaded such that A`psq returns the set of actions available at state s. Let ✓ : VˆDÑV map a vertex (intersection) and an action (direction) to the subsequent vertex following E. Additionally, we assume: (1) the map is expanded to include a 'failure' absorbing vertex vf P V , with ✓pvf ↪ dq"vf for all d P D, and (2) the goal is also absorbing with ✓pvg ↪ dq "vg for all d P D.

The state transition function T` follows Equation 1, and introduces the uncertainty from our TOC POMDP's transfer of control process given by ⇢. First, for the human actor λ, the actor transition function Tλ simply follows the map. Next, for vehicle actor ⌫, the actor transition function T⌫ ensures that: (1) autonomy-capable states follow the path, and (2) non-autonomy-capable states enter the absorbing vertex vf . Finally, for the safely parked vehicle σ, the actor transition function Tσ always self-loop since it is on the side of the road.

We now define the control transfer function ⇢. Formally, for s"xv↪ ay P S` with action xd↪ ˆay P A`psq, the allotted travel time is ⌧ "twpxv↪ ✓pv↪ dqyqu. We have a particular TOC POMDP given the intersection v, current controlling actor a, and desired successor actor ˆa from optimal SAVE policy ⇡˚ psq " xd↪ ˆay. We assume the TOC POMDP's T "t1↪ ▷ ▷ ▷ ↪ ⌧u has units in seconds without loss of generality. Given the solved TOC POMDP, we would like to compute the expected result from transfer of control. Formally, we sample trajectories over the unobserved true state, observations, and resultant action following the TOC POMDP's optimal policy. Due to the structure of the TOC POMDP, this always results in a collapsed belief with a known end result from E. Formally, let J "ts1↪ ▷ ▷ ▷ ↪ sku be a set of k final 'end result' states from the TOC POMDP's E which are determined by random state-action-observation trajectories following the TOC POMDP.

In the case with a"σ, initially the car is safely on the side of the road. Either (1) the car remains on the side of the road, (2) the human TOC succeeds, or (3) the human TOC fails:

In the case with a‰σ, either the human λ or vehicle ⌫ is the controlling entity. Either (1) no transfer is requested and the actor remains the same, (2) the TOC succeeds to switch actors, (3) the TOC fails to switch actors, or (4) the TOC is aborted and safely pulls over to the side of the road:

with r¨s denoting Iverson brackets.

Trivially, in the limit as the number of sampled trajectories grows kÑ8, this converges to the exact probabilities of obtaining each resulting actor, our desired result. This formulation of the expected value with number of samples k enables us to sample a finite number of times and obtain an approximation of ⇢ in practice.

The cost function C` simply measures the time traveling on a road, given its length and speed limit. We assume ties between actions are broken following the autonomy-preferred roads in Ep. In other words, if autonomy is preferred and the current actor is the human λ, then the next action will attempt to transfer to the vehicle ⌫. For s"xv↪ ay and a"xd↪ ˆay:

The goal is G"txvg ↪ λyu and the initial state is s0 "xv0 ↪ λy. Following the problem definition, the human is capable of acting in all states, and the vehicle can be safely on the side of the road in any state. Thus, for a vertex v, pvq is tλ↪ ⌫↪ σu if the road v is autonomy-capable, and tλ↪ σu otherwise. Trivially, the failure state has no actors ( pvf q "H). This defines L following Definition 8.

4.3 Theoretical Analysis

We now integrate all three concepts we have introduced thus far: SAS, TOC POMDP, and SAVE, in order to show that the transfer of control within our stochastic path planning model provably maintains live state guarantees. Due to space constraints, we only provide proof sketches.

Proposition 1. SAVE satisfies the live state constraints.

Proof (Sketch). Both cases in Definition 9 are satisfied because (1) the goal is a live state, and (2) Tλ forces all non-live states to transition to the absorbing states at vf .

Next, we establish Lemma 1 which states that the only uncertainty regarding the true state is over the human factor. This fact allows the agent to know and thus act appropriately at the final time step.

Lemma 1. Belief uncertainty within the TOC POMDP is only over the human state factor H; all other factors are known.

Proof (Sketch). Proof by induction following the belief update equation from b0 . Base case is trivial. Induction step considers the update to b1 for any a or !. Equation 5's ¯ P is non-zero following Pc and Ph; all other state factors deterministic (both cases). Equation 7 follows Po, only stochastic over human states. Thus, b1 has uncertainty only over H.

Establishing this property allows us to prove that the TOC POMDP never enters the failure state a in Proposition 2. This is a critical requirement in order to prove that SAVE is a strong SAS in Proposition 3.

Proposition 2. Following a TOC POMDP's optimal policy ⇡˚ , for any horizon `, the underlying true state s` ‰ a.

Proof (Sketch). By Lemma 1, we examine actions taken at reachable beliefs with t " 0, since this factor is known to the agent. By Equation 8, the abort action m is always optimal. By Equation 6, the failure state is unreachable following ⇡˚ . Thus, s` ‰ a.

Proposition 3. SAVE is a strong SAS.

Proof (Sketch). SAVE enters a failure vf from some v only for T⌫ with v R Ec and zero time remaining (t " 0). By Equation 10 and 's definition, the only way to enter a nonlive state is for an optimal TOC POMDP policy to enter a with ⌫ in control when v1 R Ec. This is impossible by Proposition 2, implying a SAVE optimal policy is strong (Definition 10). Thus, SAVE is a strong SAS.

5 Experiments

We present a series of trials with subsets of 10 cities' road data from Open Street Map (OSM). Distant start and goal addresses are selected as one would do using a Global Positioning System (GPS) device. All main roads with a speed limit of 30 or greater are marked as autonomy-preferred. We compare our approach with a human driver following the GPS (λ), only the autonomous car (⌫), and the collaboration between human and vehicle (λ & ⌫). We use three metrics for comparison. First, we check if the goal was reachable from the initial road (G). Second, we determine the percentage of time the vehicle drives autonomously, provided it could do so, for roads along its route (%). Third, we record the average travel time to compare efficiency along each of the routes (T).

Our experiments solve the TOC POMDP with Point-Based Value Iteration (PBVI) [Pineau et al., 2003] and the SAVE SAS using LAO* [Hansen and Zilberstein, 2001]. Table 1 shows our results for 100 trials for each city. Figure 1 depicts a sample collaborative policy in which the human and vehicle gracefully transfer control along the route. The driver is always able to reach the goal, but never drives autonomously, even when the car is capable of doing so. The autonomous vehicle always succeeds in autonomously driving, but is only able to reach the goal in 3 of the 10 scenarios. When it does drive autonomously, it has to take long main roads, causing travel time to be greatly increased. Interestingly, the human and autonomous vehicle collaboration always reaches the goal, and drives autonomously for large portions of the route. Also, the average travel times are relatively similar between the human and collaborative scenarios. This collaborative approach selects routes that properly balance main road autonomous driving and back road human driving.

6 Conclusion

We present a hierarchical approach to the transfer of control in semi-autonomous systems, which facilitates efficient planning for a human-agent collaboration. The hierarchical model captures explicitly and optimizes the critical transfer of control process using a POMDP. We show how to apply the general framework to SAS for semi-autonomous vehicles and demonstrate its benefits. Furthermore, we analyze the SAS with TOC model, showing that it maintains live state and thus is a strong SAS. The experiments show that the hierarchical approach is able to leverage the capabilities of the human and agent as it optimizes the desired objective.

Future work will include experiments with humans in a full-scale driving simulator. We will also explore other SAS domains such as assistive technologies (e.g., physical therapy) and disaster response (e.g., search-and-rescue). Finally, we will provide our source code to facilitate the creation of a wide variety of strong semi-autonomous systems.

Acknowledgments

We thank Claudia Goldman for feedback on early versions of this work. This research was supported by the National Science Foundation grant number IIS-1405550.