Game Theory and AI Systems: Use Case For Autonomous Cars

2484

By Lance Eliot, the AI Trends Insider

When you get onto the freeway, you are essentially entering into the matrix. For those of you familiar with the movie of the same name, you’ll realize that I am suggesting that you are entering into a kind of simulated world as your car proceeds up the freeway onramp and into the flow of traffic. Whether you know it or not, you are indeed opting into playing a game, though one much more serious than an amusement park bumper cars arena. 

On the freeway, you are playing a game of life-and-death. 

It might seem like you are merely driving to work or trying to get to the ballgame, but the reality is that for every moment you are on the freeway you are at risk of your life. Your car can go awry, say it suddenly loses a tire, and you swerve across the lanes, possibly ramming into other cars or going off a freeway embankment. Or, you might be driving perfectly well, and all of a sudden, a truck ahead of you unexpectedly slams on its breaks and you crash into the truck.

 I hope this doesn’t seem morbid. Nor do I want to appear to be an alarmist. But, you have to admit, these scenarios are all possible and you are in fact at the risk of your life while on the freeway. For a novice driver, such as a teenager starting to drive, you can usually see on their face an expression that sums up the freeway driving circumstance – abject fear. They know that one wrong move can be fatal. They are usually somewhat surprised that anyone would trust a teenager to be in such a situation of great responsibility. Most teenagers are held in contempt by adults for a lack of taking responsibility seriously, and yet we let them get behind the wheel of a multi-ton car and drive amongst the rest of us.

 That’s not to suggest that its only teenage drivers that understand this matter. There are many everyday drivers that know how serious being on the freeway is. They grip the steering wheel with both hands and arch their backs and are paying close attention to every moment while on the freeway. Meanwhile, there are drivers that have gotten so used to driving on the freeway that they act as though they are at a bumper car ride and don’t care whether they cut off other drivers or nearly cause accidents. They zoom along and seem to not have a care in the world. One always wonders whether those drivers are the ones that get into the accidents that you see while on the freeway. Are they more prone to accidents or are they actually more able to skirt around accidents, which maybe they indirectly caused, but managed to avoid themselves getting entangled into.

 For my article about how greed motivates drivers and its impacts on self-driving cars, see: https://aitrends.com/selfdrivingcars/selfishness-self-driving-cars-ai-greed-good/

 Leveraging Game Theory

Anyway, if you are willing to concede that we can think of freeway driving as a game, you then might be also willing to accept the idea that we can potentially use game theory to help understand and model driving behavior.

With game theory, we can consider the freeway driving and the traffic to be something that can be mathematically modeled. This mathematical model can take into account conflict. A car cuts off another car. One car is desperately trying to get ahead of another car. And so on. The mathematical model can also take into account cooperation. As you enter onto the freeway, perhaps other cars let you in by purposely slowing down and making an open space for you. Or, you are in the fast lane and want to get over to the slow lane, so you turn on your blinker and other cars let you make your way from one lane to the next. There is at times cooperative behavior on the freeway, and likewise at times there is behavior involving conflict.

 If this topic generally interests you, there’s key work by John Glen Wardrop that produced what is considered the core principles of equilibrium in traffic assignment. Traffic assignment is the formal name given to modeling traffic situations. He developed mathematical models that showcase how we seek to minimize our cost of travel, and that we potentially can reach various points of equilibrium in doing so. At times, traffic suffers and can be modeled as doing so due to the “price of anarchy,” which is based on presumably selfish oriented behavior.

 See my article about the prisoner’s dilemma and tit-for-tat driving: https://aitrends.com/selfdrivingcars/tit-for-tat-and-ai-self-driving-cars/

 See my article about bounded irrationality and driving behavior: https://aitrends.com/selfdrivingcars/motivational-ai-bounded-irrationality-self-driving-cars/

 For those of you that are into computer science, you likely are familiar with the work of John von Neumann. Of his many contributions to the field of computing and mathematics, he’s also known for his work involving zero-sum games. Indeed, he made use of Brouwer’s fixed-point theorem in topology, and had observed that when you dissolve sugar in a cup of coffee that there’s always a point without motion. We’ll come back to this later on in this exploration of game theory and freeway traffic.

 Let’s first define what a zero-sum game consists of. In a zero-sum game, the choices by the players will not decrease and nor increase the amount of available resources, and thus they are competing against a bounded set of resources. Each player wants their piece of the pie, and in so doing are keeping that piece away from the other player. The pie is not going to expand or contract, it stays the same size. Meanwhile, the players are fighting over the slices and when someone else takes a slice it means there’s one less for the other players to have. A non-zero sum game allows for the pie to be increased and thus one player doesn’t necessarily benefit at the expense of the other players.

 When you are on the freeway, you at times experience a zero-sum game, while at other times it is a non-zero sum game. Suppose you come upon a bunch of stopped traffic up ahead of you. You realize that there’s an accident and it has led to the traffic halting. You are going to get stuck behind the traffic and be late to work. Looking around, you see that there’s a freeway offramp that you could use to get off the freeway and take side streets to get around the snarl.

 It turns out that the freeway traffic is slowly moving forward up toward the blockage, and meanwhile other cars are also realizing that maybe they should try to get to the offramp. You are in the fast lane, which is the furthest lane from the exit ramp. The cars in the other closer lanes are all vying to make the exit. They don’t care about you. They care about themselves making the exit. If they were to let you into their lane, it would increase your chances of getting to the offramp, but simultaneously decrease their chances. This is due to the aspect that the traffic is slowly moving forward and will gradually push past the offramp. There’s a short time window involved and it’s a dog eat dog situation. Zero-sum game.

 But suppose instead the situation involved all the cars that were behind the snarl to share with each other to get to the offramp. Politely and with civility, the cars each allowed other cars around them to make the offramp. Furthermore, there was an emergency lane that the cars opted to use, which otherwise wasn’t supposed to be used, and opened up more available resources to allow the traffic to flow over to the exit. Non-zero sum game (of sorts).

 Game theory attempts to use applied mathematics to model the behavior of humans and animals, and in so doing explain how games are played. This can be done in a purely descriptive manner, meaning that game theory will only describe what is going on about a game. This can also be done in a prescriptive manner, meaning that game theory can advise about what should be done when playing a game.

 Applying Game Theory To Autonomous Cars

