Data Science

Brute Force Algorithms and AI: Use Case of Autonomous Cars


By Lance Eliot, the AI Trends Insider

When my children were young, they used to enjoy playing hide-and-seek with each other. One of them would hide somewhere either in the house or in our yard and be allowed a few minutes to find a good hiding spot. Once the other one had finished waiting the prescribed time period, the search would begin. At times, the search was quite hilarious to watch, particularly when they were quite young, since the places looked into were not at all feasible for any of them to hide in. I recall at one point that the teapot was examined and, on another occasion, that a potted plant in the house was dug into as though perhaps the hider might have become a gopher and dug into the dirt.

The search also at first covered every square inch of the house and the yard. They each would usually start indoors and go from room to room, looking throughout the bedroom of the other, then the bathroom, then their own bedroom, then the living room, then the kitchen, etc. If the hider wasn’t found in the house, the search would continue outdoors. This outdoor search usually began in the backyard, then went to the side yard, and eventually to the front yard.

There were some rules about the game that made things “fairer” in that the hider could not change their hiding spot during the game, and nor could they hide in a location that was considered out-of-bounds (for example, we banned them from climbing on the roof, that kind of thing). The person searching had to dutifully conduct the search. I mention this aspect because one tactic they discovered was the searcher could just sit and watch TV and figured that the hider would get tired of waiting to be found and voluntarily give themselves up. That wasn’t the spirit of the game.

All in all, they typically would conduct a rather exhaustive search.

It used up a chunk of their play time and perhaps honed their cognitive ability to undertake a reasoned approach to solving a problem. I enjoyed seeing that they were able to during a search proceed without backtracking and usually avoided revisiting the same location twice. If they felt that they had done an exhaustive search in a particular location, let’s say in the kitchen, they reasoned that there was no need to come back to the kitchen to do so again (recall that the hider could not be sneaky and move from location to location, which of course if so would then potentially necessitate revisiting prior search locations).

They also discovered that if they were sloppy about doing the search, they might end-up having apparently looked everywhere and yet still not found the hider. This was met with great chagrin as it implied that the searcher had somehow overlooked the hiding spot of the hider. At times, if one of them had looked inside and outside and could not find the hider, they would make an accusation that the hider had violated the rules and gone out-of-bounds. An out-of-bounds player was automatically considered the “loser” of the game and forfeited the game to the searcher. As parents, we also added additional penalties to going out-of-bounds since we didn’t want the children to unknowingly in their innocent desperation hide in a spot that would be dangerous for them (e.g., hiding in the fireplace was not allowed, likewise no hiding behind the furnace).

As they grew a bit older, and after having played the game many times, they improved upon their search techniques. One of the overarching aspects of the search involved whether to begin by searching inside the house versus outside of the house. They had each fallen into a pattern of always starting inside the house. This used up a lot of time as they went from room to room. The hider often realized that they could last longer in terms of hiding by finding a spot outside, and it was considered better to be hidden longer rather than getting caught right away. Also, living in Southern California, the outside weather was usually nice and sunny, so hiding outdoors was generally more enjoyable anyway.

As a result of these aspects, the searcher would often decide to forego starting the search indoors and instead begin it outdoors. This seemed like a prudent improvement to the search effort. Why not start the search where you believe the chances of finding the hider are heightened?

This handy rule-of-thumb had its uses and yet was not considered an iron clad approach. If the weather was somewhat foul, the odds were that the hider would opt to hide inside. In that case, rather than shifting to search outdoors first, it made more sense to instead search indoors first.

Likewise, they began to realize that the places of hiding had to be large enough to accommodate the hider. Sure, the hider could scrunch themselves up if needed, or maybe even try to stretch themselves out, but in any case, it was realized that they could not somehow fit into a teapot. There were plentiful areas both indoors and outdoors that could accommodate a hider, and meanwhile there were many more areas that obviously could not accommodate a hider.

Another rule of the game was that the hider could not disturb anything in order to hide. For example, you could not pull things out of a closet to make space for you to hide in closet. If the closet had space within which you could fit, it was permissible to hide in there, but you could not be moving things around to create a space where none already existed per se.

