CALIFORNIA PATH PROGRAM INSTITUTE OF TRANSPORTATION STUDIES UNIVERSITY OF CALIFORNIA, BERKELEY Towards a Fault Tolerant AHS Design Part I: Extended Architecture John Lygeros Datta N. Godbole Mireille Broucke California PATH Research Report UCB-ITS-PRR-96-14 This work was performed as part of the California PATH Program of the University of California, in cooperation with the State of California Business, Transportation, and Housing Agency, Department of Transportation; and the United States Department of Transportation, Federal Highway Administration. The contents of this report reflect the views of the authors who are responsible for the facts and the accuracy of the data presented herein. The contents do not necessarily reflect the official views or policies of the State of California. This report does not constitute a standard, specification, or regulation. June 1996 ISSN 1055-1425 (cid:3) Towards a Fault Tolerant AHS Design Part I: Extended Architecture John Lygeros, Datta N. Godbole, Mireille Broucke Department of Electrical Engineering and Computer Sciences University of California, Berkeley Berkeley, CA 94720 lygeros, godbole, [email protected] Abstract We propose a hierarchical control architecture for dealing with faults and adverse environ- mental conditions on an Automated Highway System (AHS). Our design builds on a previously designed control architecture that works under normal conditions of operation. The faults that areconsideredinourdesignareclassi(cid:12)edaccordingtothecapabilitiesremainingonthevehicleor roadside after the fault has occurred. Information about these capabilities is used by supervisors in each of the layers to select appropriate control strategies. We outline the extended control strategiesthatareneededbythesesupervisorsineachlayerofthehierarchyand,incertaincases, give examples of their detailed operation. A companion paper develops and veri(cid:12)es protocolsfor extended coordination strategies and maneuvers. Keywords Automated Highway System Design, Fault Tolerant Control, Safety (cid:3) ResearchsupportedbytheCaliforniaPATHprogram,InstituteofTransportationStudies,UniversityofCalifornia, Berkeley, underMOU-135 i Executive Summary The goal of the MOU 135 project is to extend the Automated Highway System (AHS) hierarchical control architecture of PATH to work under abnormal conditions such as adverse environment and system failures. Most of theresearch work inthe AVCSarea performedat PATH so farassumesthat the system is operating in the normal mode. The de(cid:12)nitionof \normal" may vary from case to case, but, ingeneral, itmeans benignenvironmentalconditionsandfaultlessoperationofallthehardware, both on the vehicles and on the roadside. Some studies to deal with \abnormal" conditions have been made (for example [Rao and Varaiya1994, Tomizuka et al.1994, Hitchcock1994]), but they are mostly concerned with speci(cid:12)c faults rather than a general framework. Our goal is to propose an AHS design that will perform well under almost any condition. The only abnormal conditions of operation that we do not consider are faults in the design (e.g., a deadlock in the communication protocols) and in the implementation of the software, since we assume the design will be veri(cid:12)ed before being implemented. Inthisreport, we proposea general framework for faulthandlingand recovery. The study results in a fault tolerant (degraded mode) control architecture for the AHS. The new architecture is a qualitative as well as a quantitative extension of the normal mode architecture. Qualitatively, the degraded modearchitecture maintains the hierarchicalstructureintroducedin[Varaiya1993] but it increases the autonomy of the system. This is achieved by adding to the design the capability to detect faults, determine their impact on the system capabilities, decide on a new control strategy and execute it. Moreover, the extended architecture adds new control laws and maneuvers in each level of the hierarchy, thus quantitatively extending the normal mode architecture. Duringthenormalmodeofoperation,theonlyinformationthatthelayersofthehierarchy needissensordata aboutthecurrentstate ofthesystem(includingthecontrolmessagespassedfrom one layer to the other). The degraded mode controllers however also need information about the current capability of the system (in addition to the sensor data) to select the best possible action. This additional information also needs to be presented in a form compatible with the abstraction of the controller at each layer of the hierarchy. We propose to extend the information (cid:13)ow by the additionof two more hierarchicalstructures. Thecapability structure encodes the discrete changes in the system capability due to faults in the vehicle and roadside hardware. The performance structure encodes the gradual degradation inthe system performancedue to adverse environmentalconditions and gradual wear of the vehicle components. These additional system monitors receive their inputs from fault detection and sensor fusion modules. We assume that the sensor structure and the fault detection module have already been designed for the normal mode (see for example [Alag et al.1994, Garg and Hedrick1993]). An important aspect of the degraded mode design is the system response strategies used to recover from the abnormal condition with safety and minimum throughput reduction. A compre- hensive list of faults, for both the vehicle and the infrastructure is presented in the Appendix. The capability and performance monitors are designed to induce a classi(cid:12)cation of faults. The classes re(cid:13)ect the capabilitiesremaininginthesystem inthepresence of a combinationof faultsandadverse conditions. New coordinated control strategies are designed for each class of failures. All strategies are implemented by a two stage process: a strategic planning stage, where a sequence of actions is planned to deal with the given degraded conditions and an execution stage where the chosen strat- egy is executed using specialized maneuvers. In case of failures on-board the vehicle, the degraded mode strategy is used to either stop the vehicle or take it to the nearest exit in cooperation with the neighboring vehicles. Infrastructure based link layer strategies are designed to divert the tra(cid:14)c around an incident using specialized queue management maneuvers. The strategies attempt to lo- calize the impact of the failure on the throughput while maintaining the safety of automated vehicle ii operation. New maneuvers and strategies (sequences of maneuvers) are outlined for the extended coordination and regulation layer. A companion report [Godbole et al.1995a] presents a complete design and veri(cid:12)cation of coordination protocols for the extended architecture. Insummary,wehaveproposedaframeworkforanAHSdesignthatiscapableofoperating in the presence of faults and other factors that induce performance degradation. Our framework is hierarchicalandbuildsonthecontrolarchitectureof[Varaiya1993]. Thedesignprovidesahighdegree of autonomy by extending the informationstructure to includedata about the system capabilityand the control structure to make a distinction between strategic planning and execution. Once the design of the control laws outlined in this report has been completed, the extended architecture can be implemented,inconjunction witha faultdiagnosis module,as a highlyautonomous faulttolerant control system for an AHS. iii Contents 1 Introduction 1 1.1 Overview of Normal Mode Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Outline of Proposed Solution 4 2.1 Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 General Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Hierarchical Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Information Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.3 Control Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 The Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Modeling Capability 7 3.1 Capability Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.1 Physical Layer Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.2 Regulation Layer Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.3 Regulation Layer Supervisor Capability Predicates . . . . . . . . . . . . . . . . 8 3.1.4 Coordination Layer Supervisor Predicates . . . . . . . . . . . . . . . . . . . . . 9 3.1.5 Link Layer Supervisor Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Performance Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.1 Robustness Analysis Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.2 Robustness Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.3 Degraded Mode Initiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Fault Classi(cid:12)cation 15 5 Control Design 17 5.1 Link Layer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.1.2 Link Layer Supervisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.1.3 Link Layer Regulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Coordination Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2.2 Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2.3 Maneuvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3 Regulation Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.2 Supervisor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3.3 Control Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4.1 Normal Mode Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.4.2 Degraded Mode Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Discussion & Further Issues 25 6.1 Design Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.2 Veri(cid:12)cation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 iv 7 Concluding Remarks & Future Work Directions 28 A List of Faults 31 A.1 Vehicle stopped/must stop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.2 Vehicle needs assistance to get out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.3 Vehicle needs no assistance to get out . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.4 Vehicle does not need to get out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.5 Infrastructure Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.6 Driver/Computer Interaction Down. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.7 Faults not considered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 B Causes of Gradual Performance Degradation 37 B.1 List of Causes: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 B.2 Performance Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B.3 Qualitative Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B.3.1 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 B.3.2 Sensors and Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 B.3.3 Regulation Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 B.3.4 Co-ordination Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 B.3.5 Link Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 v List of Figures 1 IVHS Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Overview of the Supervision Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Connection between Physical and Regulation layer capabilities . . . . . . . . . . . . . 8 4 Regulation layer supervisor capabilities. . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5 Coordination layer supervisor capabilities (normal mode) . . . . . . . . . . . . . . . . 11 6 On-line controller tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7 Introduction of robustness predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 8 Extended Architecture for Degraded Modes of Operation of AHS . . . . . . . . . . . . 17 9 Stage 1: Vehicle stopped on highway . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 10 Stage 2: Vehicle stopped on highway . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 11 Stage 3: Vehicle stopped on highway . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 12 Stage 4: Vehicle stopped on highway . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 13 Stage 5: Vehicle stopped on highway . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 14 Recovery after the stopped vehicle is towed away . . . . . . . . . . . . . . . . . . . . . 20 15 Desired velocity & density pro(cid:12)les for Stage 2 . . . . . . . . . . . . . . . . . . . . . . . 33 16 Take Immediate Exit: Highway Snapshots . . . . . . . . . . . . . . . . . . . . . . . . . 33 17 Take Immediate Exit - Escorted: Highway Snapshots . . . . . . . . . . . . . . . . . . . 34 18 Front Dock Maneuver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 19 Normal mode regulation layer supervisor . . . . . . . . . . . . . . . . . . . . . . . . . . 34 20 Outline of the degraded mode regulation layer supervisor . . . . . . . . . . . . . . . . 35 21 Fault Tolerant architecture: Fault handing and Robustness enhancement . . . . . . . . 36 vi 1 Introduction Intelligent Vehicle Highway Systems (IVHS) has been an active research area within the California 1 PATH project for the past several years. One of the main objectives is to develop an Automated Highway System (AHS) design that will signi(cid:12)cantly increase safety and highway capacity without building new roads, by adding intelligence to both the vehicle and the roadside. Several approaches to this problem have been proposed within the PATH project, ranging from Autonomous Intelligent Cruise Control (where the driver is in control of vehicle steering) to full automation. An underlying assumptioninmostofthesedesignshasbeenthattheoperationtakes placeundernormalconditions. Thede(cid:12)nitionof\normal"mayvaryfromcasetocase,but,ingeneral,itmeansbenignenvironmental conditionsandfaultlessoperationofallthehardware,bothonthevehiclesandontheroadside. Some studies to deal with \abnormal" conditions have been made (for example [Rao and Varaiya1994, Tomizuka et al.1994, Hitchcock1994]), butthey aremostlyconcerned withspeci(cid:12)cfaultsrather than a general framework. Our goal is to propose an AHS design that will perform well under almost any condition. The only abnormal conditions of operation that we do not consider are faults in the design (e.g., a deadlock in the communication protocols) and in the implementation of the software, since we assume the design will be veri(cid:12)ed before being implemented. Even with this restriction it is clear that the task is large. In this report we give an overview of what is involved and establish a framework for tackling the problem. The framework will partition the task into more manageable segments and formalize the requirements that each of them will need to satisfy. 1.1 Overview of Normal Mode Architecture Our framework builds on the control architecture proposed in [Varaiya1993] for normal modes of operation. Before presenting the framework for fault handling and recovery, we give a brief overview of the normal mode design to (cid:12)x the terminology and notation. The central concept of the architec- ture is that the AHS control problem is too large to be dealt with by means of a single controller. Therefore a hierarchical control structure is introduced. The design of the control hierarchy outlined in [Varaiya1993] centers around the notion of \platooning". It is assumed that tra(cid:14)c on the highway is organized in groups of tightly spaced vehicles, called platoons. Intuition suggests that doing this should lead to an increase in the ca- pacity and throughput of the highway; indeed theoretical studies indicate that, if such a scheme is implemented successfully, the resulting highway throughput can be as high as four times the current throughput. Moreover, this will be achieved without a negative impact on passenger safety. By having the vehicles within a platoon follow each other with a small intra-platoon separation (about 1-2 meters), we guarantee that ifthere isa failureandan impact isunavoidable, the relativespeedof the vehicles involved in the collision will be small, hence the damage to the vehicles and the injuries to the passengers will be minimized. The inter-platoon separation, on the other hand, is large (of the order of 30 meters) so that, if needed, the platoons will have enough time to come to a stop before they collide. In addition a large separation guarantees that transient decelerations will be attenuated as they propagate up the freeway. Clearly implementation of such a scheme will require automatic control of vehicles, as human drivers are not fast and reliable enough to produce the kinds of inputs necessary for forming platoons. In the architecture outlined in [Varaiya1993] the system is organized in (cid:12)ve layers (Fig- ure 1). The top layer, called the network layer, is responsible for the (cid:13)ow of tra(cid:14)c on the entire 2 highway system . Its task is to prevent congestion and maximize throughput by dynamic routing of 1 PATHstands for Partners for AdvancedTransit and Highways 2 The highway systemmightconsist of interconnection of several highways aroundan urbanmetropolis. 1 NETWORK LAYER SUGGESTED ROUTE HIGHWAY TRAVEL TIMES LINK LAYER Roadside DLPEARSNOIEPR OECRDHT AISNOPGNEESE ,D, A G G R E GFALTOEW TDRAATFAFIC Vehicle PLATOON SIZE COORDINATION LAYER MANEUVER REQUEST FLAGS & AGGREGATE SENSOR DATA REGULATION LAYER CONTROL INPUT RAW SENSOR DATA PHYSICAL LAYER (plant) Figure 1: IVHS Architecture tra(cid:14)c. Thesecondlayer, calledthelink layer,coordinatestheoperationofwholesections(links) of the highway and operates at the roadside. Its primary concern is to maximize throughput while maintaining safe conditions of operation. With these criteria in mind, it calculates an optimum platoon size and an optimum velocity for each highway section. It also decides which lanes the vehicles should follow to get to their destination as fast as possible. Finally, it monitors incidents on the highway and diverts tra(cid:14)c in order to minimize the impact of the incident on tra(cid:14)c (cid:13)ow and safety. Because the link layer bases its control actions on large numbers of vehicles, it treats the vehicles in a section in an aggregate manner rather than considering the state of individual vehicles or platoons. The commands it issues are not addressed to individual vehicles but to all the vehicles in a section; a typical command would be \30% of the vehicles going to the next exit should change lane to the right" or \all platoons in this section should be at most 10 vehicles long". A possible design for the link layer is described in [Rao and Varaiya1994]. It is based on a tra(cid:14)c (cid:13)ow model similar to the ones developed for manual tra(cid:14)c. The next level in the hierarchy below the linklayer is the coordination layer. It resides ineachvehicleandit’staskistocoordinatetheoperationofplatoonswiththeirneighbors. Itreceives the link layer commands and translates them to speci(cid:12)c maneuvers that the platoons need to carry out. For example, it will ask two platoons to join to form a single platoon whose size is closer to the optimum or, given a command like \30% of the vehicles going to the next exit change lane to the right", it will decide which vehicles comprise this 30% and split the platoons accordingly. The current design [Hsu et al.1994] uses protocols, in the form of (cid:12)nite state machines, to organize the maneuvers in a systematic way. They receive the commands of the link layer and aggregated sensor 2 informationfrom the individualvehicles (of the form \there isa vehicle in the adjacent lane"). They use this information to decide on a control policy and issue commands to the regulation layer. The commands are typically of the form \accelerate to join the preceding platoon" or \decelerate so that another vehicle may move into your lane ahead of you". Below the coordination layer in the control hierarchy lies the regulation layer. Its task is to receive the coordination layer commands and translate them to throttle, steering and braking input for the actuators on the vehicle. For this purpose it utilizes a number of continuous time feedback control laws ([Hedrick et al.1991, Peng and Tomizuka1990, Sheikholeslam and Desoer1990, Godbole and Lygeros1994,Godbole et al.1995b,Chee and Tomizuka1994])thatusethereadingspro- vided by the sensors to calculate the actuator inputs required for a particular maneuver. The regu- lation layer communicates with the coordination layer to inform it of the outcome of the maneuver. The following control laws are used in the regulation layer; lane keeping and lane changing control laws for lateral movement, leader and follower control laws used as the default longitudinal con- trollers, and longitudinal control laws for each maneuver, namely, join, split, entry (consisting of stop sign law and accelerate to enter law) and exit (consisting of catch up and platoon break up laws). The bottom layer of Figure 1 is not part of the controller. It is called the physical layer and it contains the actual plant (in this case the vehicles with their sensors, actuators and communication equipment and the highway topology). 1.2 Notation A number of \new" terms will be de(cid:12)ned throughout the paper. To help the reader keep track of them we will summarize these de(cid:12)nitions here. The term layer will be used to describe the layers of the architecture discussed above. For control under degraded conditions each of these layers will be divided into two levels. The top level in each layer will be called the supervisor. It will contain all the \intelligence" that determineswhenthe controlshouldswitch fromonemode ofoperationto another. Thebottom level will be called the regulator. It will be responsible for executing the strategy determined by the supervisor. Thecontrollerswillbearrangedinahierarchycalledthecontrol structure. Theymake use of information provided by the information hierarchies, the sensor structure, the capability structure and the performance structure. For degraded operation the coordination layer will be extended by adding a number of new strategies (compound maneuvers). They will be appropriate concatenations of atomic ma- neuvers. For brevity acronyms will be used to describe them. TIE, TIE-E, TIE-N, AS, CS and GS will be used for the compound maneuvers Take Immediate Exit, TIE-Escorted, TIE-Normal, Aided Stop, Crash Stop and Gentle Stop. FD, FS, GS, CS and ELC will be used for the atomic maneuvers Front Dock, Forced Split, Gentle Stop, Crash Stop and Emergency Lane Change. AHS will be used for Automated Highway System. 3