Hey Nikola, I’ve read your previous post about AI, it’s so nice... and I understood everything about the agents... man, those agents are niiiiice man, will you write some more nice sequels? Man, that would be soo niiice!
Of course I will!
I wrote about types of agents and how they work, but what about agent’s programs? Just like you are unique combination of your body and your mind, on the same way an agent consists of architecture (hardware part or “body” like sensors, actuators, wires...) and program (software part, analog to human’s mind). Creating an agent, in the field of AI, pretty much means to write the best agent’s program, while construction of agent’s body is more job for robotics.
Source Maxpixel.net, CC0 Public Domain
Agent’s environment is often too complex for taking all observations and mapping it into actions, so there are developed certain algorithms to help us choose the best possible action in some situation in order to solve our problems.
To find quicker solution, we use something called search algorithms.
I grew up in a not-so-rich neighborhood where you have to watch out for your stuff because someone can easily steal your mobile, or to break into your car and steal stereo and so on. One day I was coming out the store in downtown and suddenly came up to a man who was trying to break the code on the cable on my bicycle. Now, my cable has four digits, so if you are skillful with math and combinatorics you can easily calculate that it has 10^4 possible combinations of digits and to break that – you really need some time. I was standing and watching him a little bit and he didn’t notice me. He was really occupied and looked like he found proper challenge, like the seniors in the park while playing chess. I was like Hey bro, do you need some help? He looked at me and understood that I’m the owner and ran out the fastest he could.
Man, if he told me bro I’m practicing search algorithms, I would even give him the damn bike for free. Like, here you are bro, do it for the science!
If he really knew those algorithms, he could maybe broke the code a lot quicker and I wouldn’t probably have my bike anymore.
So... what are those search algori-things?
Search algorithms can be informed or uninformed (or “blind”) depending on do we have some extra information about our goal and environment.
To explain you uninformed search strategies, I will use an example of traveling problem and beside that, I will teach you Serbian geography a little bit. This example can be abstracted and usefully applied later to other problems, which don’t have to be connected to traveling.
So, first of all, let’s take a look at this simplified road map of central Serbia:
Self-made picture
Let’s say that you are now in Belgrade, chilling at Kalemegdan, shopping at Knez Mihajlova or drinking cocktails with hot chicks on the riverside and suddenly you get unexplainable desire to go tomorrow to Kruševac, for some reason. As you can see, there are many ways to do that. For example you can go from Belgrade directly to Požarevac, Kragujevac or Valjevo and then to consider your further moves, or if you are not in a hurry you can first stop by to enjoy in natural beauties of Šabac (please don't), it’s up to you.
So, the real question is how to find the best and the most economical road to Kruševac and how to find it on the quickest possible way?
To try to find answer to this, I have to introduce to you some terminology.
All possible sequences of your actions form something that is called a search tree, or simply a tree. Imagine that all states are represented with nodes and all possible actions between those states are represented as branches. Take a look at the picture below:
Self-made picture
Beograd is the root of this tree and let’s say that we are now exactly in Beograd. We are developing further this state and generating its children nodes (Beograd is in this situation parent node) Šabac, Valjevo, Kragujevac and Požarevac.
The second step is to check if any of these children nodes is maybe our goal. As we can see, none of them is Kruševac, so we can develop further one of these nodes and search for our goal and repeat that until we get where we want to be. The question is how can we know which node we should choose next to develop and explore?
That is exactly a question that we are trying to solve with the help of search algorithms and depending on our strategy, we have different types of these algorithms.
Those strategies are rated depending on four aspects:
- If the solution exists, can algorithm certainly find it?
- Is that solution optimal?
- How much time it needed to find it?
- How much memory it needs to do that search?
To calculate time and memory needs, we use branching factor b (the maximum number of children nodes for every parent node), d as depth to our goal node and m as maximum length in state space.
Now when we understood some basics, let’s review some uninformed algorithms.
Breadth-first Search (BFS strategy)
It’s a simple strategy where the root is developed first, then all its children nodes are developed, after that their successors and so on.
When a node is generated, at the same time it's also tested so we can see if we reached our goal.
You can see below, how it works:
Author Mre, CC0 1.0
This way of searching will certainly take us to our goal, but is this an optimal solution? If we take a look at time and memory complexity, results are a little bit scary.
If every node has b successors and our goal is on depth d, then there will be b+b^2 +b^3 ...b^d generated nodes. It can be written as O(b^d).
For those who are not familiar with the exponential function, I’ll translate those expresions – s c a r y.
Here are some concrete values – if every node has 10 children (b=10) then on the depth d=2 it will have 110 nodes which can be explored for about 0.11 milliseconds and that’s ok. On the depth d=10 it will have 10^10 nodes and it will need about 3 hours to explore it and about 10 Terabytes of memory! And at the depth of only d=16 it will need about 350 years and about 10 Exabytes! Can you imagine that?
So we can see that this is not the best solution, but can this algorithm be improved?
The answer is yes, and then we have The Uniform Cost Search.
The Uniform Cost Search
This strategy first develops the node which is the nearest to the root.
Self-made picture
Let's see again road map of central Serbia in order to understand how it works. The nearest city to Beograd is Šabac (60 km), so we choose that node for development. First, we test it to see if it’s maybe our goal, but as you can see it’s not, so we can develop that node and now we have Valjevo as a new node. Now we choose between Valjevo, Kragujevac and Požarevac for further development and as you can see Požarevac is the nearest of all of them (61 km < 65 km < 100 km), so that’s our next node for test and development. After Požarevac, following the same logic we will develop Valjevo and then Kragujevac, so we have in the border of our tree Jagodina and Kraljevo as the deepest nodes, so we choose one of them for further development. Because 66+61 is less than 33+30+65 (road to Kraljevo through Čačak and Valjevo) we will develop Jagodina and reach out our goal – Kruševac.
That’s not all folks – this algorithm will also save this sequence and then will check graph again for some others sequences to Kruševac. Then, it will compare all solution and choose the one which is the best!
As we can see, it will always find the solution, so you are maybe thinking now that we found perfect strategy and we don’t need to learn further about these algorithms?
I have to disappoint you and say that this strategy has one problem.
It will always develop node regarding to its cost function (in this case distance to Beograd), but it doesn’t look at the number of steps. This can lead us in a whole another direction and we could never reach our goal! Take a look at the picture below to see what I mean by that:
Self-made picture
If you would like to go from A to C, you can do it in just two steps, going through B. This algorithm won’t do that – instead, it will search through all left sub-tree so we will lose much time. Imagine that we have instead nodes with cost function 1 in this case, nodes that don’t cost at all and that we have infinite number of them – this algorithm would be stuck in that sub-tree forever and would never find the goal!
So, we should consider other strategies too. Hmmm what about Depth-first Search?
Depth-first Search (DFS)
This algorithm always chooses the deepest node in the border of the tree. After reaching the node which doesn’t have successors, algorithm would delete that node from the memory and go step back to the next deepest node. On the picture below you can see the order of nodes development.
Author Mre, CC0 1.0
Why is this strategy good?
Remember previously for BFS when memory needs were scary exponential function O(b^m). Because this algorithm is deleting explored nodes from its memory, required capacities are so much less – practically it’s a linear function O(bm) and, believe me that’s much better.
Is there any problem with this strategy?
Well, you can guess – yes. If one node has infinite number of successors, this algorithm may be stucked in that sub-tree forever. But, there is a cure for that.
We can set the limit of the depth for our tree – first limit will be 0, so algorithm will check nodes on d=0 depth and that’s basically the root of the tree. If that root is not our goal, then limit will be 1, so the algorithm would now check all nodes on the depth d=1. It would repeat this process until the goal node is revealed.
That modification is called Iterative Deepening DFS.
The bad news is that this strategy also has exponential function for time complexity O(b^d).
So what we should do now?
Well, we should check out one more uninformed search algorithm.
Bidirectional Search
The idea is very simple – let’s start our search on two sides! The algorithm would start exploring nodes from the root and also from the goal and at the time when two developed nodes “touch” each other, we can say that we found the right path from the root to the our goal node, as you can see it below.
Author Archnat, CC0 1.0
This method requires that all states are reversible and that’s not the always the case. So using this algorithm can be very hard and people have to be very clever and people are usually not clever.
Wait a minute... which algorithm is the best here? Looks like all of them have certain flaws!
Of course, there is no such thing as a perfect algorithm - it depends on the situation and the problem which one you should use.
Aaa Nikola, you were clickbaiting us – the AI will never take my bike!!! Yeah hahah... right? Or... or you want to say that guy who was trying to steal your bike from the beginning was actually AI? Omg, omg that would be so thrilling, you are so good at writing these series! But it didn’t stole your bike, I shouldn’t be afraid...right?
Well, it could break the code on your bike...
Omg, omg... I’ll put another cable on it! And... I know – It will have four digits, like yours!
Bro, the point is that using one of these algorithms it could break the code in a less than millisecond.
Three cables? Four?
Still milliseconds...
Aaa Nikola, what should I do? I love my bike soo much...
Chill out, I’ve said it can break your code, not to steal it. At the time when it could be possible that one AI can take your bike and run away, believe me – that bike won’t be important to you, because you will be chilling in a flying car.
I hope that you enjoyed,
Again, many thanks to @scienceangel for mentoring me and for her endless support in the battle against my laziness.
Sources:
Artificial Intelligence: A Modern Approach, Peter Norvig and Stuart Russell
Artificial Intelligence: The Very Idea, John Haugeland
Wiki BFS
Wiki DFS