Eventually, the game lost its attraction. There were only so many places to hide and it became apparent as to where those spots were. The job of the searcher became focused solely on going to those spots. There was no need to run all around the house and no need to run all around the yard. Just quickly go to each of the known hiding spots, and you could rather expeditiously find the hider. Furthermore, you could usually guess which of those spots the hider might actually use, since there were some spots more accommodating and desirable than others (hiding behind the stinky cat litter box was not on the top of the list of places to hide!).

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. Look everywhere. Leave no stone unturned. Just start looking and keep looking until you find the hider. It involved a lot of exciting and playful running around the house and the yard.

Brute force.

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.

As mentioned, at first, they had no particular strategy to how they were doing the search. It was almost a mindless kind of approach. Explore all possibilities was the mantra. When you find the hider, you are done.

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. Similar to the children and their hide-and-seek game, the computer could just start looking and continue doing so until it finds whatever is being searched for. No effort might be undertaken to help the computer identify where to first start looking and nor whether it can skip some of the data that might be readily inapplicable to the matter. Instead, the brute force might look at each data element, one by one, one after another, doing so exhaustively.

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.

Indeed, we tend to think of brute force as a means to search a search space. If the search space is very large, the brute force method, though perhaps easy to implement, might then be quite lengthy in trying to find the desired solution. The kids added various rules-of-thumb, which we might call heuristics, and for which it then “reduced” the amount of search space that had to be examined (no longer looking at all rooms and all possible hiding spots).

I’ve often noticed that at times software developers are pushed to get on with their coding and not given time to figure out whether the system they are crafting will run well or not. In that sense, sometimes an organization is inadvertently shooting its own foot by not encouraging the software developers to take a moment to consider what kind of algorithms there might be for the problem they are trying to solve. It could be that after some exploration, there might be algorithms that go beyond brute force and use brute reasoning that could be employed. Furthermore, there might be elegant and complex algorithms that go even further and far eclipse any kind of brutish method.

Some developers though at times eschew algorithms that they aren’t familiar with, and as a result resort to using ones that they are comfortable with, in spite of the aspect that the algorithms might be brutish and not up to the task at hand in terms of needing to meet time and space constraints. There is a trade-off of trying to get such developers to consider other algorithms, along with their hesitancy to do so, along with the added time required to have them learn about and be able to use the algorithm, etc.

Typically, developers that specialize in AI systems are familiar with a wide range of non-brute force approaches, considered a core foundation for what AI techniques and methods utilize.

That being said, sometimes AI developers are perhaps over-eager to leverage very tricky algorithms that are intended to immensely improve over brute force, but perhaps the trickiness trips them up. They might not fully ensure that the non-brute force algorithm fully applies to the matter, or they put it into place but other developers are clueless about how it works, making for difficulties if they are supposed to maintain or enhance it over time.

I recall too when managing AI developers that one of member of my team came to see me and explained that he knew of only three ways to tackle a problem we were aiming to deal with. I explained to him that when his own base of knowledge about finding faster or more effective methods is exhausted that he should consult with his fellow AI developers to see what they might advise, along with doing some background research to see what else might exist. He was focused solely on his own base of experience, and had not tried to see what others might have to say about the approaches possible.

This brings up a classic line about the idea that if you only have a hammer then everything around you looks like a nail. Essentially, if you only know some brute force methods, you are likely to use them even though they might not be the appropriate choice in the circumstance. I’d say the other side of the coin works in this case too. If you know only elegant and complex algorithms, you might tend to use those when a brute force method might actually be the more fitting choice.

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.

You might be thinking of searches when driving a car such as trying to figure out how to get to where you are going. Maybe there are ten different ways that you can drive to work. Which of the ten paths would be the best? You might use a computer algorithm to consider each of the ten paths. Some might of the paths might be shorter than others, but those shorter paths might involve lots of intersections with traffic signals, all of which might increase the driving time even if the distance is not as far.

There are other various kinds of searches that take place.

Allow me to elaborate.

I’d like to first clarify and introduce the notion that there are varying levels of AI self-driving cars. The topmost level is considered Level 5. A Level 5 self-driving car is one that is being driven by the AI and there is no human driver involved. For the design of Level 5 self-driving cars, the auto makers are even removing the gas pedal, brake pedal, and steering wheel, since those are contraptions used by human drivers. The Level 5 self-driving car is not being driven by a human and nor is there an expectation that a human driver will be present in the self-driving car. It’s all on the shoulders of the AI to drive the car.

