What computational complexity classification does autonomous/self-driving cars belong to?

Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are frequently told that Sudoku and Go are examples of NP-completeness and PSPACE-completeness, and a range of practical progress has been made in dealing with these two categories. So similarly with autonomous vehicles, I think laypeople people (like myself) intuitively accept that learning to drive properly is a "problem", but then, what is the underlying problem that such machine learning algorithms are trying to tackle?

I did some Googling around and found different articles and papers alluding to some parts or formal abstractions of the driving problem and/or maybe robotics being PSPACE-complete. So is that the answer basically? Or is it that the question is too vague to be answerable? Or even that there hasn't been a clear understanding yet, because the area is fairly new? I'm just really curious, but didn't find anything explaining this at a high level. But when I took CS in college, the professors would emphasize to programmers that understanding the nature of the problem can be very important, e.g. understanding if your specific problem is in P or is NP-complete, and so forth.

• The "autonomous/self-driving car" problem has not been formalised. Any formal solution depends on also resolving ethical issues such as the trolley problem. Mar 30, 2021 at 3:33
• That's technically true of any real-life problem though, but it doesn't seem to stop professors from telling undergrads that airline scheduling is reduced to SAT and thus an example of NP-completeness in our daily lives. Mar 30, 2021 at 3:56
• Airline scheduling is formalisable, though, in the sense that the objective functions to optimise for are easy to understand. I'm much more familiar with the "electricity grid control problem". It's easily expressible as an integer linear program with 0-1 variables representing the various controls that you can apply (e.g. turn on a pumped hydro plant). What makes it more complex in real-life is that the system is dynamic: demand fluctuates, supply fluctuates for some generators (e.g. solar), equipment is taken offline for servicing, etc. The solution: Re-solve the ILP every few minutes. Mar 30, 2021 at 5:17
• incomputable, according to current specifications. Mar 30, 2021 at 6:06
• The “trolley problem” is something that doesn’t happen in real life. Rule “don’t drive into groups of people” with precedence over “drive not into single people” it s enough. Mar 30, 2021 at 6:24

Complexity theory is mostly interested in decision problems and in optimization problems, and your problem belongs to neither class. Complexity theory is also interested in other resources, such as communication, but at the cost of neglecting computational complexity.

Apart from not fitting the mold of problems typically considered in complexity theory, your problem is also not well-defined. There is no accurate and formal specification of the required behavior. Without such a specification it is hard to mathematically gauge its complexity.

While it is possible to abstract some aspects of "autonomous driving" into pieces which do fit current theory, in my opinion it doesn't bring us any closer to understanding the actual difficulty of solving this problem.

Complexity theory won't help you in understanding the problem of poverty, or even the problem of writing poetry, or even the decision problem of determining whether a given poem is "good" or "bad". It is not an all-encompassing theory of reality, and as you observe, it doesn't even capture all problems in which computers are involved.

Autonomous driving, in particular, combines hardware, software, legal issues, and philosophical issues. When designing autonomous vehicles, we also design the sensors available to the software controller, the mechanical interventions it is allowed to use, the laws it complies with, and so on. All of these important and pertinent issues are beyond what computational complexity theory offers.

• Just as side note, regulation compliance problems tend to be in NP, though they may not be NP-hard in general. Assuming that the regulations have been formalised, it's usually easy to tell if a solution satisfies all the regulations, even if it's hard to find a solution that satisfies all the regulations.. That's not all of the nebulous "autonomous vehicle problem", but it's part of it. Mar 31, 2021 at 23:28

Let’s say your self driving car is supposed to do the following steps in a loop:

Read all the sensors.
Calculate optimum pressure on accelerator and brakes
Calculate optimum angle for steering wheel
Set the optimum pressure and angle.


Now if the calculation takes too long then it is no good, your car will crash before the calculation finishes. So instead of finding optimum values, you will try to run the calculation for a fixed time, like 10 ms, and use the best result found in that time.

So you are forced to use an algorithm that works in constant time. Whether calculating the optimum values is for example np-complete or np-hard or just a high degree polynomial doesn’t matter, because you only have limited time available.

Here’s a problem that can be reasonably formalised: The Real-time Travelling Salesman problem. It’s the same as ordinary TSP, except: We are not given distances but driving times, we have a starting point, we accept the result bit by bit (give the fist destination, then the second etc. ) and the real difference: The computer has a clock that provided the real time, and the driver can start the tour as soon as one destination is given, and must stop if he or she arrives at a destination and the computer hasn’t provided the next destination.

Clearly taking a long time to find the optimal tour while forcing the driver to wait is no good. The algorithm should produce the first destination when taking longer for the calculation isn’t likely to improve the total driving time enough. We can first use some heuristics which very quickly produces a non-optimal tour, and the algorithm has to balance quality of the tour and execution time in a way that the heuristic will be beaten.