PPAI/L5

From WikiZMSI

Spis treści

[edytuj]

Search algorithms

[edytuj]

Monkey and banana example

There is a monkey at the door into a room. In the middle of the room, a banana is hanging from the ceiling. The monkey is hungry and wants to get the banana, but he cannot stretch high enough from the floor. At the window of the room, there is a box the monkey may use.

The monkey can perform the following actions/moves:

  1. Walk on the floor
  2. Climb the box
  3. Push the box around (if it is already at the box)
  4. Grasp the banana if standing on the box directly under the banana.

Monkey World is described by some 'states' that can change in time. The current state is determined by the position of the objects:

  1. Monkey Horizontal
  2. Monkey Vertical
  3. Box Position
  4. Has Banana

The Initial State:

  1. Monkey is at the door
  2. Monkey is on the floor
  3. Box is at the window
  4. Monkey does not have the banana

Prolog code for initial state: 

state(atdoor, onfloor, atwindow, hasnot).

The Goal: 

state(_, _, _, has).

Not all moves are possible in every possible state of the world e.g. grasp is only possible if the monkey is standing on the box directly under the banana and does not have the banana yet.

Solution


[edytuj]

Excercise 1

Change the Monkey & Banana code this way, that you get the list of all moves done from the initial state to the goal state. Result: 

Solution = [walk(door, window), push(window, middle), climb, grasp]
[edytuj]

Search algorithms

Please find below links to different searching strategies:

[edytuj]

Excercise 2

Connect Monkey & Banana code with the searching algorithms to obtain three different strategies to solve the problem.

Hint:

  • Exchange conc into append, because there is no predefined conc procedure 
conc = append
  • Exchange goal into a specific for the problem 
goal( Node) : Node = state(_, _, _, has).
  • Bagof explanation:

The goal: 

bagof(X, P, L)

will produce the list L of all the objects X such that a goal P is satisfied. For example,let us assume that we have in the program a specification that classifies(some) letters into vowels and consonants: 

class(a, vow). 
class(b, con). 
class(c, con). 
class(d, con). 
class(e, vow). 
class(f, con).


Then we can obtain the list of all the consonants in this specification by the goal: 

?- bagof( Letter, class( Letter, con), Letters). 
Letters : [b,c,d,f]


[edytuj]

Excercise 3

Try to use DFS and BFS strategies to solve 8-puzzle problem.

[edytuj]

N-queens problem

The goal is to place on the nxn size board n queens in such way that they do not attack each other.

The board representation for n=4 is [1/2, 2/3, 3/1, 4/2], which are each queen coordinates.

In Prolog query for the problem: 

solution([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

Three different solutions:

Źródło: "http://wikizmsi.zut.edu.pl/wiki/PPAI/L5"