Driving an automobile involves the tasks of observing surroundings, then making a driving decision based on these observations (steer, brake, coast, etc.). In autonomous driving, all these tasks have to be automated. Autonomous driving technology thus far has relied primarily on machine learning techniques. We argue that appropriate technology should be used for the appropriate task. That is, while machine learning technology is good for observing and automatically understanding the surroundings of an automobile, driving decisions are better automated via commonsense reasoning rather than machine learning. In this paper, we discuss (i) how commonsense reasoning can be automated using answer set programming (ASP) and the goal-directed s(CASP) ASP system, and (ii) develop the AUTO-DISCERN 1 system using this technology for automating decision-making in driving. The goal of our research, described in this paper, is to develop an autonomous driving system that works by simulating the mind of a human driver. Since driving decisions are based on human-style reasoning, they are explainable, their ethics can be ensured, and they will always be correct, provided the system modeling and system inputs are correct.
Autonomous Vehicles (AVs) have been sought for a long
time. With the availability of cheaper hardware (sensors,
cameras, LIDAR) and the advent of advanced software
technology (AI, Machine/Deep learning (ML/DL), Computer
Vision) over the last decades, rapid advancements have been
made in AV technology. However, no car has yet achieved
full automation or Society of Automation Engineers (SAE)
Level 5
1AUTO-DISCERN : AUTOnomous DrivIng uSing Common sEnse ReasoniNg and stop). Our goal in this paper is to develop an AV system that emulates the mind of a human: we will use ML/DL technology for tasks for which humans use pattern matching (vision and scene understanding) and automated commonsense reasoning for tasks for which humans perform mental reasoning (driving decision-making)(see Fig. 1).
To automate commonsense reasoning, we use ASP
2
We express various decision making strategies that drivers use as commonsense rules in ASP, that will be executed on the s(CASP) system. These rules capture various driving decisions regarding steering, turning, braking, accelerating, stopping, etc. We also report on a prototype system called AUTO-DISCERN that we have developed that takes a scene-description and sensor values as input and calculates the driving decision at that instant using the rules. A use case is shown in Fig. 1. We expect that a scene description (perception) will be obtained via image processing techniques that use deep learning methods. Because our decision making is based on automated commonsense reasoning, every decision can be explained, and, in theory, our system will never make a wrong decision, as long as the rules are correct and system input is correct.
Our main contribution in this paper is to show how automated commonsense reasoning can be harnessed to achieve an SAE Level 5 autonomous driving system.
Autonomous vehicles (AVs) hold enormous promise: they can reduce the cost of transportation and increase convenience, as well as reduce road accidents and traffic fatalities by a significant number. AVs can also have a big environmental impact: private ownership of cars can become unnecessary. AVs can greatly aid in the mobility of elderly, disabled, and disadvantaged. The story of AVs has been one of great optimism: it was projected in 2017 that there will be 10 million AVs on the road by 2020 and that fully autonomous vehicles will be the norm in 10 years. Not only we have not reached the 10M vehicle mark, but also no vehicle has earned the fully automated (SAE Level 5) designation.
The history of making vehicles autonomous began with
the introduction of the cruise control in 1948
No car has reached SAE Level 5 yet. The principle reason, we believe, is over-reliance on ML and DL technologies for most aspects of driving. Our goal here is to show that automated commonsense reasoning is essential for achieving SAE Level 5 automation.
3
At present, machine learning plays a major role in the AV technology. A significant amount of technology goes into an AV: radar (to detect cars and other large objects), ultrasonic sensors (to detect objects close by, e.g, the curb), lidar (to detect lane markings, edge of a road, etc.), GPS (for direction to destination and knowing AV’s location), and video cameras (for obtaining the surrounding scene and analyzing it). All these are connected to a central computer where processing takes place. Driving data is collected along with sensor readings, video images, Lidar data, etc. In NVidia’s
PilotNet project
Neural-based technology has a number of well-known
issues with respect to accurate prediction of an outcome. An
ML algorithm is a universal function that learns an
approximate mapping from an input to an output in accordance to
the training data. This technology is fundamentally
statistical. Edge cases, unusual circumstances that are uncommon
in training data, are not covered. Obviously, anything outside
the training data is not learned. This is especially true for
autonomous driving, where there are many situations that may
never be encountered in the driving data collected for
training. A good example of this is flashing red and blue lights
in police cars and fire trucks that Tesla autopilot system has
had trouble with
Because of these issues, many companies have scaled down their ambitions down from SAE level 5. Some companies shut down (e.g., Starsky Robotics). Others (e.g., Waymo) revised their goal down to achieving SAE Level 4 while others have restricted autonomous behavior within limited circumstances (e.g., geo-fenced areas). So the goal of reaching SAE Level 5 seems illusive. In this paper, we argue that SAE Level 5 can be reached via automated commonsense reasoning. In fact, we believe that automated commonsense reasoning is indispensable for the AV technology to reach SAE Level 5 (full automation).
4
To drive a vehicle, a human driver must have the: 1. ability to control the vehicle, i.e., be able to steer, brake, accelerate, and signal for a turn. 2. ability to make visual deductive inferences, i.e., be able to see objects in front of or around the vehicle and make decisions, estimate the speed of objects, and project where they will be in the near future. 3. ability to make a visual abductive inference, i.e.: (i) be able to infer hidden or occluded parts of the objects; e.g., a car will normally have four tires, even though only two are visible; (ii) be able to perform counterfactual (“whatif”) reasoning. 4. ability to distinguish between various scenarios, e.g., be able to tell, for example, that a car in a bill board is not the same as a car on the street.
Essentially, there are two types of tasks involved in driving: (i) visual scene processing and inferencing (tasks #2 through #4 above) and (ii) controlling the vehicle (task #1). Learning to control the vehicle is hard for humans, but visual inferencing comes naturally to us. Controlling the vehicle is easy for a machine, learning visual inferencing is significantly harder for it.
To realize truly autonomous vehicles (SAE Level 5), we need to emulate the way humans drive cars, i.e., use ML for scene processing, while using automated commonsense reasoning for making inferences regarding driving actions. Once an inference is made (steer, accelerate, brake, etc.), it can be easily carried out by the machine. Our ideas are based on the insight that for tasks for which humans use pattern matching (e.g., picture recognition), we should use ML technology, while for tasks for which humans use deduction, we should use automated reasoning. The current practice of using ML for all AV tasks is overkill and is preventing us from reaching SAE Level 5.
We envisage that the cameras will provide an image of
the surroundings every second or so. This image will be
processed using deep learning (object, lane detection, depth
prediction, etc.) so that all the items present in the picture will
be labeled and their bounding-boxes marked. The labels will
be predicates, that will be extracted from the picture, along
with coordinates of each bounding-box. A picture can be
labeled with predicates with the help of datasets such as
Visual Genome
Commonsense Reasoning: As mentioned earlier, an
autonomous driving system should be able to understand and
reason like a human driver. If we examine how we humans
reason, we fill lot of gaps in our understanding of a scene,
conversation, or a piece of text we read, through our
commonsense knowledge and reasoning (e.g., if we see a car
moving fast on a road, we use our commonsense
knowledge to infer that, normally, there must be a driver inside).
Thus, to develop autonomous driving software, we need to
automate commonsense reasoning, i.e., automate the human
thought process. The human thought process is flexible and
non-monotonic in nature, which means “what we believe
now may become false in the future with new knowledge”.
It is well known that commonsense reasoning can be
modeled with (i) defaults, (ii) exceptions to defaults, (iii)
preferences over multiple defaults, and (iv) modeling multiple
worlds
Much of human knowledge consists of default rules, for example, “Normally, birds fly” is a default rule. However, there are exceptions to defaults, for example, penguins are exceptional birds that do not fly. Reasoning with default rules is non-monotonic, as a conclusion drawn using a default rule may have to be withdrawn if more knowledge becomes available and the exceptional case applies. For example, if we are told that Tweety is a bird, we will conclude it flies. Knowing later that Tweety is a penguin will cause us to withdraw our earlier conclusion. Similarly, if we see a car, we know there must be a driver inside, normally, unless we realize it’s a robot-taxi, then we withdraw that conclusion.
Humans often make inferences in the absence of complete information. Such an inference may be revised later as more information becomes available. This human-style reasoning is elegantly captured by default rules and exceptions. Preferences are needed when there are multiple default rules, in which case additional information gleaned from the context is used to resolve which rule to apply. One could argue that expert knowledge amounts to learning defaults, exceptions, and preferences in the field that a person is an expert in.
Also, humans can naturally deal with multiple worlds.
These worlds may be consistent with each other in some
parts, but inconsistent in other parts. For example, animals
don’t talk like humans in the real world, however, in the
cartoon world, animals do talk like humans. So Nemo the fish,
may be able to swim in both the real world and the cartoon
world, but it can talk only in the cartoon world. Similarly, we
are able to distinguish between a car shown on a billboard
on the road and an actual car on the road. Humans have
no trouble distinguishing between multiple worlds (world
shown in the billboard vs real world) and can easily switch
between them as the situation demands. Default reasoning,
augmented with the ability to operate in multiple worlds,
allows one to closely represent the human thought process.
Default rules with exceptions and preferences and multiple
worlds can be elegantly realized in the paradigm of ASP
Goal-directed implementations of ASP such as s(CASP)
6
The commonsense rules that a human driver uses for driving are modeled in ASP, using defaults, exceptions and preferences. The input to these rules is gleaned from a scene that the driver sees, where the scene is translated into a set of predicates that describe the objects and their placement in a scene. We assume that state-of-the-art ML technology is used to obtain these predicate labels. These predicates are represented as a set of facts in ASP that describe the environment and serves as input to the AUTO-DISCERN system. Formally, facts F for a given frame at a timestamp T are combined with (commonsense) driving rules R to make a driving decision Y, given an intent X . Fig. Fig. 4 shows the facts describing a scene and rule snippets that will be activated for this scenario to compute a driving decision at each timestamp. The ASP facts F contain speed, lane, relative distance, predicted trajectory of the AV and other detected objects, lane structure, intersection information, visible traffic signs and lights, etc. An intent X describes the short term goal that needs to be achieved by the AV in order to reach its destination. It is based on the instruction from the navigation system, for example, continue in lane, stay in leftmost Step 1. Scenario representation Extract entities from the images obtained from the environment using ML, computer vision models along with sensor data. Convert extracted information into structured format F that can be processed by prolog like programs self_speed(5, 1), self_lane(1, 1), speed_limit(10, 1), lanes([1,2,3], 1), traffic_signs(stop, 1), obj_meta(1, 2, car, ...), traffic_light(green, 1) Step 2. Common sense reasoning Apply s(CASP) based rules R on the facts F to obtain a primitive understanding of the involved entities and their relations at every frame. Build upon the primitive understanding to obtain high level driving decisions Y select_action(brake, T) :- brake_conditions(T), obstacle_in_lane(... right_lane_clear(T) :- lanes(Lids, T) ...
not neg_lane_clear(...) obstacle_in_lane :- subclass(OType, automobile), ...
Depth #< Dist RESULT. High level action for each frame, along with a detailed trace of why the action was chosen for the frame ..., action(cruise, 140), action(accelerate, 141), action(cruise, 142), action(change_lane_left, 143), ... , action(turn_left, 149), action(brake, 150) ... lane, turn left, etc. Based on the facts and the driving rules, a decision Y is taken which is one of accelerate, brake, cruise, change lane left, change lane right, turn left, turn right, etc. 6.1
The driving rules written in s(CASP) are rules that drivers use while driving (e.g., if behind a slow-moving vehicle, change lanes to go faster [default], unless lanes are blocked [exception]). We refer to this collection of rules as the ‘Driving Rules Catalog’. First, we describe this catalog using examples. We then show (in the experimentation and testing section) how the catalog examples can be converted into ASP rules and executed in s(CASP) to make decisions.
At the topmost level, the catalog is categorized by the set of actions (brake, accelerate, change lane, turn etc.). For each action, ASP rules have been developed that use knowledge of the scene to compute the driving action. Note that the number of commonsense rules that humans use while driving is not really that large. We have cataloged 35 rules at present. Next, we give some examples. À Change lane to left, if there is a non-automobile obstacle ahead in the lane within x meters, and the left lane is clear to perform the lane change Á Turn right, if the intent is to enter the right lane, and if on the major lane of a T-junction intersection, and if AV’s predicted path does not intersect with any object(pedestrian, cyclist, . . . )  Turn right, if the intent is to enter the right lane, and if at a signalized 4-way intersection, and if the traffic light is green, and if AV’s predicted path does not intersect with any object à Brake, if there is an object ahead, within stopping distance from the AV and in the same lane Ä Brake, if at an unsignalized 4-way intersection, and AV vehicle is not the earliest to arrive at the intersection To arrive at a decision, the AV evaluates all possible actions consistent with the current intent and decides on the best one. For each action, there is a set of default rules and exceptions. The default rules evaluate the conditions under which AV should consider taking the action. The exception acts as a filter, checking if the action is safe to perform. The hierarchical logic and default reasoning have been encoded in s(CASP). Here is code for change lane-left: select_action(change_lane_left, T) :change_lane_left_conditions(T), not ab(d_select_action(change_lane_left, T)), not neg_select_action(change_lane_left, T).
The change lane left conditions define the default rules to perform the action. The AV would consider changing to left lane if the current intent is to stay in leftmost lane (precursor to performing a left turn) or it needs to overtake a vehicle or avoid an obstacle ahead. change_lane_left_conditions(T) :- self_lane(SLid, T), nonmv_ahead_in_lane(T, SLid, 20, OType), neg_can_drive_over(OType), can_swerve_around(OType). change_lane_left_conditions(T) :
intent(stay_in_leftmost_lane, T).
However, it is not always possible to perform an action even if it is a short term goal. Predicate neg select action encodes the exception rules when performing the action is not safe or possible. The AV cannot change to the left lane if its not clear of obstacles. Similarly, it cannot accelerate if it is approaching a red traffic light or it is above the speed limit. neg_select_action(accelerate, T) :above_speed_limit(T); self_lane(SLid, T), neg_lane_clear(T, SLid, 10); traffic_light(red, T). neg_select_action(change_lane_left, T) :
not left_lane_clear(T). 6.2
We demonstrate the usability and simplicity of our approach to autonomous driving. Further, we show selected scenarios where common sense reasoning is essential to safe driving and how our approach achieves this. For each selected scenario, we show the relevant rules that lead to the action and describe the decision making process.
System Testing We have developed a large set of test scenarios to test our ASP-coded commonsense rules for driving. The test scenarios cover normal and adverse conditions encountered during driving. These scenarios cover general cases as well as corner case situations that even humans would find challenging to drive in. In Fig. 5, we show some of the scenarios that are covered by our model.
Common Driving Scenarios Once our rules were tested,
we evaluated the AUTO-DISCERN system on real-world
situations obtained from the KITTI
Selected frames from the experiment along with the rules that allowed AUTO-DISCERN to perform the required action are shown below. Fig. 6a shows a situation where the AV has to merge into the left lane with high incoming traffic. As the AV approached the merge, it slowed down to a stop, performing the lane change when the left lane was clear. Fig. 6b is an example of waiting before performing a right turn. The rules build upon predicted object trajectories obtained from ML model to realize performing a right turn is unsafe. These rules were derived from example À and Á of the driving rules catalog respectively.
Finally, we tested the AUTO-DISCERN system on cases where a ML based system failed. AUTO-DISCERN system was able to arrive at a correct decision in all such scenarios.
Our experiments indicate that commonsense knowledge about driving can be modeled with relative ease. This should not come as a surprise, as we use relatively few rules to chart a course through the various types of objects we encounter as we drive. If the rules are correct, and the input to our system is correct, then we are in effect modeling an unerring 2Experiment run on Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz 8-Core Processor, 12GB RAM. change_lane_left_conditions(T) :
intent(merge_into_left_lane, T). neg_select_action(change_lane_left, T) :
not left_lane_clear(T).
brake_conditions(T) :- intent(merge_into_left_lane, T),
not left_lane_clear(T).
(a) AV performs a change lane left to merge at high city traffic.
turn_right_conditions(T) :- intent(enter_right_lane, T).
neg_select_action(turn_right, T)
:self_pred_path(SPath, T),
obj_pred_path(Oid, OPath, T),
path_intersects(SPath, OPath).
brake_conditions(T) :- intent(enter_right_lane, T),
intersection(_, _, at, T).
(b) AV waits for pedestrians before performing a right turn.
human driver. There are many advantages to developing an
AV system based on commonsense reasoning:
Explainability: Every driving decision made is explainable,
as it can be justified via rules. The justification is obtained
by using the s(CASP) system’s proof tree generation facility
The global constraints hold.
Error Mitigation: A major problem with ML-based systems is that unusual and corner cases may be missed. For example, as shown earlier, the speed limit of 35 may be read as 85. If a human misinterprets the speed limit sign of 35 as 85, their commonsense knowledge that they are in a city tells them that an 85 speed limit seems too high. This type of commonsense reasoning can be performed in our AUTO-DISCERN system. Defaults rules with exceptions can be written in ASP to determine what a reasonable speed limit ought to be in each type of surrounding, which can then be used to perform sanity checks as shown in the (selfexplanatory) example below: max_speed(Location, S) :- reasonable_speed(Location, S1), posted_speed_limit(Location, S2), minimum(S1, S2, S), not abnormal(Location, S).
Commonsense knowledge can also be used to ensure that the frame corresponding to a scene is consistent with information provided by various sensors in the AV. If there is any inconsistency, the sensor information can be given priority, as visual information is more likely to be erroneous. Consider the example shown in Fig. 2. The following rules allow AUTO-DISCERN to perform a change lane right based on sensor data overriding the visual information. change_lane_right_conditions(T) :sensor(left, Dist, T), collision_distance(CD, T), Dist =< CD.
Thus, ensuring that the AV system is safe is considerably easier as we are emulating a human driver’s mind that gets inputs from various sources and tries to infer a consistent world view with respect to which a driving action is taken. A system like AUTO-DISCERN can also be used to aid ML based AV systems to cross-check the decision made by them. Additionally, it’s provably ethical and explainable.
can also be handled through the use of s(CASP)-based commonsense reasoning technology. For instance, flashing traffic lights require that a sequence of scenes is processed to recognize the flashing of lights. Commonsense rules to perform this processing can be easily written in ASP/s(CASP). Similarly, predicting where various objects in the scene will be a few seconds in the future can also be done by analyzing a sequence of temporally ordered scene through commonsense reasoning. Incorporating more nuanced commonsense reasoning is part of our future work.
An ML based AV system has to be retrained if it has to be used in another country with slightly different conventions. In contrast, a commonsense reasoning-based AV system such as AUTO-DISCERN can be easily used in such situations as the differences in conventions can be described as commonsense rules (the DL-based scene understanding system, of course, must be retrained if traffic signs are different). Note that humans don’t have to be heavily retrained when they drive in another country.
Use of formal logic and ASP to model driving has been
proposed in the past. Bhatt et al. have employed ASP and
the CLINGO system for autonomous driving experiments
Karimi and Duggirala
To conclude, in this paper we described our AUTO-DISCERN system that employs commonsense reasoning (CSR) for autonomous driving. Commonsense knowledge about driving is represented as a predicate answer set program and executed on the s(CASP) goaldirected ASP system. While ML based AV have made significant advances, none of them have reached the level of full automation. We strongly believe that taking an approach based on automating CSR is indispensable for developing AV technology. The goal is to emulate human drivers, who use CSR for making decision while driving. Rules for driving were developed into the AUTO-DISCERN system with the help of existing data-sets such as KITTI, driving manuals available, and our own commonsense knowledge of driving. Our system is explainable and provably ethical. Input to the system consists of data from all the sensors as well as description of the scene as predicates (obtained using ML technology). Given that CSR is used, ML errors in processing the scene can be compensated for.
The main contribution of our work is to demonstrate how a complete decision making system for autonomous driving can be developed by modeling commonsense reasoning in ASP and the s(CASP) system. The s(CASP) system is what makes AUTO-DISCERN possible, and it is one reason why an AV system based entirely on commonsense reasoning has not been developed thus far. Future work includes refining and developing the AUTO-DISCERN infrastructure to make it work with the CARLA setup (https://carla.org) as well as to develop an actual AV deployment with our industrial partner.
Authors are supported by NSF awards IIS 1718945, IIS 1910131, IIP 1916206 and by grants from Amazon and DoD.
Gelfond, M.; and Kahl, Y. 2014. Knowledge representation, reasoning, and the design of intelligent agents: The answerset programming approach. Cambridge University Press.