4G Spaces

Part -1 Search

Introduction

AIMA (Artificial Intelligence: A Modern Approach) might be the most successful textbook about AI. I take this course with Prof. Yixin Chen this semester. I am going to go through all the source code (Python) provided on the website and use them to finish my homework. Therefore, both for my personal referral purpose and for someone who might be interested in using that code, I write a very simple “practical guide to AIMA python source code” series here. Enjoy the magic of AI and Python!

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

to make sure that you have all the packages like Image and Tk with your python. If you don’t have them, just download them. The general guideline is to use apt-get if possible. If you are not using Debian family OS, download the Python package and then use

``Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

at the python package folder.

**Step 2, study the code — tree search

In order to use the code, we have to get familiar with the interface. Let’s get start from search.py and start from depth_first_tree_search (Line 130). The line reads:

def depth_first_tree_search(problem): return tree_search(problem, Stack())

We all know that depth-first search uses Stack. Now let’s omit the technical detail about the implementation of Stack in util.py and check what the “problem” is.

Let’s move to Line 16 of search.py. Here is the definition of Problem class. Here ```Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

``Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

at the python package folder.

**Step 2, study the code — tree search

In order to use the code, we have to get familiar with the interface. Let’s get start from search.py and start from depth_first_tree_search (Line 130). The line reads:

def depth_first_tree_search(problem): return tree_search(problem, Stack())

We all know that depth-first search uses Stack. Now let’s omit the technical detail about the implementation of Stack in util.py and check what the “problem” is.

Let’s move to Line 16 of search.py. Here is the definition of Problem class. Here``` just assigns the initial state. All functions like successor and goal_test are abstract. So, let’s take a look a concrete example. Let’s jump to Line 458, NQueenProblem. It’s a subclass of Problem. It defines the initial state, successor function, and goal_test function. Node that the function conflicted and conflict are for internal use only, there are not the essential part of a problem.

Here, by this case study, we at least know that we have to define a problem with

self.initial field which is the starting point for a problem.
A successor function which generate the successor state for a given state. We will study it carefully later.
A goal_test function which returns either False or True.

The initial is really trivial, we can just assign a initial state to it. Note that Python is a dynamic type language, so we don’t actually care about what type of state is. We will exam the type of state later, but now let’s assume that we know the type of state.

