Patent Publication Number: US-10782700-B2

Title: Fault-tolerant method for operating an autonomous controlled object

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to and the benefit of EP application No. 17161533.9, filed Mar. 17, 2017, which is incorporated by reference herein in its entirety. 
     The invention relates to a method for operating a controlled object, for example a vehicle that is embedded in a changing environment, wherein an electronic system that implements the control system comprises sensors, in particular a plurality of sensors, actuators, in particular a plurality of actuators, and node computers, in particular a plurality of node computers, which exchange data via a real-time communication system. 
     The invention further relates to an electronic system, for example a computer system, for operating a controlled object, for example a vehicle, that is embedded in a changing environment, wherein the electronic system that implements the control system comprises sensors, in particular a plurality of sensors, actuators, in particular a plurality of actuators, and node computers, in particular a plurality of node computers, which exchange data via a real-time communication system. 
     The present invention is within the field of computer technology. It relates to a method and an electronic system for fault-tolerant operation of a controlled object, in particular of an autonomous controlled object, in particular of a vehicle. 
     The developments in sensor technology and computer technology permit the largely autonomous control of technical systems and objects, such as a vehicle, that autonomously heads for its destination. 
     According to Wikipedia [4], the classification of autonomous driving is organized in six levels:
     Level 0: “Driver only”, the driver himself drives, steers, accelerates, brakes, etc.   Level 1: Designated assistance systems help with vehicle operation (including ACC).   Level 2: Partial automation. Among others, automatic parking, lane-keeping function, general longitudinal guidance, acceleration, braking etc. are taken over by the assistance systems (such as traffic jam assistance).   Level 3: High-level automation. The driver does not have to monitor the system continuously. The vehicle conducts independent functions such as triggering turn indicators, lane changes and lane tracking. The driver can attend to other things, but is required to take over driving from the system within a preliminary warning period, as needed. This form of autonomy is technically feasible on highways. The legislature is working towards permitting Level 3 vehicles. There is talk of a time frame by 2020.   Level 4: Full automation. The guidance of the vehicle is continuously taken over by the system. If the driving tasks are no longer managed by the system, the driver may be required to take over the driving.   Level 5: Full autonomy of the vehicle. The vehicle is provided without a steering wheel; the vehicle can move around without a driver.   

     Level 2 is currently implemented in vehicles available on the market. At Level 2, the driver is required to continually monitor the proper functioning of the computer system and to intervene immediately in the event of a fault. At the higher automation levels, the computer system must be designed to be fault tolerant in order to guarantee the safety of the vehicle even in the event of an error in the computer system. 
     In the ISO 26262 standard, an electronic system (hardware plus software) in a vehicle must be assigned to one of four integrity levels (Level ASIL A to ASIL D), wherein the Level ASIL D represents the highest level of integrity [5]. The integrity of electronic systems for fully automated vehicle operation (Level 4 and Level 5) must conform to ASIL D. Whereas the probability for an occurrence of a dangerous error having serious implications for the safety of a vehicle at Level ASIL B must be less than 10 −6  per hour (i.e. 103 FIT), this probability at ASIL D must be less than 10 −8  per hour (i.e. 10 FIT). 
     The cause for the occurrence of a failure of an electronic system may be an error due to hardware aging (physical fault) or a design error (design fault) in the hardware or software. 
     An aging error is present if an assembly that was fully functional at the beginning of its useful life fails because of aging processes of the hardware. For state of the art automotive chips, the permanent error rate for errors due to aging is &lt;100 FIT. By using active redundancy (TMR or self-checking components), the required error rate for ASIL D (less than 10 FIT) can be achieved in the hardware. 
     Design errors may be present in the hardware or in the software. The consequences of hardware design errors can be mastered using the active redundancy of diversitary hardware. 
     Measures that result in a reduction in the probability of the presence of an undetected design error in the software are a systematic design process, verification and validation, primarily by comprehensive testing. 
     A significant cause of the occurrence of design errors in the software is the complexity of the software. According to the state of the art, it is possible to so thoroughly validate a complex software system that the required error rate for ASIL B can be achieved, but not that for ASIL D. 
     The fact that control systems (i.e. systems for the real-time operation and/or control of a controlled object), such as a subject electronic system, periodically run corresponds to the prior art [8, p. 7]. The controlled object is observed at periodic observation times (sampling points). The data collected as a result of this form the basis for the calculation, preferably as quickly as possible, of (new) target values for actuators that influence the behavior of the controlled object. 
     We refer to the periodically repeating execution of a sequence of possibly distributed calculations that are made after each observation as a frame. 
     The sequence of software processes that must be executed within a frame is defined in one or more data flow paths (DFPs). 
     Two time parameters are associated with each frame: 
     The execution time specifies the time interval between the sampling point and the instant of the output of the results of the frame to the actuators of the object to be controlled. The shorter the execution time of a frame, the better the quality of a control system. 
     The frame interval (sampling time) specifies the time lag between two consecutive sampling points. 
     It is an object of the invention to ensure the safe behavior of a controlled object, even if a hardware or software error occurs in a frame of the control system. 
     This object is achieved by a method mentioned above and an electronic system mentioned above, for example a computer system, in that the controlled object and its environment are periodically observed using sensors and in each frame, at least three independent data flow paths, DFPs, are executed based on the data recorded through the observation of the controlled object and its environment, wherein the observation is carried out, for example, for each DFP via different sensors, and wherein
         a first DFP determines from the data recorded by the observation of the controlled object and its environment via complex software a model of the controlled object and of the environment of the controlled object and, on the basis of this model, carries out a trajectory planning in order to create one or more possible trajectories that, under the given environmental conditions, correspond to a specified task assignment, and wherein   a second DFP determines from the data recorded by the observation of the controlled object and its environment via a, preferably diversitary, complex software a model of the controlled object and of the environment of the controlled object and, on the basis of this model, determines a safe space-time domain, SRZD, within which SRZD all safe trajectories must be located, and wherein
 
