Brute Force Algorithms In AI Are Easy But Not Smarticle, Use Them Wisely In Driverless Cars

Dr. Lance Eliot, AI Insider

Image for post
Image for post

When my children were young, they used to enjoy playing hide-and-seek with each other. At times, they would look in every nook and corner, including places that would not accommodate hiding. This was an approach sometimes considered an “exhaustive search” in computer science, meaning that you search high and low, doing so without any particular rhyme or reason to the search other than focusing on simply conducting the search.

Eventually, as the kids got older, they realized that it would be prudent to search in a more refined manner, such as not looking in places that weren’t large enough to hide. Plus, they at first had always started searching indoors and then gone outdoors, but they each realized this and had opted often to hide outdoors, doing so to lengthy their hiding time, but they both also caught onto their each behaviors and so tended to switch toward looking outdoors first and then looking indoors.

As an AI developer, I was fascinated in the evolution of their playing this hide-and-seek game.

When they were young and first discovering how to play the game, they pretty much did an exhaustive kind of search, doing so in a brute force manner.

Brute Force Algorithms Have Their Pro And Con

Brute force is a phrase that would aptly describe their initial approach to playing the hide-and-seek game.

The notion of brute force is that you undertake an exhaustive effort towards trying to do something, doing so without particularly having any added insight or ways to cut corners, instead you just go at it until you (hopefully) succeed in your quest. In the case of the kids, they would begin looking and just keep looking until they found the hider. All rooms were included, and all of the outdoor yard area was included.

The nice thing about a brute force method or algorithm is that it is usually pretty easy to implement and describe. I’m going to start looking for the hider and continue doing so until they are found and will look high and low to find them. This search process of looking high and low included areas that would not even accommodate the hider.

One of the disadvantages of a brute force approach is that it can be inefficient. The children would run throughout all rooms of the house and yet there were some rooms that had no available hiding spots. They at first always looked inside the house, even though the odds were that the hider was likely hiding outside. They looked in spots that would not even accommodate the hider. All of this was a quite inefficient search process (but, they had a lot of fun!).

Imagine if you had a computer that was undertaking some kind of search among a lot of data. You could use a brute force method to do so.

From a programming perspective, the odds are that the programmer that opts to use a brute force approach doesn’t have to do much work in terms of preparing the code for the effort. It tends to be easy to write such code. When I say easy, I mean that in comparison to having come up with a more elaborated method takes more effort to do. If you want to have a computer routine that will be savvy in doing a search, it takes some thinking about what the method should be. You need to design it and then code it. You need to test it to figure out whether it works or not. And so on.

One potential issue with brute force is that it can be difficult to know whether the brutish method will be able to find the desired solution in a “reasonable” amount of time.

Suppose the kids had a timeclock that kept track of their hide-and-seek game. If they had agreed to limit the search time to say five minutes, and if the approach of going throughout the entire house was taking say six minutes, it would imply that they would have only had time to do the indoors search and not the outdoors search. Furthermore, the six minutes to do the indoors search would have to end at the five minute deadline, meaning that even the indoor search would not necessarily complete.

For a computer system, using a brute force algorithm, it might take minutes, hours, days, weeks, months, or might not ever end (assuming you could let it keep running), while trying to find the solution being sought. This could chew-up a lot of processing cycles too. You could potentially devote a computer entirely to this search task and it might consume all available computing cycles in doing so.

Use Of Computing Resources Is A Trade-Off Too

Often times, when considering computer systems, you need to look at both the processing cycles consumed and the amount of computer memory consumed too. A brute force method can make use of computer processing cycles during its efforts. This might also require the use of computer memory while doing so.

Memory can be consumed at a tremendous rate during a brute force method. One danger then of a brute force approach is that it can consume so much memory that it might use up all available memory for the computer system being used. This could cause the brute force method to falter, and in some cases come to a halt prematurely.

Oddly enough, a brute force method can actually be a low memory consumer. In other words, rather than using up a lot of memory, the brute force algorithm might use hardly any memory at all. The simplistic nature of the algorithm might be that it uses a minimal amount of memory to undertake its steps. In contrast, sometimes a savvy algorithm might use up a lot of memory, doing so as a means of reducing the time required to find a solution.

If the time performance of a brute force computer algorithm is maybe taking too long, there are ways to potentially speed up the brute force effort without having to change the algorithm itself. For example, you might be able to use a faster computer processor. You might be able to add more computer memory. You might see if you can parallelize it, doing so by perhaps deploying the algorithm onto multiple processors.

The parallelization is not so easy a means to speed-up things. The nature of the brute force algorithm might not lend itself to working in parallel. As such, you cannot blindly just toss more processors at the situation and hope that it will help. The added processors might not speed up things and might actually be unused since there’s no clear-cut way to parallelize without changing the algorithm.

There’s a fine line between pure brute force and trying to make the brute force a bit savvier. Remember when the children realized that they might be better off to start their search outside, since they knew that it was an often-used hiding spot. Maybe we can improve a pure brute force method by refining it.

Some refer to this as employing brute reason.