The successor function is really tricky. A straight-forward way to design a successor function will return all possible states in a list. But if you do that, you will get an “Too many values to unpack” error. The design here is actually very neat: instead of put a state in to the list, you can put a (action, state) tuple in to a list. [Line 88 of search.py, in

function expand(problem) ... for (act, next) in problem.successor(self.state)

read this line and you will figure out the date structure to store the successors. The reason is also simple: we can trace the path easily if you record the action down at every expanding step.

Since we moved our eyes to the Node class, let’s exam it carefully.

The constructor of Node is fairly simple. The path function will backtrack all the path to the root. We can modify the code of __repr__ here to print the action out if needed. If any search finally return a result in the form of Node, we can actually get everything we need from this Node, e.g., the path to the node, the action series to the node.

Based on the knowledge above, you can write your own problem model based on tree search. Now let’s move on to graph search.

Step 3. Graph search.

The only difference between tree search and graph search is that in graph search, we have a fringe that stores the closed notes. As you might know, the fringe is implemented in hash table. In Python, there is a tiny technical point: List is not hash-able as it’s mutable, Tuple and String are hash-able. Therefore, if you implement your state as a list, make sure to convert it to a tuple or string or a constant. Otherwise graph search will not be happy with this and complain about it.

If you want to use A* search, another point arises: heuristic function. Note that Line 211 reads:

````Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

``Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

at the python package folder.

**Step 2, study the code — tree search

In order to use the code, we have to get familiar with the interface. Let’s get start from search.py and start from depth_first_tree_search (Line 130). The line reads:

def depth_first_tree_search(problem): return tree_search(problem, Stack())

We all know that depth-first search uses Stack. Now let’s omit the technical detail about the implementation of Stack in util.py and check what the “problem” is.

Let’s move to Line 16 of search.py. Here is the definition of Problem class. Here ```Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

``Part -1 Search

Introduction

Step 1, build the environment.

In this section, you will need three python files:

http://aima-python.googlecode.com/svn/trunk/agents.py

http://aima-python.googlecode.com/svn/trunk/search.py

http://aima-python.googlecode.com/svn/trunk/utils.py

Type:

python agents.py

and

python search.py

at the python package folder.

**Step 2, study the code — tree search

In order to use the code, we have to get familiar with the interface. Let’s get start from search.py and start from depth_first_tree_search (Line 130). The line reads:

def depth_first_tree_search(problem): return tree_search(problem, Stack())

We all know that depth-first search uses Stack. Now let’s omit the technical detail about the implementation of Stack in util.py and check what the “problem” is.

Here, by this case study, we at least know that we have to define a problem with

self.initial field which is the starting point for a problem.
A successor function which generate the successor state for a given state. We will study it carefully later.
A goal_test function which returns either False or True.

function expand(problem) ... for (act, next) in problem.successor(self.state)

read this line and you will figure out the date structure to store the successors. The reason is also simple: we can trace the path easily if you record the action down at every expanding step.

Since we moved our eyes to the Node class, let’s exam it carefully.

Based on the knowledge above, you can write your own problem model based on tree search. Now let’s move on to graph search.

Step 3. Graph search.

If you want to use A* search, another point arises: heuristic function. Note that Line 211 reads:

````

here n is a Node instead of a State. Hence, if you want to get the state information and implement h, you have to use n.state to get the state information.

Step 4. build your application

Perhaps the best part to study the code is to write your own code to test it. Here are my implementations on eightpuzzle and three-missionaries three cannibals problem. The code is ugly and only for study purpose only. _Please don’t directly copy it to your homework.

Eightpuzzle.py

#!/usr/bin/python

from utils import *;
from search import *;

class EightPuzzle(Problem):
	"""The problem of solving a eight puzzle problem """
	def __init__(self, state):
		self.initial = tuple(state)

	def successor(self, state):
		"""In the 8 puzzle problem, move the blank to other position."""
		result = []
		position = list(state).index()
		for action, newposition in self.possible_position(position).iteritems():
			new = list(state[:])
			new[newposition], new[position] = new[position], new[newposition]
			result.append((action, tuple(new)))
		return result

	def possible_position(self, position):
		"""return the possible position"""
		result = {};
		col = position % 3;
		row = position // 3;
		if row != 2:
			result['D'] = position +3
		if col != :
			result['L'] = position -1
		if row != :
			result['U'] = position -3
		if col != 2:
			result['R'] = position +1

		return result
	

	def goal_test(self, state):
		if state[] != :
			return False
		elif state[1] !=1:
			return False
		elif state[2] !=2:
			return False
		elif state[3] !=3:
			return False
		elif state[4] !=4:
			return False
		elif state[5] !=5:
			return False
		elif state[6] !=6:
			return False
		elif state[7] !=7:
			return False
		elif state[8] !=8:
			return False
		else:
			return True 	

	def h(self, node):
		"""Heuristic function"""
		temp=list(node.state)
		sum=
		for x in range(8):	# mahatten distance
			sum = sum + abs(temp.index(x)-x)
		return sum

	def h2(self, node):
		"""bad h"""
		sum = 
		pos = 
		for x in node.state:
			sum = sum + abs(x - pos)
			pos = pos + 1
		return sum

if (__name__=="__main__"):

#	state = [1, 2, 3, 4, 5, 6, 7, 8, 0]
	state = [7, 2, 4, 5, , 6, 8, 3, 1]
#	state = (2, 6, 4, 7, 0, 3, 5, 8, 1)
	instance = EightPuzzle(state)
#	breadth_first_tree_search(instance)
#	depth_first_tree_search(instance)
#	breadth_first_graph_search(instance)
#	print depth_first_graph_search(instance).path()
	print astar_search(instance, instance.h).path()

Boat.py

#!/usr/bin/python

from utils import *;
from search import *;

"""state is a tuple with (#m1, #m2, #s1, #s2, where_is_the_boat)"""

class Boat(Problem):
	def __init__(self, state):
		self.initial = tuple(state)
		self.N = state[]
		self.nodenum = 1

	def successor(self, state):
		result = []
		symbol = state[4]*2 -1; # 0 => -1
		action = 
		for x in (, 1, 2):
			for y in (, 1, 2):
				if x + y >= 1 and x + y <= 2:
					new = (state[] + symbol*x, state[1]-symbol*x, state[2] + symbol*y, state[3] - symbol*y, 1 - state[4])
					if self.check(new):
						result.append((action, new))
						action = action + 1
		self.nodenum = self.nodenum + action
		print result
		return result

	def check(self, state):
		for x in state[:-1]:
			if x<:
				return False;

		if state[]!= and state[] < state[2]: return False;
		if state[1]!= and state[1] < state[3]: return False;

		return True

	def goal_test(self, state):
		if state[] ==  and state[1] == self.N and state[2] ==  and state[3] == self.N and state[4] ==1:
			print state
			return True
		return False;

	def h(self, node):
		return 
		state=node.state
		return state[]

if (__name__=="__main__"):

	state=[3, , 3, , ]

	instance = Boat(state)
#	breadth_first_tree_search(instance)
#	depth_first_tree_search(instance)
#	breadth_first_graph_search(instance)
#	depth_first_graph_search(instance)
	astar_search(instance, instance.h)
	print instance.nodenum

BTW, if you need to highlight your source code and convert it to HTML for example, one of the handy program is GNU source-highlight. I really love this.

最新文章

社会网络

A practical guide to the AIMA Python code -1