the results of the first and of the second DFP are transmitted to a deciding instance, wherein the deciding instance is realized via simple software, and wherein the deciding instance verifies whether at least one of the trajectories determined by the first DFP is safe, meaning located within the SRZD that was determined by the second DFP, and wherein, in the case that these match, one of the safe trajectories determined by the first DFP is selected, and wherein the deciding instance transmits the target values corresponding to the selected trajectory to an actuator control, and wherein, in the case that these do not match, it waits for the results of at least one following frame, and wherein, in the case that there is also no safe trajectory available in the following frame or the one after that, the deciding instance switches to an emergency trajectory.
       

     If, therefore, it is determined in one frame that none of the trajectories established by the first DFP in this frame is safe, meaning that none of the trajectories is located within the SRZD established by the second DFP, then, as described above, it will wait for the result in at least one of the frames following the frame under consideration, and if in the next frame or the one following that (with respect to the frame under consideration) there is also no safe trajectory available, the deciding instance switches to an emergency trajectory. 
     The present invention discloses a method and a hardware architecture for increasing the reliability of a complex electronics system. By targeted use of hardware and software redundancy, the reliability of the electronic system is significantly increased. The invention permits the integrated treatment of aging errors in the hardware and/or errors in the design of the hardware and/or the complex software. 
     For example, each DFP can use the observations of all of the sensors. It can also be provided, however that each DFP uses only the observations of certain sensors and it can also be provided, for example, that each DFP only uses sensors, meaning their observations, specifically assigned to it. 
     The sensors are preferably synchronized, meaning that all sensors conduct their observations simultaneously (periodically). 
     The DFPs are preferably each executed in one frame simultaneously. This means that, on the one hand, observations of the sensors take place simultaneously (see above) such that the DFPs begin at the same time, and that, in addition to this, the results of the DFPs are transmitted to the deciding instance at the same instant. 
     In the field of safety technology in air and space travel, a distinction is made between simple and complex software [6]. In general, we refer to software that verifies formally and/or can be tested comprehensively as simple software. If the software that is used is simple and formally verified and/or can be comprehensively tested, it is then assumed that the required error rate for ASIL D can be attained through a careful development process. 
     If the software that is used is complex, we assume that the probability for the occurrence of design errors corresponds to that of ASIL B. Through software redundancy, meaning the parallel execution of two or more diversitary ASIL B software systems with a subsequent, usage-specific comparison of the results, the reliability of the software can be significantly increased. A method for increasing software reliability by active redundancy (by means of diversitary software) is described in [7]. This method is not applicable, however, if the diversitary software versions do not behave in a replica deterministic manner. 
     Diversitary software is not replica deterministic if there is a non-deterministic design construct (NDDC) [8, p. 128] in the software. An NDDC decides between two correct but incompatible scenarios. In general, it cannot be assumed that two diversitary versions of the software having NDDCs will arrive at comparable results. 
     If, for example, there is a boulder in the street and a decision must be made whether this boulder should be bypassed on the left or the right, it cannot be generally assumed that two diversitary software versions will arrive at the same result. Although both results are correct, they are not replica deterministic. The error tolerance is thus lost. 
     The autonomous operation of a motor vehicle requires a software system for image recognition, environmental modeling and trajectory planning. This software system is not simple, but complex and usually includes NDDCs. 
     It is preferably proposed to divide the complete software system into two parts. One part comprises the complex software. The second part comprises simple software, preferably having NDDCSs. 
     The reliability of the complex software is significantly increased by the functional redundancy of two or more different versions of the complex software that are executed on independent fault containment units (FCUs). The reliability of the simple software is achieved through exhaustive testing and formal analyses. 
     In order to effect broad software diversity of the complex software, one software version calculates one or more suitable trajectories in the space-time continuum, while another independent software version determines a structure in the space-time continuum, within which each safe trajectory must be located. A third independent software version determines an emergency trajectory that guides the vehicle to a safe state. 
     A deciding instance that is implemented in simple software without software redundancy and preferably comprises NDDCs verifies the alternative results prepared by the complex software and decides which alternative is selected. This simple software is executed on preferably fault-tolerant hardware in order to mask hardware errors that arise. 
     The present invention describes an innovative method by which a complex electronic system for operating an, in particular, safety-critical controlled object, for example driving an autonomous vehicle, can be implemented. A decision is made between simple and complex software, wherein the simple software preferably is implemented on fault-tolerant hardware and wherein, for example, a plurality of diversitary versions of the complex software is simultaneously implemented in independent fault containment units (FCU) and where a result that is to be passed on to the actuators is selected by a deciding instance from the results of the complex software that is implemented using simple software. 
     Advantageous embodiments of the method or the system according to the invention are explained below:
         The calculations of the deciding instance can be executed on TMR hardware.   The calculations of the deciding instance can be executed simultaneously on two independent self-checking hardware units.   A third independent DFP can calculate an emergency trajectory that is sent to the deciding instance.   The deciding instance checks whether the emergency trajectory is safe after determining that the trajectory calculated by the first DFP is safe, and, in the case that the emergency trajectory is not available or safe, delivers an alarm message, for example to a user of the controlled object, e.g. to the driver of a vehicle.       

    
    
     
       In the following, the invention is described using an exemplary embodiment illustrated in the drawings. Shown in the drawings are: 
         FIG. 1  a data flow diagram of a complex electronic system for operation of a controlled object in the form of a vehicle, 
         FIG. 2  a possible hardware architecture for implementing the complex electronic system of  FIG. 1  having TMR hardware for implementing an NDDC, and 
         FIG. 3  shows a possible hardware architecture for implementing the complex electronic system of  FIG. 1  having a self-checking hardware for implementing an NDDC. 
     
    
    
     The following concrete description of an implementation addresses one of the many possible executions of the new method using the example of an autonomous vehicle control system. The description uses terms that are described more accurately below. These terms apply not only in the context of the description of the figures, but also in connection with the complete disclosure. 
     A controlled object (abbreviated CO) is a technical system that is controlled by an electronic system, for example a computer system, and/or a person and has the goal of performing a predetermined task over a period of time under the given environmental conditions. Examples of COs are: a vehicle, an airplane, an agricultural machine, a robot or a drone. 
     A task for a drone could comprise flying to a specified target while observing a closed section of the airspace, or while attaining a specified lowest flight height, etc. 
     An environmental model is a digital data structure that at a given instant represents an image of the essential characteristics of the environment for the specified task, in particular of the environment of a CO. An example of an environmental model is the description of a street and the static and dynamic objects found on the street at a given instant. 
     A trajectory is a path in the space-time continuum that a CO can follow in the course of time in order to complete a given task. The characteristics of the trajectories of a CO depend on the design of the CO, the given task and the current environmental conditions. For example, one can refer to a possible path that a vehicle can follow or cover under given environmental conditions in order to reach its destination as a trajectory. A characteristic of a trajectory or of the trajectories can be, for example, the speed with which the trajectory is traversed. 
     A software process is understood to be the execution of a program system on one or more computers. 
     A fault containment unit (FCU) is an assembly that encapsulates the immediate consequences of an error cause (6, p. 155). 
     The term fault-tolerant hardware is to be understood as a hardware architecture that masks hardware errors which arise that correspond to the aforementioned error hypothesis. Examples of such hardware architectures are triple modular redundancy (TMR) or the parallel implementation of software on self-checking assemblies as described in (6, p. 156). In accordance with the state of the art, the redundant FCUs receive their input data over at least two independent communications channels and transmit their output data over at least two independent communication channels. 
     A data flow path (DFP) is a sequence of distributed software processes, wherein the first software process reads input data and the output data of a previously stored software process represent the input data for the ensuing software process. The output data of the last software process are the result data of the DFP. In many usage cases of real-time data processing, the first software process of a DFP acquires the sensor data and the last software process of a DFP produces the target values for the actuators. 
     In most usage cases of real-time data processing, a DFP is cycled through. The time lag between two cycles is referred to as a frame. An inner state [8, p. 84] of a software process can be stored between two sequential frames of a DFP. 
     Two DFPs are diversitary if they pursue the same goal, but the software processes of the DFPs use different algorithms (algorithmic diversity) and/or different input data (data diversity). 
     Environmental modeling is a software process that creates an environmental model based on the static data of the environment and the dynamic data of the environment collected from different sensors. 
     A trajectory design is a software process that, on the basis of a given environmental model and a given objective, determines one or more possible trajectories which solve a predetermined task or objective. 
     The immediate future of an instant is the time interval that begins with the instant and ends as soon as the process (e.g. the vehicle) is in a safe state. 
     If, for example, 10 seconds are required in order to bring a vehicle to a standstill (safe state) and a sample rate of 30 frames per second is provided, the immediate future thus contains a sequence of 300 temporally equidistant instants. 
     A safe trajectory is a trajectory in the space-time continuum that describes the path of a process (e.g. of a vehicle) in the immediate future, wherein this path is free from obstacles and all boundaries relevant in the immediate future (e.g. driving-dynamic) are observed. 
     If, for example, the road is wet, the driving-dynamic boundaries must be set differently than when the road is dry. 
     An emergency trajectory is a safe trajectory that guides the process (e.g. the vehicle) into a safe state. 
     A safe space-time domain (SRZD) is a tubular structure in the space-time continuum, in which all safe trajectories in the immediate future are contained. 
     A deciding instance is a usage-specific software process that receives a number of proposals as input data, analyzes these proposals and has the freedom to arrive at a decision as to which—possibly changed—proposal is selected. In many cases, a deciding instance comprises NDDCs. 
     The normal operation is characterized in that a trajectory calculated by the trajectory planning is located in the safe space-time domain (SRZD). 
     For example, a deciding instance receives a number of proposals for possible trajectories of a vehicle as input and decides on one—possibly changed—trajectory that will be implemented. 
       FIG. 1  shows a data flow diagram of a complex electronic system for autonomous control of a vehicle. Vertical connection lines  100  of the box in  FIG. 1  show the data flow from top to bottom. 
     In  FIG. 1 , three diversitary DFPs  110 ,  120  and  130  are illustrated. Each of the DFPs provides observation of the environment of the vehicle via its own sensors. The sensors are read cyclically. First DFP  110  has sensors  111 , second DFP  120  has sensors  121  and third DFP  130  has sensors  131 . Examples of vehicle sensors are cameras, radar sensors, LIDAR sensors and ultrasound sensors. In the first processing step of the DFP, the raw sensor data are read out and pre-processed. That is software process  112  in DFP  110 , software process  122  in DFP  120  and software process  132  in DFP  130 . 
     It is advantageous if software processes  112 ,  122  and  132  use different algorithms (algorithm diversity) that are supplied with different input data (data diversity). 
     It is advantageous, if sensors  111 ,  121  and  131  observe the environment simultaneously. Simultaneous observation can be achieved via a distributed trigger signal derived from a fault-tolerant global time. 
     In the second processing step of the DFP, the environmental modeling is completed on the basis of the received sensor data and information about the static environmental parameters (e.g. from the maps of a navigation system). That is software process  113  in DFP  110 , software process  123  in DFP  120  and software process  133  in DFP  130 . 
     It is advantageous, if software processes  113 ,  123  and  133  use different algorithms (algorithm diversity) that are supplied with different input data (data diversity). 
     In the third processing step of first DFP  110 , that is, of software process  114 , trajectory planning is implemented on the basis of the environmental model produced by second processing step  113 . 
     In the third processing step of second DFP  120 , that is, of software process  124 , a safe space-time domain (SRZD), in which all safe trajectories must be located, is determined on the basis of the environmental model produced by second processing step  123 . 
     In the third processing step of DFP  130 , that is, of software process  134 , the emergency trajectory, which can guide the vehicle into a safe space within the immediate future, is calculated on the basis of the environmental model produced by second processing step  133 . 
     Trajectory planning  114  in the third processing step of first DFP  110  develops one or more alternative trajectories for reaching the destination that are offered to the subsequent software process, a deciding instance  150 . The proposed trajectories can be evaluated by trajectory planning  114  in terms of safety and effectiveness with respect to reaching the destination or the objective. 
     Deciding instance  150 , which is implemented in a simple software, verifies whether the selected trajectory of trajectory planning  114  is located within the safe space-time domain (SRZD) determined by software process  124  of second DFP  120 . If this is the case, the corresponding target values are transmitted to the actuators. 
     If none of the trajectories of trajectory planning  114  is located within the SRDZ calculated by software process  124 , the deciding instance does not output new target values to the actuator, but waits for the following frame. 
     If also in the following frame none of the trajectories of trajectory planning  114  are located within the SRZD calculated by software process  124 , the deciding instance chooses the emergency trajectory offered by software process  134  and brings the vehicle into a safe state. 
       FIG. 2  shows a possible hardware structure for implementing the DFPs in  FIG. 1 . The boxes in  FIG. 2  represent assemblies. Connecting lines  200  of the assemblies in  FIG. 2  show the available communication channels for transmitting data. 
     DFP  110  includes sensors  111  and assembly  210 . DFP  120  includes sensors  121  and assembly  220 . DFP  130  includes sensors  131  and assembly  230 . Assembly  210  forms a fault containment unit (FCU) that contains the hardware components (node computer, data lines, storage) for implementing software processes  112 ,  113  and  114  of DFP  110 . Assembly  220  forms a fault containment unit (FCU) that contains the hardware components (node computer, data lines, storage) for implementing software processes  122 ,  123  and  124  of DFP  120 . Assembly  230  forms a fault containment unit (FCU) that contains the hardware components (node computer, data lines, storage) for implementing software processes  132 ,  133 , and  134  of DFP  130 . 
     Deciding instance  150  in  FIG. 1  is simultaneously executed on three node computers  251 ,  252  and  253  in a replica deterministic manner in order to be able to mask hardware errors. The results of the three node computers  251 ,  252 , and  253  are transferred to a—preferably intelligent—actuator control  260 , which performs a bit-by-bit two-of-three vote. 
       FIG. 3  shows a different hardware structure for implementation of the DFPs in  FIG. 1 . The boxes in  FIG. 2  represent assemblies. The same reference characters in  FIG. 3  and  FIG. 2  indicate the same elements. 
     Connecting lines  300  of the assemblies show the communication channels available for transmitting data. In contrast to  FIG. 2  in  FIG. 3 , deciding instance  150  is implemented on two self-checking assemblies  351  and  352 . A preferably intelligent actuator control  360  accepts one of the results from  351  or  352 . Because the software processes that run on assemblies  351  and  352  are replica deterministic and the hardware of assemblies  351  and  352  checks itself, the results from assemblies  351  and  352  must be identical. 
     In normal operation, in particular in each frame, at least one of the first trajectories calculated by the first DFP is located within the safe space-time domain (SRZD) that was calculated by the second DFP. In order to be able to recognize a failure or error in the third DFP, which executes the emergency trajectory calculation, it is preferably provided that in normal operation—in particular, in every frame—it is verified whether the emergency trajectory is located within the SRZD. If this is not the case, an alarm signal is transmitted to the driver in order to inform him that the emergency trajectory calculation has failed. 
     In the case of an error, the trajectories calculated by the first DFP are not located within the safe space-time domain (SRZD) that was calculated by the second DFP. In the case of an error, it cannot be decided whether the first DFP or the second DFP is mistaken. In the case of an error, it is then preferably provided that the emergency trajectory is selected by the deciding instance without verifying whether the emergency trajectory is located within the SRZD. 
     During ongoing operations, it is very difficult to decide whether an error in the result of one DFP was caused by the two other DFPs or because of an aging error in the hardware or by a software error. At the moment of the occurrence, however, this decision is irrelevant because the proposed architecture masks the two error types. 
     LITERATURE CITED 
     
         
         [1] US Pat. Application 20160033965 Device and Method for the Autonomous Control of Vehicles, published Feb. 4, 2016 
         [2] PCT Application PCT/AT2015/050212. Computer system and method for safety-critical applications. Patent application by FTS Computertechnik with the Austrian Patent office. Sep. 3, 2015. 
         [3] Austrian patent registration A 5073/2016. Fault-tolerant method and device for controlling an autonomous technical system by means of diversitary trajectory planning. Patent application by FTS Computertechnik with the Austrian Patent office. Aug. 16, 2016 
         [4] Wikipedia, Autonomous Driving, retrieved on Aug. 11, 2016 
         [5] Wikipedia, Automotive Safety Integrity Levels ISO 26262, retrieved on Aug. 11, 2016 
         [6] FAA. Advisory Circular System Safety Assessment for Part 23 Airplanes. URL: http://www.faa.gov/documentLibrary/media/Advisory_Circular/AC %2023.1309-1E.pdf, retrieved on Aug. 11, 2016 
         [7] Avizienis, A. The N-Version Approach to Fault-Tolerant Software, IEEE Trans. on Software Engineering, Vol 11, pp. 1491-1501. December 1985 
         [8] Kopetz, H. Real-Time Systems, Design Principles for Distributed Embedded Applications. Springer Verlag. 2011.