SISTEMAS INTELIGENTES

EXERCISE 2

The 8 puzzle | informed search | Goals

The 8-puzzle

For the second exercise, we will deal with a pair of informed search algorithms: greedy and A*. For that purpose, we will use a fourth domain, the 8-puzzle. We have a 3x3 grid that contains 8 tiles and a hole. In each situation we can slid towards the hole some of its adjacent tiles. As an example, we will use the following intial and goal states:

 4
  1
 3
 7
 2
 5
  
 8
 6

                  
 1
 2
 3
 4
 5
 6
7
  8
 

Initial state 1
Goal state

We will use four possible actions  u, d, l, r (meaning up, down, left, right, respectively) depending on which of the adjacent tiles we move towards the hole.

As before, we will have to encode the problem defining the predicates initial, goal and transition.

Informed search: greedy and A*

Predicate search allows two algorithms for informed search: greedy and a_star. These predicates maintain the fringe as a priority queue ordered by the heuristic function h in the case of the greedy algorithm, and by function f = cost+h in the case of a_star (algorithm A*).

In both cases, we have to specify a new predicate h(N,X), that will define the heuristic function:

h(N,X)
 Specifies the heuristic value X for any node search N, where N has the structure n(State,ParentNodeNum,Action,Cost,Deth)

As an example, the file romania.pl already contains an heuristic function that uses the straight distance from any city to Bucharest


h(n(S,_,_,_,_),D) :- straight(S,D).

Compare the search results using the uninformed search algorithms seen before (breadth, depth, uniform) with respect to:

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

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

GOALS OF EXERCISE 2

  1. Create the third domain 8puzzle.pl.

  2. Make experiments of uninformed search with the scenario seen before. Try also with the following alternative initial states:

 1
 6
  2
 3
 
 8
 4
 7
 5

Initial state 2
 7
  2
 1
 8
 
 3
 5
 4
 6

Initial state 3

  1. Define an admissible heuristic function h for this problem and try the greedy and A* algorithms. Do you reduce the execution time and number of expanded nodes?

Evaluación y entrega

Los ejercicios serán realizados preferentemente en grupos de 2 alumnos. Para la entrega, hay que empaquetar todos los archivos necesarios para los ejercicios 1 y 2 (salvo search.pl) en un único zip y subirlo a la plataforma Moodle. La calificación máxima es de 1.5 puntos = 15% de la asignatura. La fecha límite de entrega es el viernes 22 de abril de 2016. Todas las prácticas deberán superar una defensa presencial que puede realizarse antes de la entrega, durante las horas de laboratorio, o después, reservando turno en horario de tutorías (se hará público un horario de reserva de turno). La copia de prácticas se puntúa automáticamente con un 0 en este apartado.