Intro to AI with Python - Unit 0, Part 2: Intelligent Search
HarvardX offers a program called Introduction to Computer Science which consists of two courses. The first course is Computer Science for Artificial Intelligence, and the second is Introduction to Artificial Intelligence with Python. I looked at the outline of the first course, and started going through the lectures. But I stopped after one day because I realized that this course was a rehash of things I learned as an undergraduate (thank you, University of Scranton CS department!).
Please note: My full notes on this course will always be available on my website.
The Intro to AI with Python course is made up of 7 units, each containing a lecture and a set of? exercises. I will not be posting my solutions to the exercises.
In my previous post, I covered basic search.
Depth-first and breadth-first search are both uninformed, they don't use any problem-specific or environment-specific knowledge, so they can't use any intelligence to search for a solution.
Greedy Best-First Search (GBFS) is an informed search algorithm that expands the node that is closest to the goal, as estimated by a heuristic function h(n). The standard heuristic function is Manhattan distance, named after the grid-like nature of the Manhattan street map. The Manhattan distance between two grid locations is the number of vertical (north-south) cells between the two locations + the number of horizontal (east-west) cells between the two locations.
The Manhattan distance between the driveway and the restaurant parking lot is 28 units: 21 units north + 7 units west.
Implementing GBFS search using Manhattan distance as our heuristic function, we would progress like this, with the Manhattan distance noted on the frontier nodes:
After expanding a couple of nodes, we have two options: the first unit west on Residential Road has a Manhattan distance of 26 units, while the first unit east on Residential Road has a Manhattan distance of 28 units. The GBFS algorithm says to expand the node with the lowest Manhattan distance, so we would proceed west on Residential.
When we get to the first intersection, we have the choice of going north on Jefferson, or continuing west on Residential. Since both options have a Manhattan distance of 23 units from our goal state, the algorithm would expand both nodes.
We continue expanding nodes along both paths until we eventually get to the state pictured here. The two paths (west on Residential, north on Jefferson) have the same Manhattan distance.
If we expand one more node along the two paths, we see an interesting phenomenon. The Manhattan distance for the westward path increases as we "overshoot" the target. The path north on Jefferson doesn't encounter this phenomenon, so we continue expanding nodes northward on Jefferson.
The branches to Third Street and Second Street are added to the frontier, but not expanded further because the Manhattan distance is greater for both paths.
As we continue expanding the path down First Street, the Manhattan distance eventually starts to increase because First Street turns away from the goal state. By the time we get to the state in this diagram, the paths down First Street and Second Street have the same Manhattan distance, so we start expanding both nodes again.
After a few expansions, four paths that have the same Manhattan distance - First Street, Second Street, Third Street, and Lincoln Street (southbound). We expand each of those four paths to get to the next state.
After one more expansion, only one path has the lowest Manhattan distance.
The path westward along Main Street will continue to be expanded, and will become the solution.
Because the path along First Street maintained the lowest Manhattan distance to the goal state, our GBFS algorithm recommends this path as the solution, with a path length of 50 units. Remember from the previous post that the Breadth-First Search algorithm found the optimal solution, with a path length of 34 units. This is a good illustration of the fact that the GBFS may not find the optimal solution.
领英推荐
The A* algorithm makes one enhancement to GBFS: in addition to the heuristic distance from a specific state to the goal state, the A* algorithm also looks at the length of the path traversed to that node in order to determine which node to expand.
For our search problem, we'll continue to use the Manhattan distance for the heuristic. The A* algorithm progresses like this, with the current traversal distance noted on the last explored node and the remaining Manhattan distance noted on the frontier nodes:
After one node expansion off the driveway, the two frontier nodes have their respective Manhattan distances.
Since the traversal+Manhattan value for the westbound path is lower, we expanded in that direction.
At the intersection of Residential and Jefferson, both the westward and northward paths have the same traversal+Manhattan values, so we continue expanding along both paths until we get to this point.
One further expansion west shows a higher traversal+Manhattan distance than if we had continued north. So, we pause expanding westward.
Branching at Third Street creates a new frontier element with a higher traversal+Manhattan value.
Branching at Second street does the same.
As soon as we turn on First Street, all five nodes in the frontier have the same traversal+Manhattan value, so we expand all.
After one expansion, the traversal+Manhattan value for the northbound route on Division Street is lower than all others.
Continue expanding on Division Street and Main Street until we "overshoot" the goal state again, at which point all frontier nodes have the same traversal+Manhattan values. Expand everything.
After two further expansions, the path north into the Mall has the lowest traversal+Manhattan value.
In this instance, the A* algorithm finds the optimal solution to this search problem in 34 units. Generally speaking, A* search will find the optimal solution as long as:
Next up: Adversarial search.
Self-promoting plug: Speed and Balance (website), my consulting company, lives at the intersection of business agility and transformative technology. Connect with me to see what AI can do for your organization. To thrive in business today, you need Speed and Balance.