AI Search

Solution A sequence of actions that leads from the initial state to a goal state

• Optimal solution A solution that has the lowest path cost among all solutions.

In a search process, data is often stored in a node, a data structure that contains the following data:

• A state
• Its parent node, through which the current node was generated
• The action that was applied to the state of the parent to get to the current node
• The path cost from the initial state to this node

Nodes contain information that makes them very useful for the purposes of search algorithms. They contain a state, which can be checked using the goal test to see if it is the final state. If it is, the node’s path cost can be compared to other nodes’ path costs, which allows choosing the optimal solution. Once the node is chosen, by virtue of storing the parent node and the action that led from the parent to the current node, it is possible to trace back every step of the way from the initial state to this node, and this sequence of actions is the solution.

To search, we use the frontier, the mechanism that “manages” the nodes.

General Approach

• Start with a frontier that contains the initial state
• Start with an empty explored set.
• Repeat:

1. If the frontier is empty,
   • Stop. There is no solution to the problem.
2. Remove a node from the frontier. This is the node that will be considered.
3. If the node contains the goal state, Return the solution. Stop.
4. Expand the node, and add resulting nodes to the frontier if they aren’t already in the frontier or the explored set.
5. Add the current node to the explored set.

Template Solving Code

# Keep track of number of states explored
self.num_explored = 0
# Initialize frontier to just the starting position
start = Node(state=self.start, parent=None, action=None)
frontier = StackFrontier()
frontier.add(start)
# Initialize an empty explored set
self.explored = set()
 
# Keep looping until solution found
while True:
	# If nothing left in frontier, then no path
	if frontier.empty():
		raise Exception("no solution")
 
	# Choose a node from the frontier
	node = frontier.remove()
	self.num_explored += 1
 
	# If node is the goal, then we have a solution
	if node.state == self.goal:
		actions = []
		cells = []
		while node.parent is not None:
			actions.append(node.action)
			cells.append(node.state)
			node = node.parent
		actions.reverse()
		cells.reverse()
		self.solution = (actions, cells)
		return
 
	# Mark node as explored
	self.explored.add(node.state)
 
	# Add neighbors to frontier
	for action, state in self.neighbors(node.state):
		if not frontier.contains_state(state) and state not in self.explored:
			child = Node(state=state, parent=node, action=action)
			frontier.add(child)