I am continuing with the Intro to Ai course.
The following is my summary of Unit 2: Problem Solving.
Formal Definition of a problem:
Initial state of the Agent: In route finding it would be the initial position of the Agent
Available Actions for that State: A function that takes a State as input and returns all available Actions that the Agent can execute when in that State. In route finding you would input the agent position and it would return all possible neighboring destinations.
Result: A function taking a State and an Action and returning the new State after applying that Action.
GoalTest: A function taking a State and returns true or false depending on whether the goal is reached.
Path: Sequence of State+Action transitions
PathCostFunction: Takes a Path and returns a Cost of that path. Usually the PathCostFunction is additive, so the Cost of the total path is the sum of the Cost of each step in the Path.
StepCostFuntion: Function that takes a State, Action and resulting State as input and returns the cost of that action. In Route finding the cost could be the distance to travel between the positions or the time it takes to travel.
Problem Summary:
State InitialState
Action[] AvailableActions(State currentState)
State Result(State currentState, Action action)
bool GoalTest(State currentState)
(State,Action)[] Path
int StepCost(State, Action)
int PathCost(Path) = SUM(StepCost for each (State, Action) in Path)
To solve the problem you would start from the InitialState, get all Available Actions for that state, apply those actions using the Result funtion to get a set of new possible States, check whether one of these States is the Goal using the GoalTest, if it is you have solved the problem, if not, continue by expanding these States in the same way one by one. Once you have found the Goal you can calculate the Cost to arrive at the Goal using the PathCost of the Path you found to the Goal. If there are multiple paths to the Goal you might want to optimize by choosing the Path with the lowest PathCost.
Summarized in psuedocode:
currentState = InitialState
while(!GoalTest(currentState))
actions = AvailableActions(currentState)
nextAction = SelectNextAction(actions)
currentState = Result(currentState, nextAction)
This would be the general idea, but the above psuedocode is not complete or even correct.
I have introduced a SelectNextAction function that decides which part of the path to go down. The algorithm above would search down a single path ignoring all the actions along the way that were not selected by the SelectNextAction function. So there is something missing.
These two points are the crux of the topic being discussed in this unit.
- How to make sure you search all relevant paths so that you always find the optimal path to the goal
- How to optimally choose the order in which you search through these paths.
One thing I did not find clearly explained in the course material is the difference between TreeSearch and GraphSearch. What I did not clearly understand initially is that TreeSearch is meant only for Tree structured environments (a structure where each node has children and you search from the root node down (or up depending on how you draw the tree!) until you reach the leaves. You would not apply TreeSearch on a Graph structure. When your environment is a Graph structure - a set of many points with "edges" or "vertices" connecting each point to any number of other points - your TreeSearch algorithm will quickly start looping back to points already traversed and will start going in circles.
To make sure we search all relevant paths without looping back we will introduce two concepts - the Frontier and Explored paths.
Instead of just selecting one possible next action from the current state's available actions, we will save a list of the available States produced from the AvailableActions of the currently selected state. But instead of just saving the State we will store the Path (which is the State including all States and Actions that lead to this State). We will add these Paths to a list of Paths called the Frontier. Initially we will have only the InitialPath in the Frontier, after the first iteration the InitialPath will be removed and all the InitialStates neighbors will be added to the Frontier. Then we will select which state to explore next from all of the Paths that are in the Frontier. In this way we will explore all possible paths.
To avoid back-tracking to states already explored, we will save to the Explored list all the Paths that we remove from the Frontier.
Updated PsuedoCode:
InitialPath = Path(InitialState)
Frontier = [InitialPath]
selectedPath = InitialPath
while(!GoalTest(selectedPath.State))
Frontier.Remove(selectedPath)
Explored.Add(selectedPath)
actions = AvailableActions(selectedPath.State)
foreach action in actions:
Frontier.Add(Result(selectedPath, action))
selectedPath = SelectNextPath(Frontier)
This is the basic common algorithm. The way that the SelectNextPath decides which of the Paths that are in the current Frontier should be expanded/explored leads to different implementations of the search algorithm.
Breadth First
This is the most basic option - we will always explore all of the items in the current Frontier before starting to explore new items added to the Frontier. Basically the frontier would be a first in first out queue. In this way you would expand your search in a circle around the InitialState with each iteration. This would not be a very efficient way to search, it is the equivalent of walking in ever expanding circles (ignoring the terrain, wading through marshes and scaling mountains in perfect circles) until you happen upon your destination.
eg:
State SelectNextState(Frontier)
return Frontier.Pop() // Frontier is a First in First Out queue
Depth First
In this case you would always choose the most recently added path from the Frontier, in effect choosing a direction and exploring it until its end before going back and choosing a different direction and again exploring it until its end until you find your destination. If you are lucky you could find the destination quickly, but if you are unlucky and especially if the distance until the end of your path is long this could turn out very bad. As an extreme example, if the path does not have an end (infinitely long) your search will take forever and never complete the first iteration.
eg:
State SelectNextState(Frontier)
return Frontier.Pop() // Frontier is a Last in First Out queue (stack)
Uniform Cost
Uniform Cost is basically the same as Breadth First except that it takes into consideration the PathCost of reaching the State in the Frontier. It will always choose the State in the Frontier with the lowest PathCost to explore next.
eg:
State SelectNextState(Frontier)
foreach path in Frontier:
if (PathCost(path) < minPathCost) or (minPathCost == None)
minPathCost = PathCost(path)
selectedPath = path
return selectedPath
This is very similar to Breadth First search, except that the search expand in concentric "relief lines" with the same PathCost. It will be more efficient than the Breadth First search especially in cases where there are certain areas of the state map that are much more difficult to reach than others, but it is still not very "goal oriented".
Greedy Best-First
In Greedy Best-First you must first define a distance measure between two states. Then you will always choose the State in the Frontier that is the "closest" to the Destination to expand first.
eg:
State SelectNextState(Frontier)
foreach path in Frontier:
if (Distance(path.State, Destination) < minDistance) or (minDistance == None)
minDistance = Distance(path.State, Destination)
selectedPath = path
return selectedPath
This would be the most efficient algorithm, expanding a single path in the direction of the Goal until it reaches the destination. The problem is that in some cases it will not find the best path. It is like being lost in the woods, taking out your Compass and walking in the direction of your Goal. If you reach a cliff-face you cannot pass you will keep walking around it in the direction that is closest to the direction of the Goal - even if that means you will walk ten times further than if you took the other direction.
A*
This is the "best of both worlds" algorithm that takes Uniform Cost and mixes in a bit of Greedy Best-First for a more efficient version that is still guaranteed to find the optimal result.
Again you must define a "distance" metric (heuristic), but now you will use the PathCost + Distance to determine which is the 'best' Frontier node to expand.
e.g:
State SelectNextState(Frontier)
foreach path in Frontier:
if (PathCost(path) < minPathCost) or (minPathCost == None)
minPathCost = PathCost(path)
selectedPath = path
if (Distance(path.State, Destination) < minDistance) or (minDistance == None)
minDistance = Distance(path.State, Destination)
selectedPath = path
return selectedPath
After completing listening to the unit I implemented an A* algorithm.
One thing that I found was not explained in the course material is what to do when you have a new Path that is in the Frontier or the Explored set but where the new path has lower cost. In the case of the Frontier you would clearly want to replace the existing path with the new, better one. I did the same thing for paths in the Explored set. I removed it from the Explored set and added it to the Frontier.
The complete code can be found in my github, the main parts I will show below:
I defined a Path Node that stored its parent, Cost, current State and the total A* Cost function:
class PathNode(object):
def __init__(self, parent, state, cost, ffunc):
self.Parent = parent
self.State = state
self.Cost = cost
self.FFunc = ffunc
return
def __init__(self, x, y):
self.x = x
self.y = y
And finally a class that implements A* search
class AStarGraph(object):
def __init__(self, costMap, startState, endState):
self.CostMap = costMap
self.dimX = len(self.CostMap)
self.dimY = len(self.CostMap[0])
self.PathStart = PathNode(None, startState, 0, self.f)
self.End = endState
self.Frontier = PriorityQueueSet([self.PathStart])
self.Explored = dict()
def f(self, path):
return self.g(path) + self.h(path)
def g(self, path):
return path.Cost
# The sum of the horisontal and vertical distances should be the perfect candidate for the heuristic
def h(self, path):
distanceX = abs(path.State.x - self.End.x)
distanceY = abs(path.State.y - self.End.y)
return distanceX + distanceY
def takeNextNode(self):
return self.Frontier.pop_smallest()
def expandPathNode(self, path):
# Success!
if path.State == self.End:
return path
self.Explored[path.State] = path
# Add all the options
for option in self.getOptions(path.State):
optionPath = PathNode(path, option, path.Cost+self.CostMap[option.x][option.y], self.f)
if self.Frontier.has_item(option):
if optionPath < self.Frontier.get_item(option):
self.Frontier.replace(optionPath)
continue
if (option in self.Explored):
if optionPath < self.Explored[option]:
del self.Explored[option]
self.Frontier.add(optionPath)
continue
self.Frontier.add(optionPath)
def getOptions(self, state):
options = list()
if (state.x+1 < self.dimX) and (self.CostMap[state.x+1][state.y] != 0):
options.append(State(state.x+1, state.y))
if (state.x-1 >= 0) and (self.CostMap[state.x-1][state.y] != 0):
options.append(State(state.x-1, state.y))
if (state.y+1 < self.dimY) and (self.CostMap[state.x][state.y+1] != 0):
options.append(State(state.x, state.y+1))
if (state.y-1 >= 0) and (self.CostMap[state.x][state.y-1] != 0):
options.append(State(state.x, state.y-1))
return options
def iterate(self):
return self.expandPathNode(self.takeNextNode())
This code is by no means elegant or optimized. It was just a quick and dirty implementation trying to keep close to the definitions provided in the unit.
While looking for more information on the course forum I came across an excellent site that explains all of these search algorithms extremely well. It has much better code and animations of the different algorithms. It is more geared towards gaming but the concepts are the same.
While looking for more information on the course forum I came across an excellent site that explains all of these search algorithms extremely well. It has much better code and animations of the different algorithms. It is more geared towards gaming but the concepts are the same.
