SISTEMAS INTELIGENTES

EXERCISE 1

Introduction | Code | Goals


Search algorithms.

The file search.pl implements a Prolog program with several search algorithms directly extracted from the book Artificial Intelligence: A Modern Approach [Russell&Norvig03]. In this first exercise, we will play with 3 uninformed search algorithms: depth first, breadth first and uniform search. We will use this program to build different search domains, including the Romania roadmap (from the book), the 2-buckets problem and the blocks world.

Domain 1: Romania roadmap

This scenario is extracted from [Russell&Norvig03]. We have the Romania roadmap with the following cities and distances among them by road:

Romania roadmap

We want to find a route from Bucharest to Arad (preferrably, the shortest one).

Domain 2: the two buckets problem

In this example, we have a bucket a with volume n and a bucket b of volume m such that gcd(m,n)=1. Initially, both buckets are empty. We want to obtain a given measure k <= max(m,n) of water and the only possible actions are:

A goal state is any of these three cases: (1) a contains k litres, (2) b contains k litres or (3) a and b together contain k litres.

Domain 3: the blocks world

This is a a classical example in Artificial Intelligence. We have a set of n blocks  (enumerated from 0 to n-1). Each block can be located on the table or on top of another block, building towers.  We can only move free blocks, that do not have anything above them. The notation for actions will be move(X,Y) where X is a free block and Y a free block or the table. In the simplest version, the table always has room enough for all the blocks. For our first proofs we will use the following initial and goal states.

blocks

Code

For each domain, we will have to build a prolog file that implements the following predicates:

initial(S) Fixes the initial state S
goal(S) Defines when S is considered to be a goal state
transition(S0,A,S1,C)
 Defines when we can execute action A in state S0, producing state S1 as a result and consuming a cost C
h(N,X) Specifies the heuristic value X for any node search N. We will not use it in this first exercise.
write_action(A) Prints a given action (used for printing the obtained plan, if one is found)
write_state(S) Prints a given state (only used when printing a plan in verbose mode)

A relevant part of the coding exercise will consist in deciding a comfortable representation for states and actions. Of course, apart from these predicates, we can also use as many auxiliary predicates as we consider necessary.

As an example, we provide the romania roadmap scenario in the file romania.pl. In this case, the state is just the name of the city at which we are currently located, and the action is the name of the city where we will go in the next step. The auxiliary predicate road(X,Y,D) contains the road database including not only the pairs of connected cities X,Y but also the road distance D. We have also included the straight distance from Bucharest to each other city (we will use this as heuristic in the next exercise).

To execute a given domain, we will do the following steps. First, we load search.pl in the swipl interpreter as follows:

$  swipl -f search.pl

From the prolog prompt, we can now call predicate search(F,A) where F is some domain file name and A is some uninformed search algorithm (depth, breadth, uniform). As an example, the prolog query:

?- search('romania.pl',depth).

invokes the execution of a depth-first (graph) search algorithm displaying some statistics about the search. Try changing the search algorithms and compare the different results.

Suggestion 1: open the file search.pl and have a look at the predicates graph_search and expand. Can you recognize the pseudocode in [Russell&Norvig03] for the search and expand routines?

Multiple instances: for problems like the buckets riddle or the blocks world, we may have different problem instances by varying the initial and goal states or some of the domain parameters (the capacity of the buckets, the final measure to obtain, etc). We can separate the domain description and the problem instance in different files and call predicate search using a list of files. For instance, for the 2 buckets problem, we can use a file 2b-0.pl with the data:

initial(...).       % fill here!
goal(...) :- ...    % fill here!
capacity(a,5).
capacity(b,3).

a second problem instance 2b-1.pl with

initial(...).             % fill here!
goal(...) :- ...    % fill here!
capacity(a,55).
capacity(b,17).

and so on. If the common part of the domain description (transition, h, write_action, ...) is stored in in 2buckets.pl then, we can make the call

?- search(['2buckets.pl','2b-0.pl'],depth).

and it will work as if the two files were provided altogether.

AUTOMATON MODE

The tool search.pl includes a new module that allows generating the complete automaton for a given planning problem. This is done by ignoring the goal predicate which, as expected, expands all possible nodes, storing the transitions among them too. For using this feature, download file automaton.pl and keep it in the same folder as search.pl. You will also need installing graphviz, a tool for automated graph drawing: be sure that the executable dot is in your path. Finally, after loading search.pl, try invoking the predicate:

?- build_automaton('romania.pl',pdf).

This will create a PDF file romania.pl.pdf displaying the automaton. Be careful with this option, since combinatorial problems easily blow up in the number of possible states. You can also use the format XML

?- build_automaton('romania.pl',XML).

that generates a readable input for the animation tool graph searching. Note that the results obtained by search.pl and by the animation tool may differ due to differences in the node ordering applied when inserting in the fringe.


GOALS OF EXERCISE 1

  1. Create the other two domains 2buckets.pl and blocks.pl. Try several scenarios for the 2 buckets problem and the blocks world.

  2. Make experiments with the 3 algorithms in the 3 domains