Brute Reasoning At The Edge Of Brute Force

It can be hard to say where the dividing line is between a pure brute force versus adding brute reasoning, and also then extending beyond brute reasoning to say that we are using a non-brute force method entirely.

With the kids, they might have been using “brute reasoning” when they opted to search outdoors at first rather than indoors and they no longer looked in spots that could not accommodate a hider. You might say they progressed beyond brute reasoning and into a non-brute force method when they began to use their awareness of where the hider was more likely to hide, and not look in every room and reduce the overall search space size accordingly.

Brute Force As Deployed In AI Autonomous Cars

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

At the Cybernetic AI Self-Driving Cars Institute, we are developing AI software for self-driving cars. One crucial aspect of the AI involves its ability to perform various searches.

There are other various kinds of searches that take place.

For example, suppose that the camera has captured a picture of the scene in front of the self-driving car. The AI needs to examine the picture and try to see if there are other cars up ahead. Are there pedestrians nearby the self-driving car? Are there bicyclists nearby the self-driving car? All of these have to be found in the picture. Likewise, for the radar, sonic results, LIDAR data, a search needs to be made to figure out what objects exist in that data.

Brute force would be one way to conduct the search of the sensory collected data. The computer on-board the self-driving car could exhaustively examine the data. This might seem like a sensible approach. Just have the system look at everything and anything.

But, suppose the amount of time it takes to do this brute force examination of the sensory data took three seconds to undertake. Suppose the self-driving car was moving along at 55 miles per hour, which is about 80 feet per second. In the three seconds that the brute force algorithm was looking at the data, the self-driving car has moved 240 feet. In that distance, it could be that the self-driving car rams into another car ahead, doing so because the AI was not yet aware that a car was directly ahead and that the AI ought to hit the brakes on the self-driving car.

As such, using a simplistic brute force algorithm might be “easy” to implement, but it could also have life-or-death consequences. Driving a car is a real-time task that requires being extremely mindful of the clock.

Throwing Hardware At Brute Force Won’t Necessarily Solve Things

You might be tempted to suggest that perhaps we can speed-up the data exploration by adding more processors to the on-board computer systems. It might help, it might not.

Not only would adding more hardware increase the costs associated with the self-driving car, it would add weight and take up more space in the self-driving car. By adding weight to a self-driving car, you are potentially impacting its overall size and maneuverability. The use of space in the self-driving car would likely reduce available space for other purposes, such as space for the human occupants that would likely be wanting to ride in the self-driving car.

There are other important and time critical aspects of the driving task for the AI.

The AI system is keeping track of a virtual world model. This is a kind of 3D virtual representation of the surroundings of the self-driving car. The AI needs to use this virtual model to try and anticipate what it should do next, and what else might occur next in the surrounding environment.

While the AI is driving the self-driving car, it needs to carefully explore the virtual world model. The AI might tentatively decide that a right turn would be prudent at the next corner.

But, suppose further examination of the virtual world model reveals that the right corner is blocked with red cones and there is construction work taking place there. This might preclude taking a right turn at the corner. The AI would then need to reassess and figure out what might be the next best move, perhaps waiting to make a right turn later on or perhaps making a series of left turns to get to where it needs to go.

Would it make sense to explore the virtual model on a pure brute force approach? The issue is similar to the points made earlier, namely whether a brute force algorithm could work quickly enough and thoroughly enough to get the job done in time. Likely not.

As a result, it is crucial that these kinds of AI systems be using at least brute reasoning, and more so that they would be using very savvy heuristics. A wide variety of AI techniques are utilized, such as using machine learning, support vector machines, etc.

Conclusion

At some of my presentations about AI autonomous cars I at times have programmers that seem to wonder why the AI software for a self-driving driverless car is so complex.

For some of these programmers, they think that the programming should be straightforward. I point out that if we could just use simplistic brute force methods, it would reduce the complexity of the software and make getting the software established much easier and faster.

Unfortunately, due to the nature of the driving task, a brute force approach is unlikely to be sufficient. It would tend to not work adequately under the severe time constraints involved in driving a car. For the programmer’s toolkit, having brute force algorithms at the ready is handy, but they should only be used when appropriate. The AI systems for self-driving cars require much more than brute force.

For free podcast of this story, visit: http://ai-selfdriving-cars.libsyn.com/website

The podcasts are also available on Spotify, iTunes, iHeartRadio, etc.

More info about AI self-driving cars, see: www.ai-selfdriving-cars.guru

To follow Lance Eliot on Twitter: @LanceEliot

For his Forbes.com blog, see: https://forbes.com/sites/lanceeliot/

For his Medium blog, see: https://medium.com/@lance.eliot

For Dr. Eliot’s books, see: https://www.amazon.com/Dr.-Lance-Eliot/e/B07Q2FQ7G4

Copyright © 2019 Dr. Lance B. Eliot

Written by

Dr. Lance B. Eliot is a renowned global expert on AI, Stanford Fellow at Stanford University, was a professor at USC, headed an AI Lab, top exec at a major VC.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store