For self-driving cars less than a Level 5, there must be a human driver present in the car. The human driver is currently considered the responsible party for the acts of the car. The AI and the human driver are co-sharing the driving task. In spite of this co-sharing, the human is supposed to remain fully immersed into the driving task and be ready at all times to perform the driving task. I’ve repeatedly warned about the dangers of this co-sharing arrangement and predicted it will produce many untoward results.

For the levels of self-driving cars, see my article: https://aitrends.com/selfdrivingcars/richter-scale-levels-self-driving-cars/

For my overall framework about AI self-driving cars, see my article: https://aitrends.com/selfdrivingcars/framework-ai-self-driving-driverless-cars-big-picture/

For why AI Level 5 self-driving cars are like a moonshot, see my article: https://aitrends.com/selfdrivingcars/self-driving-car-mother-ai-projects-moonshot/

For the dangers of co-sharing the driving task, see my article: https://aitrends.com/selfdrivingcars/human-back-up-drivers-for-ai-self-driving-cars/

Let’s focus herein on the true Level 5 self-driving car. Much of the comments apply to the less than Level 5 self-driving cars too, but the fully autonomous AI self-driving car will receive the most attention in this discussion.

Here’s the usual steps involved in the AI driving task:

  •         Sensor data collection and interpretation
  •         Sensor fusion
  •         Virtual world model updating
  •         AI action planning
  •         Car controls command issuance

During the driving task, the AI system is collecting data from the myriad of sensors, including radar, sonic, cameras, LIDAR, and others. The data needs to be explored to try and identify what the data indicates.

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.

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.

For the cognition timing aspects of the driving task, see my article: https://aitrends.com/selfdrivingcars/cognitive-timing-for-ai-self-driving-cars/

For rear-end collisions and AI self-driving cars, see my analysis: https://aitrends.com/ai-insider/rear-end-collisions-and-ai-self-driving-cars-plus-apple-lexus-incident/

For defensive driving tactics and AI self-driving cars, see my article: https://aitrends.com/selfdrivingcars/art-defensive-driving-key-self-driving-car-success/

For how AI developers are designing the AI, see my article: https://aitrends.com/selfdrivingcars/egocentric-design-and-ai-self-driving-cars/

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. As mentioned before, parallelization is not an automatic due to just adding more processors. Plus, you need to consider the added cost to the self-driving car, which would be boosted by adding more processors, or faster processors, or adding more memory.

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. Is that car to your right going to try and get ahead of the self-driving car and barge into the lane of the self-driving car? Is that bicyclist that’s riding in the bike lane going to potentially swerve out of the bike lane and into the path of the self-driving car?

You might think of the analysis of the virtual world model as a game of chess. In chess, you need to consider what your next move consists of. Furthermore, you need to consider what counter-moves might take place after your next move. You can do this for a series of levels of thinking ahead, called ply. How many ply ahead should you look when playing chess? Usually, the more ply, the better your current move will be chosen.

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.

Brute force.

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.

For more about support vector machines, see my article: https://aitrends.com/selfdrivingcars/support-vector-machines-svm-ai-self-driving-cars/

For aspects of ensemble machine learning, see my article: https://aitrends.com/selfdrivingcars/ensemble-machine-learning-for-ai-self-driving-cars/

For my article about machine learning and AI self-driving cars, see: https://aitrends.com/ai-insider/machine-learning-benchmarks-and-ai-self-driving-cars/

For the freezing robot problems, see my article: https://aitrends.com/selfdrivingcars/freezing-robot-problem-and-ai-self-driving-cars/

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.

Copyright 2019 Dr. Lance Eliot

This content is originally posted on AI Trends.

[Ed. Note: See Lance Eliot’s piece published on June 18: Cognitive Mental Disorders and AI Ramifications: The Case of AI Autonomous Cars.]


Source link

Guest Blogger

We feature multiple guest blogger from around the digital world. If you are featured here, don't be surprised, you are a our knowledge star. :)

Related Articles

Back to top button
Close
Close