What does this have to do with AI self-driving driverless autonomous cars?

At the Cybernetic AI Self-Driving Car Institute, we are using game theory to aid in modeling the traffic that will occur with the advent of AI self-driving cars.

 There are some that believe in a nirvana world whereby all cars on the roadways will be exclusively AI self-driving cars. This provides a grand opportunity to essentially control all cars and do so in a macroscopic manner. Presumably, either by government efforts or by other means, we could setup some master system that would direct the traffic on our roads. Imagine that when you got onto the freeway, all of the cars on the freeway were under the control of a master traffic flow system. Each car was to obey strictly to the master traffic flow system. It alone would determine which lane each car would be in, what the speed of the car would be, when it will change lanes, etc.

 In this scenario, it is assumed that there would never be traffic snarls again. Somehow the master traffic flow system would prevent traffic snarls from occurring. All traffic would magically flow along at maximum speeds and we could increase the speed limit to say 120 miles per hour. Pretty exciting!

 But, this is something that seems less based on mathematics and more so based on a hunch and a dream.

 It’s also somewhat hard to believe that humans are going to be willing to give up the control of their cars to a master traffic flow system. I realize you might immediately point out that if people are willing to secede control of the driving task to an AI-based self-driving car, it’s a simple next step to then secede that their particular AI self-driving car must obey some master traffic control system. We’ll have to wait and see whether people will want their AI self-driving car to be an individualized driver, or whether they’ll be accepting that their individualized driver will become a robot Borg of the larger collective.

 Anyway, even if all of this is interesting to postulate, it still omits the real-world aspect that we are not going to have all and only AI self-driving cars for a very long time. In the United States alone, there are 200+ million conventional cars. Those conventional cars are not going to disappear overnight and be replaced with AI self-driving cars. It’s just not economically feasible. As such, we’re going to have a mixture of AI self-driving cars and conventional cars for quite some time.

 Let’s make that even longer too, due to the aspect that there are different levels of AI self-driving cars. A true self-driving car is considered at Level 5. That’s a self-driving car for which the AI does all of the driving. There is no need for a human driver. There is indeed usually no provision for a human driver, and the driving controls such as the steering wheel and pedals are not even present. For self-driving cars less than Level 5, the driving task is co-shared between the human driver and the AI.

 We might as well then say that the self-driving cars that are less than a Level 5 are pretty much in the same boat as the conventional cars. This is due to the aspect that the human driver can still take over the driving task (though, for Level 4, this is not yet quite settled and some view that a Level 4 would still have car controls for humans, while others insist it not). If we have even one ounce of human driving, we’re back to the situation that it’s going to be problematic to have a master traffic flow system that commands all cars to obey. You might argue that maybe when a less than level 5 self-driving car gets onto the freeway we could jury rig those cars to obey the master traffic flow system, but this seems like a credibility stretch of how this would play out.

 You could even stand this topic on its ear by making the following proposal. Forget about AI self-driving cars per se. Instead, let’s make all cars to have some kind of remote car driving capability. We add this into all cars, conventional or otherwise. When any car gets onto the freeway, it must have this remote control feature included, otherwise it is banned from getting onto the freeway. So, we’ve now reduced all such cars to follow-along automata that the master traffic flow system can control. We would somehow lock-out the human driving controls and only allow the use of the remote control, during the time that the car is on the freeway.

 See my article about the levels of AI self-driving cars: https://aitrends.com/selfdrivingcars/richter-scale-levels-self-driving-cars/

 See my article about swarms and AI self-driving cars: https://aitrends.com/selfdrivingcars/swarm-intelligence-ai-self-driving-cars-stigmergy-boids/

 If we did this, it might give us the nirvana traffic flow advantages that some claim they see in the future. And it would still allow for human driving, but just not on the freeways, or maybe only on the freeways at off-hours and that during the morning traffic and evening traffic times the master flow system takes over all such cars on the freeways. We then wouldn’t need to be in a rush to perfect the AI self-driving cars, since instead we’ve just outfitted cars with this remote control feature. It would be a lot easier than trying to get a car to drive like a human does, which is what the AI self-driving car efforts are trying to achieve.

 Well, I really doubt we’ll have us all accept the notion of having a remote control driving feature placed into our conventional cars. This seems like something that society at large would have severe heartburn over. It has too much of a Big Brother smell to it.

 That’s actually why so far there seems to be such overall support for AI self-driving cars. Most people tend to assume that an AI self-driving car will obey whomever the human occupant is. It’s like having your own electronic chauffeur that is always at your beck and call. If instead it was being pitched that AI self-driving cars would allow for governmental control of all car traffic and that wherever you wanted your AI self-driving car to go would first need to be cleared by the government, I’d bet we’d have a lot of people saying let’s put the brakes on this AI self-driving car thing.

 Now, it could be that we at first have AI self-driving cars that are all about individual needs. You are able to use your AI self-driving car to drive you wherever you want to go, and however you want to get there. But, then there’s a gradual realization that it might be prudent to collective guide those AI self-driving cars. And so via V2I (vehicle to infrastructure) communication, we creep down that path by having the roads tell your AI self-driving car which road to take and how fast to go. This then expands and eventually reaches a point whereby all AI self-driving cars are doing this. The next step becomes master control. Ouch, we got back to that. It’s just that it might happen by happenstance over time, rather than as part of a large-scale master plan.

 You might enjoy reading my piece about conspiracy theories and AI self-driving cars: https://aitrends.com/selfdrivingcars/conspiracy-theories-about-ai-self-driving-cars/

 Predicting A Point Of Equilibrium

