Given a problem description, a vacuum search agent searches a sequence of actions that describe the movements that have to be done to clean all dirty squares and then goes back to the start position to shut itself down. A prerequisite for this is that the vacuum agent has complete knowledge about the world, and in particular about where the dirt is located. This means that when the search is performed, no percepts are needed to act upon. As the agent has complete knowledge, there is no need for obtaining information via perception.
breadth-first-search, depth-first-search,
depth-limited-search, iterative-deepening-search.
There are also search algorithms that use heuristic functions:
uniform-cost-search, greedy-search, and
a*-search.
For the vacuum domain, the heuristic function h that is used by
greedy-search and a*-search to estimate the distance
to the goal is defined as the number of pieces of
dirt that are still left times two. The cost for each action is one.
The file ~TDDA23/www-pub/mtrl/labs/ailabs/aima/search/
algorithms/repeated.lisp contains algorithms with loop detection, such as,
for instance no-cycles-depth-first-search. The loop detector
no-returns makes sure that the algorithm does not generate
nodes equal to the parent node. no-duplicates makes sure the
algorithm avoids generating nodes that have been generated before and
no-cycles makes sure no cycles are generated.
The search algorithms take a problem as input and return a sequence of actions
that lead to a predefined goal. The problems can be generated using the
constructor functions for the problem domain. The function
vacuum-problem in the file
~TDDA23/www-pub/mtrl/labs/ailabs/aima/search/domains/vacuum.lisp takes the size of the world in
m x n squares as a mandatory argument together with a
list dirt with squares that are dirty and a probability factor
dirt-probability for a square being dirty as an optional argument.
If dirt is nil dirt is randomly assigned to all
squares using dirt-probability, otherwise not.
The constructor to specify a square is @ and takes an
x-coordinate and a y-coordinate as arguments.
To create a vaccum problem with 2 x 2 squares and dirt at square (1 1),
(the agent starts at square (0 0)), you write:
(setq vp (vacuum-problem 2 2 :dirt (list (@ 1 1)))) which returns
#<vacuum world problem state:((1 0) ((1 1)) 2 2 T (0 0)), expanded: 0 >
where
((1 0) ((1 1)) 2 2 T (0 0)) represents the root node in the search tree.
(1 0) is the agent's direction at the east.
((1 1)) represents the square with dirt.
2 2 is the size of the world.
T denotes the fact that the vacuum agent is switched on.
(0 0) is the agent's position.
To solve a problem with a specific algorithm, use the function
solve.
(solve vp :algorithm #'no-duplicates-breadth-first-search)
prints the following information
Searching... Level Number of nodes in queue ===== ===== 0 1 1 4 2 7 3 8 4 8 5 7 6 5 7 5 8 7 9 7 ===== ===== Search completed! (FORWARD (TURN LEFT) FORWARD (TURN LEFT) SUCK FORWARD (TURN LEFT) FORWARD SHUT-OFF)#<NODE f(9) = g(9) + h(0) state:((0 -1) NIL 2 2 NIL (0 0)) >
You can obtain more information by setting the argument print
to t.
(solve vp :algorithm #'no-duplicates-breadth-first-search :print t)
gives extra information
Action State
===== ======
((1 0) ((1 1)) 2 2 T (0 0))
FORWARD ((1 0) ((1 1)) 2 2 T (1 0))
(TURN LEFT) ((0 1) ((1 1)) 2 2 T (1 0))
FORWARD ((0 1) ((1 1)) 2 2 T (1 1))
(TURN LEFT) ((-1 0) ((1 1)) 2 2 T (1 1))
SUCK ((-1 0) NIL 2 2 T (1 1))
FORWARD ((-1 0) NIL 2 2 T (0 1))
(TURN LEFT) ((0 -1) NIL 2 2 T (0 1))
FORWARD ((0 -1) NIL 2 2 T (0 0))
SHUT-OFF ((0 -1) NIL 2 2 NIL (0 0))
===== ======
Total of 57 nodes expanded.
Note: Some of the algorithms may not find a solution in an acceptable time span and you will have to stop the execution.
time which returns
the search time as well as the amount of memory used during the search.(time (solve vp :algorithm #'no-cycles-breadth-first-search))
; cpu time (non-gc) 4,640 msec user, 360 msec system ; cpu time (gc) 350 msec user, 40 msec system ; cpu time (total) 4,990 msec user, 400 msec system ; real time 5,661 msec ; space allocation: ; 394,524 cons cells, 6,613 symbols, 414,696 other bytes
run-problem which returns the points for a vacuum
agent that uses search.(run-problem vp :algorithm #'no-duplicates-depth-first-search :display t)
compare-search-algorithms which returns a table with information about
the different algorithms' efficiency, among which the cost and the number
of expanded nodes.
(compare-search-algorithms
#'(lambda ()
(vacuum-problem 3 3 :dirt nil))
'(a*-search no-duplicates-breadth-first-search))
returnsSolved Cost Length Nodes Algorithm ====== ====== ====== ======= ========= 10 10.8 10.8 335.7 A*-SEARCH 10 10.8 10.8 398.5 NO-DUPLICATES-BREADTH-FIRST-SEARCHThis means that a*-search found a solution in 10 out of 10 cases, that the cost for the length of the solution was 10.8 in average, and that the algorithm expanded on average 335.7 nodes.
Note! You have to use a lambda-expression to obtain the problem. Otherwise the world is not re-initialized between the different executions for the different algorithms.
su6-6 <6> emacs-allegro-cl
:ld ~TDDA23/www-pub/mtrl/labs/ailabs/aima/aima
(aima-load 'search)
su6-6 <1> ~TDDA23/www-pub/mtrl/labs/ailabs/emacs-allegro-garnet:ld ~TDDA23/www-pub/mtrl/labs/ailabs/aima/aima
(aima-load 'search-gui)
depth-limited-search
you will have to define own functions that you have to run.(defun depth-limited-search-5 (problem)
(depth-limited-search problem 5))
(solve vp :algorithm #'depth-limited-search-5)