Situation Awareness for Tactical Driving
Rahul Sukthankar January 27, 1997
CMU-RI-TR-97-08 Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. c 1997 Rahul Sukthankar
This research was partially supported by the U.S. Department of Transportation, under cooperative agreement Automated Highway System: DTFH61-94-X-00001. iii Abstract
A primary challenge to creating an intelligent vehicle that can competently drive in traffic is the task of tactical reasoning: deciding which maneuvers to perform in a particular driving situation, in real-time, given incomplete information about the rapidly changing traffic configuration. Human expertise in tactical driving is attributed to situation awareness, a task-specific understanding of the dynamic entities in the environment, and their projected impact on the agent's actions. In this thesis, I demonstrate how situation awareness may be used as a basis for tactical-level reasoning in intelligent vehicles. SAPIENT (Situation Awareness Planner Implementing Effective Navigation in Traffic) combines a knowledge of high-level driving goals with low-level reactive behavior to control vehicles in a custom tactical-level simulator, SHIVA. The simulated vehicles are based on the Carnegie Mellon Navlabs, sharing a common perception and control interface, allowing researchers to port systems from simulation to real life with minimal modification. The first implementation, MonoSAPIENT, uses explicitly encoded rules for competent driving, along with specialized algorithms for gap selection and lane changing to drive safely in the simulated world. The second implementation, PolySAPIENT, is a distributed intelligence, built around the notion of reasoning objects, independent experts, each specializing in a single aspect of the driving domain. Each reasoning object is associated with an observed traffic entity, such as a nearby vehicle or an upcoming exit, and examines the projected interactions of that entity on the agent's proposed actions. Thus, a reasoning object associated with a vehicle is responsible for preventing collisions, while one associated with a desired exit recommends those actions that will help maneuver the vehicle to the exit. The results are expressed as votes and vetoes over a tactical action space of available maneuvers, and are used by a domainindependent arbiter to select the agent's next action. This loose coupling avoids the complex interactions common in traditional architectures, and also allows new reasoning objects to be easily added to an existing PolySAPIENT system. I also introduce a new learning strategy, based on the PBIL evolutionary algorithm, that simultaneously optimizes internal parameters for multiple reasoning objects given a user-specified evaluation metric. This automated parameter exploration also enables rapid prototyping of new PolySAPIENT configurations. iv v Acknowledgements
Many thanks to my advisors, Chuck Thorpe and Dean Pomerleau, for guiding me through my Ph.D. research. From the initial experiments with RACCOON on the Navlab to the last-minute PolySAPIENT hacking, they provided invaluable insights into the theory, as well as practical advice on the implementation. Thanks also to the other members of my thesis committee: Joe Kearney, for valuable discussions and detailed feedback on the earlier draft of this dissertation; and Haris Koutsopoulos, for his perspective on how my work fits into the context of an intelligent transportation system. John Hancock has collaborated with me on the SHIVA simulator for the last two years. His great ideas and solid code have helped make SHIVA into a useful research tool. Shumeet Baluja introduced learning to PolySAPIENT in the form of his elegant evolutionary algorithm, PBIL. John and Shumeet's harsh (yet constructive) feedback, given during numerous 3 a.m. debugging sessions helped this thesis greatly. Parag Batavia, Michelle Bayouth, Frank Dellaert, Dave Duggins, Jay Gowdy, Bala Kumar, Julio Rosenblatt, and Liang Zhao all gave useful ¨ ¨ suggestions for my research. Farokh Eskafi, Aleks Gollu, and others at UCB/PATH provided new perspectives and good ideas on simulation during my summer in Berkeley. Thanks to Charalambos Athanassiou, Mei Chen, Ian Davis, Wes Huang, Dave LaRose, Dirk Langer, Rich Madison and other grad students in VASC for their help over the years. And thanks also to people in the SCS environment who kept things running: Marie Elm, Jim Moody, Marce Zaragoza, and Kris Hutchings (for fixing my Zeos Palmtop with a thumbtack). My best friend, now my wife, Gita, participated in every aspect of this work. On the technical side, she wrote the Perl data manipulation programs, tamed my Linux machine, suggested research ideas, proofread several versions of this document, and generated the SGI videos for my thesis defense. She also lived my eccentric schedule, shared my dreams, and loved me unconditionally. It is good to be done. vi Contents
Abstract Acknowledgements 1 Introduction 1.1 Intelligent Vehicles . . . . . . . . . . . . . . . . . . . . . . 1.2 The AHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Driving in Traffic . . . . . . . . . . . . . . . . . . . . . . . 1.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Human Driving Strategies 2.1 Driver Models . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Task Models . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Risk Models . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Perceptual and Motivational Models . . . . . . . . vii iii v 1 2 3 5 8 15 16 16 18 20 viii CONTENTS
2.1.4 Control Models . . . . . . . . . . . . . . . . . . . . 2.1.5 Situation Awareness . . . . . . . . . . . . . . . . . 22 23 24 25 26 27 28 29 30 31 34 36 38 40 44 47 47 48 49 2.2 Tactical SA . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Real-time reasoning in dynamic environments . . 2.2.2 Information overload . . . . . . . . . . . . . . . . . 2.2.3 Positional maneuvering . . . . . . . . . . . . . . . 2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 The Simulation Environment 3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Road Representation . . . . . . . . . . . . . . . . . . . . . 3.4 Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Perception . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Car Detection and Tracking . . . . . . . . . . . . . 3.5.2 Lane Trackers . . . . . . . . . . . . . . . . . . . . . 3.5.3 Positioning . . . . . . . . . . . . . . . . . . . . . . . 3.6 Cognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Actuation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Design Tools . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS
3.8.1 Visualization and Validation . . . . . . . . . . . . . 3.8.2 Measurement and Analysis . . . . . . . . . . . . . 3.8.3 Interactive Exploration and Modification . . . . . 3.9 Scenario Generation . . . . . . . . . . . . . . . . . . . . . 3.9.1 Scenario Creation . . . . . . . . . . . . . . . . . . . 3.9.2 Scenario Manipulation . . . . . . . . . . . . . . . . 3.10 Saving the Simulation State . . . . . . . . . . . . . . . . . 3.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 MonoSAPIENT: Rule-Based SA 4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 System Overview . . . . . . . . . . . . . . . . . . . . . . . 4.3 Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Perception . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 The World Model . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Robot Self-state . . . . . . . . . . . . . . . . . . . . 4.5.2 Road State . . . . . . . . . . . . . . . . . . . . . . . 4.5.3 Traffic State . . . . . . . . . . . . . . . . . . . . . . 4.6 The Decision Tree . . . . . . . . . . . . . . . . . . . . . . . 4.7 Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 50 53 54 56 56 58 59 60 61 62 63 64 66 69 69 71 72 73 76 x CONTENTS
4.7.1 Deciding to Pass . . . . . . . . . . . . . . . . . . . . 4.7.2 Gap Reasoning . . . . . . . . . . . . . . . . . . . . . 4.7.3 Action Execution . . . . . . . . . . . . . . . . . . . 4.7.4 Aborted Lane Changes . . . . . . . . . . . . . . . . 4.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 80 83 85 86 91 92 93 93 98 5 PolySAPIENT: Distributed SA 5.1 System Overview . . . . . . . . . . . . . . . . . . . . . . . 5.2 Reasoning Objects . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Decomposing the Tactical Driving Task . . . . . . 5.2.2 The Structure of a Reasoning Object . . . . . . . . 5.3 Actions and Action Spaces . . . . . . . . . . . . . . . . . . 101 5.3.1 The Myopic Action Space . . . . . . . . . . . . . . . 103 5.3.2 The Global Action Space . . . . . . . . . . . . . . . 104 5.4 Action Selection . . . . . . . . . . . . . . . . . . . . . . . . 107 5.4.1 Related Work in Command Fusion . . . . . . . . . 108 5.5 Knowledge-Free Arbitration . . . . . . . . . . . . . . . . . 113 5.6 Action Execution . . . . . . . . . . . . . . . . . . . . . . . 116 5.6.1 Lateral Control . . . . . . . . . . . . . . . . . . . . 116 5.6.2 Longitudinal Control . . . . . . . . . . . . . . . . . 117 CONTENTS xi 5.7 Reasoning Object Complications . . . . . . . . . . . . . . 118 5.8 Independence Assumption Violations . . . . . . . . . . . . 123 5.9 Extending the PolySAPIENT Paradigm . . . . . . . . . . 125 5.10 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6 Learning Situation Awareness 129 6.1 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.2 PBIL: Evolving Intelligent Driving . . . . . . . . . . . . . 130 6.2.1 Internal Representation . . . . . . . . . . . . . . . 131 6.2.2 The Probability Vector . . . . . . . . . . . . . . . . 132 6.2.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . 133 6.3 Applying PBIL . . . . . . . . . . . . . . . . . . . . . . . . . 136 6.3.1 The Evaluation Function . . . . . . . . . . . . . . . 137 6.3.2 Parameter Encoding . . . . . . . . . . . . . . . . . 140 6.3.3 Training Scenarios . . . . . . . . . . . . . . . . . . 142 6.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.4.1 Evaluation Function Sensitivity . . . . . . . . . . 146 7 Evaluating Tactical Driving 151 7.1 Assessing SA . . . . . . . . . . . . . . . . . . . . . . . . . . 152 xii CONTENTS
7.2 Implicit Measures . . . . . . . . . . . . . . . . . . . . . . . 154 7.2.1 Insights into PolySAPIENT Training . . . . . . . . 155 7.2.2 Heavy Traffic on the Cyclotron . . . . . . . . . . . 162 7.3 Explicit Measures . . . . . . . . . . . . . . . . . . . . . . . 166 7.3.1 Stationary Obstacle: Emergency Braking . . . . . 167 7.3.2 Swerving a Stationary Obstacle . . . . . . . . . . . 169 7.3.3 Overtaking a Slow Vehicle . . . . . . . . . . . . . . 171 7.3.4 Exit Scenarios . . . . . . . . . . . . . . . . . . . . . 174 7.3.5 Discovered Check . . . . . . . . . . . . . . . . . . . 178 7.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.4.1 Escaping the Discovered Check . . . . . . . . . . . 182 8 Conclusion 183 8.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 183 8.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 186 8.2.1 Tactical Driving in Real Traffic . . . . . . . . . . . 186 8.2.2 Mixed Traffic Studies for the AHS . . . . . . . . . 188 8.2.3 Reasoning Objects in Other Domains . . . . . . . . 190 A PolySAPIENT Reasoning Objects 193 CONTENTS xiii A.1 Desired Velocity Reasoning Object . . . . . . . . . . . . . 193 A.2 Lane Reasoning Object . . . . . . . . . . . . . . . . . . . . 194 A.3 Vehicle and Obstacle Reasoning Objects . . . . . . . . . . 195 A.4 Exit Reasoning Object . . . . . . . . . . . . . . . . . . . . 196 A.5 Hysteresis Reasoning Object . . . . . . . . . . . . . . . . . 197 Bibliography 199 xiv CONTENTS Chapter 1 Introduction
Nowlan's Theory: He who hesitates is not only lost, but several miles from the next freeway exit [31]. Before the invention of the automobile, most forms of human transportation were, in some sense, intelligent. For example, a rider could rely on a horse's self-preservation instincts to avoid obstacles, or its sense of direction to find the way home [98]. Currently, the automobile possesses neither; a moment's inattention on a driver's part can cause the car to leave its lane, or crash into a nearby vehicle. Government studies attribute 96.2% of accidents in the U.S. to driver error [107]. A large fraction of these deaths could be prevented by the introduction of systems with the ability to make driving decisions in traffic, either to generate warnings for the human driver, or to control the vehicle un1 2 CHAPTER 1. INTRODUCTION der autonomous control. These intelligent vehicles would recapture the "lost intelligence" in transportation systems. 1.1 Intelligent Vehicles An intelligent vehicle is an automobile equipped with sensors, computers, and a control system. The sensors enable the vehicle to perceive the road, potential hazards, and other vehicles; the computers process this information and determine actions (such as steering or braking); the control system executes the chosen actions. In designs where the control system is not present (or is disengaged), the intelligent vehicle passively observes the traffic situation to issue warnings or recommendations for the human driver. The idea of a car that drives itself is not new. Research in the 1960s focused on the problem of semi-autonomous vehicle control with promising results [35, 70, 19]1 . Significant progress was made when visionbased lane-trackers were integrated with vehicle control systems, enabling robot cars to drive on clear highways under controlled circumstances [23, 54, 73]. Simultaneously, research in automatic headway control [16, 22] and convoying [34, 55] led to vehicles capable of autonomous car following [52, 101]. In 1995, an intelligent vehicle, the Carnegie Mellon Navlab 5, steered 98% of the distance between Wash1 Throughout this thesis, multiple references are listed in chronological order. 1.2. THE AHS 3 ington D.C. and San Diego (a distance of 2800 miles), demonstrating the maturity of this technology. One application of research in intelligent vehicles is an ambitious proposal known as the Automated Highway System -- a concept where large numbers of intelligent vehicles could be used to improve highway capacities and reduce traffic accidents. 1.2 The Automated Highway System
The proposal for an Automated Highway System (AHS) consists of intelligent vehicles operating on a roadway that is free of pedestrians and traffic control devices [15, 65, 89, 91]. All vehicles enter the AHS under human control. Following a successful check-in procedure, the intelligent vehicles switch to computer control. While on the AHS, the automated vehicles travel at high speeds, possibly with reduced headways, until they reach their destination exit. At this point, the human driver regains control of the vehicle. Proponents of the Automated Highway System believe that such a roadway will have two important benefits (in addition to user convenience): 1) a reduction in traffic accidents; 2) an improvement in highway throughput. Both are briefly discussed below. Computer-controlled vehicles, unlike human drivers, are not subject to boredom, fatigue, or distractions. Since single vehicle roadway de- 4 CHAPTER 1. INTRODUCTION parture crashes (caused by driver inattention or impairment) account for almost 15000 deaths in the U.S. annually [115], even the introduction of a simple lane-keeping system (such as [74]) could reduce fatalities. Further improvements would require intelligent vehicles to understand the concept of driving in traffic: inhibiting unsafe lane changes, initiating swerving maneuvers (to avoid obstacles), and responding to tailgating. By combining an awareness of the traffic situation with super-human reflexes, it is conceivable that computer controlled vehicles will significantly improve safety on highways. Intelligent vehicles could improve highway capacities in the following ways. First, intelligent vehicles could drive with reduced headways (in extreme cases, as small as one meter [110]), greatly increasing highway throughput. Second, the intelligent vehicles could help damp out traffic waves caused by abrupt acceleration and braking on the highway. Third, the intelligent vehicles could all be instructed to travel at a speed that is globally optimal for highway throughput. Several competing designs (known as AHS concepts) promise these benefits to different degrees. Some advocate that all vehicles on the AHS be computer-controlled (dedicated-lane concepts) while others allow autonomous and human-controlled vehicles to share the highway (mixed-traffic concepts). In the former, the intelligent vehicles can rely on protocols established using communication with the infrastructure and other smart cars (as described in [110]) to execute lane-changing and exit maneuvers. In the latter, the intelligent vehicles must compe- 1.3. DRIVING IN TRAFFIC
tently drive in uncontrolled traffic, much as human drivers do today. 5 Naturally, AHS concepts which require communication or substantial infrastructure modification cannot be deployed quickly on a large scale -- particularly since the prohibition on human-controlled vehicles prevents the incremental conversion of existing highways into dedicated AHS roadways. Therefore, mixed traffic concepts must be investigated, not only as possible AHS goals, but as potential solutions to the dedicated concept deployment problem. Whether autonomous navigation in mixed traffic is possible is an open research question2 . 1.3 Driving in Traffic
Given that a robot van steered 98% of a cross-country highway journey autonomously, one could believe that the problem of driving in traffic had already been solved. This is not true for two reasons. First, it is important to realize that the intelligent vehicle was stable in the presence of other vehicles, but that it did not react to them. Thus, the Navlab did not pass slower traffic (unless directed by the human driver), nor did it change lanes in preparation for a chosen exit -- the intelligent vehicle lacked any higher-level understanding of the traffic situation. Second, most highway drives have long periods of quiescence, interspersed
2 Reddy [79] notes that the development of an intelligent vehicle capable of com- petent driving on real roads is one of the central problems in Artificial Intelligence today. 6 CHAPTER 1. INTRODUCTION with brief bursts of intense activity (particularly near on-ramps or exits) where the driver changes lanes and speeds to achieve short-term goals. In the No Hands Across America trip, these maneuvers were performed by the human driver; the 98% statistic, which only considers raw distance, fails to capture this distinction. Driving in traffic is very difficult for intelligent vehicles because good decisions need to be made given only incomplete information, in real time. Standard AI techniques such as search-based planning [30] are infeasible for several reasons. First, the effects of the robot's actions on the environment (especially other vehicles) cannot be determined. Second, most of these methods cannot function under noisy, uncertain conditions. Third, the state-space is extremely large if realistic maneuvers such as aborted lane changes are taken into account. The scenario shown in Figure 1.1 illustrates some important elements of the problem of driving in traffic. Here, Car A, the vehicle of interest3 , is following a slow-moving vehicle, Car B, in the right lane of a divided highway. Car A would like to overtake Car B, but would prefer not to miss its upcoming exit. The decision on whether or not to pass depends on a large number of factors including: the distance to the exit, the speeds of Cars A and B, Car A's preferred velocity, and the traffic in the area. Human drivers face such situations regularly and make good decisions with little conscious thought. Psychologists
3 Throughout this thesis, the phrase "the intelligent vehicle" refers to the particu- lar vehicle of interest (also shown consistently as Car A in scenario diagrams). 1.3. DRIVING IN TRAFFIC 7 A B GOAL Figure 1.1: A scenario illustrating the problem of driving in traffic. attribute this competence to a task-specific understanding of the situation, termed situation awareness. According to situation awareness theories, Car A's driver has been monitoring several entities in the traffic scene for some time (such as Car B, the desired exit, and vehicles in the passing lane), and has formed expectations on how the scenario will unfold over time [26]. This information enables the driver to select an appropriate maneuver. My thesis research develops cognition systems for intelligent vehicles that demonstrate a similar situation awareness. The problem of navigating in traffic should be examined in the context of the entire driving task. In [67], driving is characterized as consisting of three levels: strategic, tactical and operational. At the highest (strategic) level, a route is planned and goals are determined. At the intermediate (tactical) level, maneuvers are selected to achieve shortterm objectives -- such as deciding whether to pass a blocking vehicle, as shown in Figure 1.1. At the lowest (operational) level, these maneuvers are translated into steering, throttle, and brake commands. 8 CHAPTER 1. INTRODUCTION Mobile robot research has addressed these three levels to different degrees. Strategic-level route-guidance has been successfully tackled using standard AI search techniques on digital maps using GPS positioning information [24, 100, 83, 113]. Operational-level systems have become increasingly robust, allowing intelligent vehicles to be reliably controlled on real highways [106, 63, 36, 62]. However, the tactical level, critical to the deployment of intelligent vehicles, has not been rigorously addressed. 1.4 Thesis Overview In this dissertation, I present solutions to the tactical driving task. My goal is to create cognitive modules which enable intelligent vehicles to drive competently in mixed-traffic highway situations by combining an understanding of high-level goals with low-level reactive behavior. Such systems: · Assume the current state of sensing and computing technology · Depend only on the existing roadway infrastructure · Do not rely on communication with other vehicles on the highway Chapter 2 presents an overview of current situation awareness (SA) theories. SA offers a cognitive model of the human real-time decision 1.4. OVERVIEW 9 making process. While SA research to-date has focused primarily on air combat applications, I illustrate how SA may be applied to tacticallevel action selection for driving. I then explore how SA may be used as a basis for autonomous tactical driving systems for intelligent vehicles -- and propose the design of such a novel system. SAPIENT (Situation Awareness Planner Implementing Effective Navigation in Traffic) is conceived as a tactical system interfacing with existing perception and control modules on the Carnegie Mellon Navlab [106] robots. While SAPIENT is designed to be implemented on the Navlab, real traffic is (at least initially), an unsuitable testbed for several reasons. First, exploring new tactical algorithms in close proximity to other vehicles at high speeds is obviously unsafe. Second, the current configuration of car-sensing equipment on the Navlab does not provide adequate coverage of the areas beside and behind the robot. Finally, coordinating multiple, moving vehicles on the highway to create tactical scenarios is difficult. A natural solution is to develop reasoning systems in simulation. SHIVA (Simulated Highways for Intelligent Vehicle Algorithms), described in Chapter 3, is a traffic micro-simulator and design tool emphasizing tactical-level issues. SHIVA's simulated vehicles are functionally similar to the Navlabs and share a common control interface -- allowing researchers to port algorithms from simulation to robot with minimal modification. Additionally, SHIVA offers specialized features for scenario creation, visualization, and interactive debugging of intelligent vehicle algorithms. 10 CHAPTER 1. INTRODUCTION Chapter 4 describes the initial SAPIENT implementation, known as MonoSAPIENT. The system architecture is traditional: perception modules sense objects in the scene and update a global world model representing all of the relevant traffic entities; analytical algorithms such as gap reasoning manipulate this world model to derive desirable future positions for the intelligent vehicle; a decision tree selects the best action based on the current cognition state (e.g., "executing a left-lane change"); the chosen tactical action modifies the cognition state and generates operational-level commands; finally, these commands are sent to the robot's controller for execution. The competence of this implementation depends largely on the sophistication in the MonoSAPIENT decision tree. Unfortunately, the cognition states and interactions between the various rules explode exponentially in such monolithic systems as new functions are implemented [21]. Additionally, modifying the decision tree requires large numbers of non-local modifications -- an error-prone and time-consuming task for researchers. To address these deficiencies, a distributed implementation of the reasoning system is proposed. Chapter 5 details the distributed implementation of SAPIENT, termed PolySAPIENT. This architecture is built around the notion of reasoning objects, independent experts which monitors local aspects of the traffic scene. Each reasoning object is implemented using whichever AI techniques are natural for its task -- for instance, some reasoning objects employ rule-based algorithms, others rely on potential field approaches, etc. The recommendations from each reasoning object are 1.4. OVERVIEW 11 expressed in a common language: as votes and vetoes distributed over a tactical action space. A knowledge-free arbiter examines the votes generated by each expert to determine the appropriate tactical-level response. This action, is translated into operational-level commands for execution by the intelligent vehicle controller. PolySAPIENT is successful because the tactical driving task can be decoupled into relatively independent subtasks (represented by the individual reasoning objects). Thus, adding functionality to the system only requires the implementation and addition of new reasoning objects -- the existing objects and the arbiter do not need to be modified. While the distributed implementation of SAPIENT successfully addresses the criticisms raised in Chapter 4, it still leaves the problem of parameter optimization: the behaviors of individual reasoning objects depend upon a number of internal settings (such as thresholds or gains), and the votes from the different reasoning objects are scaled with external weights. Adjusting these parameters manually is a tedious task for humans, particularly when the meanings of these variables is not intuitive. Chapter 6 discusses approaches for automatically tuning PolySAPIENT reasoning object parameters. Most conventional supervised learning techniques, such as neural networks trained using backpropagation [56], fail in this domain because tactical-level training signals are not available at each time step, but rather, only at the end of a scenario. I introduce a method relying on three components: 1) an evolutionary algorithm, termed PBIL (Population Based Incremental Learning) [14]; 2) a user-defined evaluation function which describes the de- 12 CHAPTER 1. INTRODUCTION sired vehicle behavior; and, 3) a set of training scenarios generated in the SHIVA simulation environment. The learning progresses in an iterative manner summarized as follows. PBIL stochastically generates a population of candidate parameter values based upon its accumulated statistical understanding of the domain. These parameters are instantiated as PolySAPIENT reasoning objects for simulated vehicles, and tested over the set of SHIVA scenarios. The scores received by the parameter values are then used by PBIL to adjust its internal statistics -- and this process is repeated. Over time, this technique generates high-scoring parameter values with a high probability. The tactical driving application challenges PBIL in a number of ways. First, since a vehicle's decisions depend on the behavior of other vehicles which are not under its control, the evaluation function is stochastic. Second, the PBIL algorithm is never exposed to all possible traffic situations. Third, since each evaluation takes considerable time to simulate, minimizing the total number of evaluations is important. The solutions to these problems are detailed in the chapter. Chapter 6 also discusses a novel application for learning: as a tool to explore the viability of reasoning object configurations in PolySAPIENT. Researchers can quickly determine whether a particular set of reasoning objects will be able to drive successfully by seeing if PBIL is able to find high-scoring parameter settings. This rapid prototyping can also be applied to the debugging of reasoning object representations. 1.4. OVERVIEW 13 Throughout this thesis, I have used scenarios to illustrate tactical situations, train SAPIENT vehicles and evaluate potential solutions. Chapter 7 classifies tactical-level scenarios collected from real-life situations and examines the cognitive processing required to solve them. Scenarios have been successfully used in situation awareness literature to evaluate SA in human experts [25, 32, 90, 94, 86]. I extend this approach to assessing SA in tactical reasoning systems. Two types of experiments are proposed and performed: 1) a detailed examination of the decisions made by the intelligent vehicle over a set of microscenarios. 2) an observation of the behavior of large numbers of intelligent vehicles, driving using different tactical reasoning systems, on a macro-scenario. Finally, Chapter 8 reviews the role of situation awareness in the tactical driving domain. The systems presented in the earlier chapters demonstrate that intelligent agents can exhibit competent tactical-level behavior. I briefly discuss the implications of intelligent vehicles in mixed traffic situations and present the contributions of this thesis in three main areas: artificial intelligence, machine learning, and simulation. This research can be extended in a number of interesting directions; I conclude with a brief look at some topics for future work. 14 CHAPTER 1. INTRODUCTION Chapter 2 Human Driving Strategies
Let us not look back in anger or forward in fear, but around in awareness. --Unknown Tactical-level driving is characterized by the constant battle between long-term goals and real-time constraints. Drivers must select appropriate maneuvers such as lane changing, accelerating, and car following given very little knowledge of the intentions of other drivers in their environment. In this fluid problem space, optimal solutions are rarely to be found, but the penalties for bad decisions are clear and severe. Unfortunately, safety cannot be guaranteed, even by conservative driv15 16 CHAPTER 2. HUMAN DRIVING STRATEGIES ing1 -- some level of risk-taking is unavoidable. Tactical driving thus forces a careful balance between competition and cooperation: aggressive maneuvering is successful, but not when it results in a crash. The only examples of competent tactical driving to date are human drivers. This chapter examines models for human competence to see if similar methods may be used to create competent automated driving systems. The impatient reader is referred to Chapters 4 and 5, where these ideas are implemented. 2.1 Driver Models Human driver modeling is an interdisciplinary endeavor involving a number of fields including robotics, psychology, control theory and statistics. In this section I examine models from some representative categories and focus on their relevance to tactical-level reasoning. 2.1.1 Task Models
Task models define the broad tasks involved in driving (e.g., car following), and decompose these tasks into detailed subtasks (e.g., headway
1 A driver can be involved in collisions through no fault of his/hers; tailgating, reckless lane-changing, and animals jumping onto the highway can all precipitate a crash. 2.1. DRIVER MODELS 17 maintenance). McKnight and Adams [66] presented a comprehensive treatment of the situations and actions involved in driving. However, since their report was targeted towards human driver education, most of the recommendations, such as "[When passing, the driver] selects a lane relative to his car's speed, maneuvers, and traffic flow", are too vague to be directly used in tactical reasoning systems. A second difficulty with most task models is that, like proverbs2 , the recommendations are often contradictory. As Reece [80] observes, the McKnight and Adams task list includes two subtasks that instruct drivers to "observe pedestrians and playing children" and to "ignore activity on the sidewalk that has no impact on driving" without providing insights as to which sidewalk activities have no impact on driving. Since these discriminating between these situations requires "common sense", encoding this knowledge in the form of driving rules for a reasoning system is challenging. Task models are nevertheless useful in this thesis research for two reasons. First, they highlight aspects of the tactical driving task that should be need to be addressed by an intelligent vehicle. Second, they provide insights about mapping observable phenomena into specific conditions (e.g., the driver should initiate an overtaking maneuver in response to a slower vehicle ahead). 2 For example, "haste makes waste", and "a stitch in time saves nine", prescribe opposite responses in similar situations. 18 CHAPTER 2. HUMAN DRIVING STRATEGIES 2.1.2 Risk Models
Risk models for driving have emerged from psychological research in the area of perceived risk. By combining the decision theoretic notions of expected utility and the willingness of humans to take "acceptable risks", these models attempt to explain commonly observed phenomena such as speeding, aggressive driving styles and intoxicated driving. Although robot vehicles are not likely to engage in such behavior, intelligent systems demonstrating situation awareness may require sophisticated models of human drivers. Utility functions based on perceived risk (such as time-to-impact measures) can also be used by reasoning systems to select tactical-level maneuvers (See Chapter 5). A representative example of a risk model is Wilde's Risk Homeostasis Theory: Risk Homeostasis Theory maintains that, in any activity, people accept a certain level of subjectively estimated risk to their health, safety, and other things they value, in exchange for the benefits they hope to receive from that activity [120]. Counterintuitively, risk homeostasis theory predicts that humans adjust their behavior so as to maintain (rather than minimize) their perceived risk at a constant set-point risk level: The degree of risk-taking behavior and the magnitude of loss . . . are maintained over time, unless there is a change in the target level of risk [120]. 2.1. DRIVER MODELS 19 A case study, known as the Munich Taxicab Experiment [7] was conducted to test the implications of risk homeostasis theory under controlled conditions. Some vehicles in a taxi fleet were equipped with an anti-lock braking system (ABS) that allowed drivers to maintain steering control during hard braking on slippery roads. Conventional wisdom predicted that the ABS-equipped vehicles would be safer than unequipped vehicles. Surprisingly, the results showed that: [7, 120]: · Among the accidents involving the company's taxis, there was no statistically significant difference between the involvement rate of the two vehicle types (in fact, the ABS vehicles were involved in slightly more accidents). · Accident severity was independent of the presence or absence of ABS in the taxi. · Accelerometers installed in the taxis measured more extreme decelerations (associated with hard braking) in vehicles equipped with ABS. · Drivers in ABS cabs made sharper turns in curves, were less accurate in lane-keeping behavior, maintained shorter headway distances, made poorer merge maneuvers and created more "traffic conflicts". All of these differences were statistically significant. Thus risk homeostasis theory, as supported by such experiments, has pessimistic predictions for any attempt to improve highway safety solely 20 CHAPTER 2. HUMAN DRIVING STRATEGIES through technology. However, in the context of tactical-level reasoning, risk homeostasis theory provides support for utility-based approaches to situation awareness (See Chapter 5). 2.1.3 Perceptual and Motivational Models
Perception models have been used to describe driver behavior in accidents [109], suggest methods for safer driving [117, 118] and motivate new collision warning devices [8]. In the tactical driving domain, perceptual models are particularly relevant in two areas: sensor modeling and driver intentions. Sensor modeling at the operational level is primarily concerned with tracking objects and segmentation (low-level actions which humans typically take for granted). At the tactical level, the focus shifts to reasoning about object-to-lane mapping, blind spots and occlusions -- tasks which human drivers perform more consciously. Unsurprisingly, novice drivers are less adept at these higher-level tasks: for example, inexperienced drivers are likely to forget about vehicles which are not currently visible [118]. Perceptual models also lead to heuristics for safer driving which can be exploited by both humans and intelligent vehicles (e.g., "At night, don't over-drive the range of your headlights"). The perceptual motivation for positional maneuvering is further discussed in Section 2.2.3. 2.1. DRIVER MODELS 21 In partially automated systems, the intelligent vehicle must be sensitive to its driver's intentions. Perceptual models can be used to gain some insights into this area: recent research [71] shows that drivers' eye fixation patterns are strongly correlated with their current mental state. In Pentland and Liu's system, the driver's internal state is modeled as a four-state Hidden Markov Model (HMM). Once the HMM has been trained, the system is able to predict when the driver is about to brake or turn. This knowledge may then be used by the intelligent vehicle to optimize its behavior for the expected maneuver -- in some sense, the situation awareness is shared over the driver-vehicle system. The notion of a driver's internal state is central to motivational models. In this framework, perceptual information is integrated with discrete mental states in an attempt to predict the actions that a human driver would take in that given situation [108]. This description of human cognitive activity can also involve aspects from utility theory -- generally in the form of a "perceived risk" factor. Although some effort have been made to specify motivational models in a symbolic programming language [1], no successful implementation currently exists. In MonoSAPIENT (See Chapter 4), discrete internal states, analogous to mental states here, are used to differentiate the different modes of driving (e.g., car following vs lane-changing behavior). 22 CHAPTER 2. HUMAN DRIVING STRATEGIES 2.1.4 Control Models Control models for drivers are primarily important when modeling operational level phenomena. For example, the well-known "Two-Second Rule" for car following [92] is based on the observation that humans require approximately 1.75 seconds to identify and react to a potentially dangerous situation [66]. Lane-keeping and steering models such as pure-pursuit tracking [114] are valuable at the tactical-level. First, such models can help the intelligent vehicle predict the future likely positions of observed vehicles. Second, such models can allow the reasoning system to estimate the time needed to execute a given maneuver (such as a lane change). Control models can also be applied to plan recognition -- for example, a Hidden Markov Model (HMM) could be used to predict the "internal states" of the other vehicles in the area. Other control models have been developed in the traffic simulation domain. The ones of most interest to tactical driving research are those which model lane-changing [116, 2], car following [124], and emergency maneuvers [3]. Since these models are computational, they can be directly incorporated into tactical reasoning system, as described in Chapters 4 and 5. 2.1. DRIVER MODELS 23 2.1.5 Situation Awareness
Models of human competence have been developed to describe expert performance in other domains. While these are not generally classified as driver models, they are nevertheless applicable to the tactical driving task. The primary example of such a theory is situation awareness (SA), described as: [An expert's] perception of the elements in the environment within a volume of time and space, the comprehension of their meaning, and the projection of their status in the near future [25]. Situation awareness was first discussed in connection with pilot performance in air-to-air combat and was seen as the critical difference between fighter aces and ordinary pilots [45, 50, 87, 72]. Subsequent research has also connected SA with the ability of commercial airline pilots to fly in difficult conditions [95], the success of commanders to make decisions in tactical battle simulations [99] and the effectiveness of medical technicians during emergency room procedures [46]. In this thesis, I show how the principles behind situation awareness are applicable to driving in traffic, and how the methods used to test situation awareness in human experts can be extended to assessing SA in intelligent vehicles (See Chapter 7). 24 CHAPTER 2. HUMAN DRIVING STRATEGIES Situation awareness theory has motivated intelligent systems in other domains. TacAir-Soar [85] is an intelligent automated agent for simulated fighter planes. The goal of the project is to develop automated pilots whose behavior in simulated battlefields is indistinguishable from experienced human pilots. Current versions have demonstrated some competence in one-on-one scenarios similar to those used in real training missions. An interesting feature of this system is that the automated pilots can be "debriefed" using a natural language interface. The researchers claim that the ability to explain why the agent made critical decisions is vital in demonstrating the system's situation awareness. Other work in this area includes: a proposed "Information Manager" for pilot decision support [95] and a proposal for a blackboard architecture-based combat helicopter system [9]. 2.2 Situation Awareness in Driving To see how SA theories originating in tactical combat may be applied to tactical-level driving, it is instructive to note the similarities between air-to-air combat and navigating in traffic. First, both tasks require real-time reasoning in dynamic, uncertain environments. Second, pilots and drivers face information overload since extracting (only) the relevant information from the available sensors is challenging. Third, positional maneuvering is critical in both arenas: combat aircraft seek to achieve desirable configurations relative to the enemy such as higher 2.2. TACTICAL SA 25 altitude, or an advantageous geometric potential [125] while vehicles in traffic seek to maintain space cushions, find suitable gaps and avoid driving in blindspots [66]. 2.2.1 Real-time reasoning in dynamic environments Traditional artificial intelligence techniques are well suited to solving problems where initial and goal states can be clearly specified. Given sufficient time, powerful search methods can efficiently find optimal solutions. Unfortunately, the agent's knowledge of the environment, in both air-to-air combat and tactical driving, is very incomplete (and constantly changing). Optimality is ill-defined and time constraints require that satisfactory actions be taken at every instant. The number of possible states, given a particular action on the agent's part, is very large. In the absence of a higher-level structure, the search space quickly explodes. Furthermore, new information is revealed as the agents change their configurations, and selected plans may become invalid with the changing situation. Maintaining detailed plans about long-term goals is impractical ­ rather the agent must focus on shortterm planning given the available information. 26 CHAPTER 2. HUMAN DRIVING STRATEGIES 2.2.2 Information overload Pilots and drivers receive information about their environment not as a concise list of symbols, but as a constantly changing set of sensor readings. Since time constraints prevent processing all of this information at every time instant, the agent must intelligently select the information most critical to the immediate task. Reece addressed the issue of information overload for robot driving through selective perception [80]. His system, Ulysses exploited the fact that reasoning could be simplified by first focusing on those objects in the environment that most constrain the agent's available actions. For example, when approaching an intersection with a Stop sign, the driver can safely ignore the trajectories of vehicles beyond the intersection, since the Stop sign forces the ego-vehicle to come to a halt. Further improvements were possible by making some assumptions about objects in the environment: for example, upon first observing an oncoming vehicle the agent could note its position and velocity, then "forget" about the vehicle for some time interval -- knowing that the vehicle would not be able to close the distance in that time. Reece showed that selective perception techniques reduced average perceptual costs in simulated scenarios by several orders of magnitude. However, when an object in the environment violates these assumptions, selective perception can cause the agent to unintentionally place itself in a more dangerous situation. For example, vehicles that have stopped on the highway are extremely hazardous to drivers who "over-drive" their headlights. 2.2. TACTICAL SA 27 2.2.3 Positional maneuvering Drivers, unlike fighter pilots, are not typically interested in maneuvering to gain an offensive advantage over other vehicles as a prelude to combat. However, according to defensive driving theory [118, 68], certain configurations of vehicles in traffic are inherently risky while others are relatively safe. This is due to several factors: perceptual limitations; incomplete knowledge of driver intentions; and, availability of escape routes. The first factor can be caused by either incomplete sensor coverage (e.g., blind spots) or environmental aspects (e.g., glare for vision sensors). Under these circumstances, the driver may not be able to accurately sense the positions or velocities of nearby vehicles. The resulting increase in uncertainty restricts safe options and motivates well-known heuristics like "Avoid staying in a vehicle's blind spot" and "Don't overtake as you approach a hill". The second factor is caused by imperfect communication between vehicles. Although turn indicators, brake lights and hand signals can all provide some indication of other drivers' intentions, it is clear that these are not perfect predictors of the future states of nearby vehicles. While all drivers need to make assumptions on the behavior of other vehicles, relying on these assumptions is unwise -- an adjacent driver may suddenly change lanes, or a tailgater may fail to react in time. The third factor is a direct result of overcrowding: for example, driving beside a vehicle limits lane chang- 28 CHAPTER 2. HUMAN DRIVING STRATEGIES ing options. Defensive driving theory thus stresses the importance for each driver to maintain a space cushion (an area free of other vehicles) around the vehicle whenever possible. 2.3 Discussion Human driving strategies, and in particular, situation awareness theories, offer valuable insights to the driving researcher. The task-level descriptions structure the driving problem into smaller, manageable components while SA provides a domain-independent framework for processing the perceptual inputs to the sy