Intro to AI with Python - Unit 0, Part 1: Basic 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.
Artificial Intelligence is more than just large language models. There are a whole host of AI concepts and solutions that don’t involve language processing at all. The first class of problems covered by the course is Search.
Search problems involve trying to get from an initial state to a goal state by following a series of actions from an available set. A standard example of a Search problem is driving directions. The initial state could be your home and the goal state could be the restaurant you’re heading out to for dinner. The set of available actions is each road, fork, and turn on the map.
Solutions to the driving directions search problem can be expressed as a path. Intuitively, the directions from your house to the restaurant could be: left turn out of your driveway, right turn on Division Street, right turn on Main Street, left turn on Mall Drive, and left turn into the restaurant parking lot. The quality of the solution is determined by the “cost” of the path provided by the solution. Clearly, there are many paths from your house to the restaurant. The objective of most search problems, therefore, ?is to look for the optimal solution - the one that minimizes the path cost.
Terminology:
The data for the search problem is typically stored as Nodes. A node is a structure that keeps track of a state, a parent state, the action taken to get from the parent state to this node, and the path cost from the initial state.
The explored set is a set of states that you have already visited when traversing the full set of states. The frontier is the set of next explorable states.
The general algorithm to solve a search problem is as follows:
1 - Start with a frontier that contains the initial state
2 - Start with an empty explored set
3 - Repeat
3.1 - If the frontier is empty, then there is no solution
3.2 - Remove a node from the frontier
3.3 - If node is a goal state, return the solution
3.4 - Otherwise, add the node to the explored set, expand the node, and add resulting nodes to the frontier but only if the expanded node is not in the explored set
Expanding a node in step 3.4 involves investigating all available actions from a particular node and identifying all next states as a result of each of those actions.
There are a couple of options when removing a node from the frontier in step 3.2.
If the frontier is implemented as a last-in-first-out (LIFO) stack, the last item added to the frontier becomes the first item removed from the frontier. This approach is called depth-first search (DFS). If a solution exists, DFS is guaranteed to find it. But the solution may not be optimal, i.e. it may not be the “shortest” path from the initial state to the target state.
If the frontier is implemented as a first-in-first-out (FIFO) queue, the first item added to the frontier becomes the first item removed from the frontier. This approach is called breadth-first search (BFS). If a solution exists, BFS is guaranteed to find it, and the solution will be optimal, but the algorithm may require extremely large amounts of memory for storing.
Let’s take a closer look at the example above, and how the Search algorithm could be implemented to get driving directions.
The initial state is your driveway (cell Q23) The goal state is the restaurant parking lot (cell J2)
Start with a frontier that contains the initial state
Start with an empty explored set
In the first iteration of the repeat block, we remove Q23 from the frontier. Q23 is not the goal state, so we add it to the explored set, and expand it. The only one action is to go out of your driveway to cell Q22. That node goes into the frontier.
In the second iteration, we remove Q22 from the frontier. Q22 is not the goal state, so we add it to the explored set, and expand it. There are two possible actions: left turn to P22 or right turn to R22. Those two go into the frontier.
In the next iteration, we remove one of the nodes from the frontier. If using BFS, we pick the first element in the frontier (P22). If using DFS, we pick the second element in the frontier (R22). Let’s assume DFS, we pick P22 from the frontier. P22 is not the goal state, so we add it to the explored set, and expand it. The actions available are either continue straight to O22 or turn around to Q22. Since Q22 is already in the explored set, we don’t add it to the frontier. So O22 goes into the frontier.
领英推荐
We would continue iterating until we found the goal state.
If using BFS, we would essentially explore every block that’s 1 unit away from the initial state, followed by every block that’s 2 units away from the initial state, then 3 units, etc.
At 34 units, you would arrive at the restaurant along the path: Driveway {Q23}, Left on Residential {West from Q22 to I22}, Right on Division {North from I21 to I4), Right on Main (East from J4 to L4}, Left on Mall Drive {North from L3 to L2}, Left into restaurant parking lot {K1}. All other paths take a larger number of units to get to the restaurant, so this path would be the first to arrive at the goal state, and is the optimal solution.
If using DFS, we would explore the first option at every decision point until we get to the goal state or no further options down a decision point. Let’s say that we expand states in the order Right, Straight, Left, and add them to the frontier in that same order. Because DFS implements the frontier as a LIFO stack, we would always explore the nodes in reverse order that they were added, i.e. down the Left branch first, followed by the Straight branch, followed by the Right branch. Applying that logic, we would go left on Residential until we hit the cul-de-sac at C22. Since C22 is not a solution, and there are no unexplored states to add to the frontier, the next node we remove from the frontier would be E21, right on Eisenhower. We would next explore the cul-de-sac at C13, followed by the cul-de-sac at C4 before finally turning East on Main, and getting to the restaurant. The path would be: Driveway {Q23}, Left on Residential {West from Q22 to E22}, Right on Eisenhower {North from E21 to E4}, Right on Main (East from F4 to L4}, Left on Mall Drive {North from L3 to L2}, Left into restaurant parking lot {K1}. The total number of units traveled would be 42.
It's also important to note that if our expand algorithm reversed the order (Left, Straight, then Right), the algorithm's solution would be different: Driveway {Q23}, Right on Residential {East from Q22 to U22}, Left on Lincoln {North from U21 to U7}, Right on First {East from V7 to Y7 and North from Y6 to Y4}, Left on Main {West from X4 to L4}, Right on Mall Drive {North from L3 to L2}, Left into restaurant parking lot {K1}. The total number of units traveled would be 44.
At this point, the course has provided enough information to be able to code Six Degrees of Separation, the first exercise.
Next up: A more intelligent search, and 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.