Returning to the aspect about using game theory, we can at least try to do traffic simulations and attempt to see what might happen as more and more cars become AI self-driving cars, especially those that are at the vaunted Level 5. These simulations use various payoff matrices to gauge what will happen as an AI self-driving car drives alongside human driven cars. A symmetric payoff is one that depends upon the strategy being deployed and not the AI or person deploying it, while an asymmetric payoff is dependent. We also include varying degrees of cooperative behavior versus non-cooperative behavior.

See my article about human and AI driving styles: https://aitrends.com/selfdrivingcars/driving-styles-and-ai-self-driving-cars/

 See my article about simulations for AI self-driving cars: https://aitrends.com/selfdrivingcars/simulations-self-driving-cars-machine-learning-without-fear/

 John Nash made some crucial contributions to game theory and ultimately was awarded the Nobel Prize in Economic Science for it. His mathematical formulation suggested that when there are two or more players in a game, at some point there will be an equilibrium state such that no player can do any better than they are already doing. The sad thing is that we cannot yet predict per se when that equilibrium point is going to be reached – well, let’s say it is very hard to do.  This is still an open research problem and if you can solve it, good for you, and it might get you your very own Nobel Prize too.

 Why would we want to be able to predict that point of equilibrium? Because we could then potentially guide the players toward it. On the freeway, imagine that you have a hundred cars all moving along. Some are not doing so well and are behind in terms of trying to get to work on time. Others are doing really well and ahead of schedule and will get to work with plenty of time to spare. All else being equal, if we had a master traffic flow system, suppose it could reposition and guide the cars so that they would all be at their best possible state.

 But if we aren’t able to figure out that best possible state, there’s no means to therefore guide everyone toward it. We instead have to use a hit-and-miss approach (not literally hit, just metaphorically). In more formal terms, Nash stated that for a game of a finite number of moves, there exists a means by which the player can randomly choose their moves such that they will ultimately reach a collective point of equilibrium, and that at that point no player can further improve their situation.

 You might say that everyone has reached the happiest point to which they can arrive, given the status of everyone else involved too. When I earlier said it was hard to calculate the point of equilibrium, I was suggesting that it can be found but that it is computationally expensive to do so. Some of you might be familiar with classes of mathematical problems that are considered computable in polynomial time (P), and others that are NP (non-deterministic polynomial time). We aren’t sure yet whether the calculation of Nash’s point of equilibrium is P or NP. Right now, it seems hard to calculate, that we can say for sure.

 By the way, for those of you looking for a Nobel Prize, please let us know if P = NP.

 Conclusion

Game theory will increasingly become important to designing and shaping traffic flow on our roads, particularly once we begin to see the advent of true Level 5 AI self-driving cars. The effort to mathematically model conflict and cooperation in our traffic will involve not only the intelligent rational human decision makers, along with their irrational behavior, but also the potential intelligent rational (and maybe irrational) behavior of the AI of the self-driving cars.

Getting a handle on the traffic aspects will allow AI developers to better shape the AI of the self-driving cars and will aid regulators and the public at large in experiencing what hopefully will be better traffic conditions than with human-only drivers. I don’t think we want to end-up with AI self-driving cars that drive like those crazy human drivers that seem to not realize they are involved in a game of life-and-death. It’s deadly out there and we need to make sure that the AI self-driving cars know how to best play that that serious and somber game.

Copyright 2019 Dr. Lance Eliot 

This content is originally posted on AI Trends.