COMP9414/9814 Artificial Intelligence
Session 1, 2018
Project 3, Option 2: Prolog (BDI Agent)
Due: Sunday 3 June, 11:59 pm
Marks: 18% of final assessment
Introduction
In this Assignment, you will be implementing an agent to move around in a rectangular
environment, picking up stones from the land and dropping them in the water, thus
building a path to the location of a dangerous sea monster. The final stone must be
dropped on the head of the sea monster in order to kill it.
In doing this assignment, you will implement the basic functions of a simple BDI Agent
that operates in a Gridworld, and learn about the ideas underlying BDI agents.
Gridworld
The Gridworld consists of a two-dimensional grid of locations, extending to infinity in
both directions. Some locations are specified as being on land, while the others are
assumed to be water. In the first round of the simulation, the agent must construct a
minimal list of locations in which stepping stones need to be dropped, in order to
create a path to the location of the monster. In subsequent rounds, stones will appear
randomly at certain locations. The agent is able to move to a place where a stone is
located and execute a pick action. It can then move to one of the pre-computed drop
locations and execute a drop action. The agent can stay where it is, or move one square
at a time, either horizontally or vertically. The world is dynamic in that stones can
appear spontaneously at random locations at any time.
The supplied Prolog program gridworld.pl implements a system for conducting an
experimental trial consisting of an agent in the Gridworld that repeatedly executes the
BDI interpretation cycle for 100 iterations (you may like to reduce this number while
debugging your program). The initial state of the world is always that there are no
stones, and the agent is at location (1,1) holding no stones.
The agent’s goals at any time are in the form [goal(X1,Y1), … ,
goal(Xn,Yn)] where (X1,Y1), … , (Xn,Yn) are locations where stones can be picked up.
The agent’s intentions are in the
form intents(Intents_drop,Intents_pick) where Intents_drop and Intents_pick each
consist of a list of pairs of the form [goal(X,Y), Plan], representing a goal with an
associated plan (which may be the empty plan), ordered according to some priority.
Each plan is a list of actions. To fulfil an intention, the agent executes the plan
associated with its goal, which will make the agent move along a path towards the goal
and then either pick or drop a stone. If, when the agent chooses an intention to fulfil,
the plan associated with the goal of that intention is empty or cannot be executed, the
agent creates a new plan for the goal and then begins to execute this plan.
In each cycle the agent executes one action. There are three types of action the agent
can execute:
move(X,Y) – the agent moves to location (X,Y)
pick(X,Y) – the agent picks up the stone at (X,Y)
drop(X,Y) – the agent drops a stone at (X,Y)
move(X,Y) can be executed when the Manhattan distance from the agent’s current
location to (X,Y) is either 0 or 1, and land_or_dropped(X,Y) is true.
pick(X,Y) can be executed if the Manhattan distance from the agent’s current location
to (X,Y) is exactly 1, have_stones(0) is true and stone_at(X,Y) is true.
drop(X,Y) can be executed if the Manhattan distance from the agent’s current
location to (X,Y) is exactly 1, have_stones(1) is true and land_or_dropped(X,Y) is false.
BDI Interpreter
In each time cycle, the agent executes the interpreter shown abstractly in the table
below. The new external events on each cycle are represented as a list of terms of the
form stone(X,Y), within some viewing distance of the agent. The agent will repeatedly
perceive any stone so long as it remains in viewing range. It is not assumed that the
agent can see all of the grid, so a new external event may occur as the agent is moving
towards another target. Each new perceived event stone(X,Y)should trigger a goal for
the agent, represented as a term of the form goal(X,Y). Any new goal is incorporated
into the agent’s current intentions according to the agent’s prioritization strategy (see
below). The agent then selects one action for execution from the current set of
intentions. Here the agent always selects the first intention on the list if there is one,
creates or modifies the associated plan if necessary, then selects the first action in that
plan, removes the selected action from the chosen plan, executes the action, and
updates the list of intentions by removing any successfully achieved goals.
Abstract BDI Interpreter:
initialize-state();
do
Percepts = get_new_external_events();
G = trigger(Percepts);
I = incorporate_goals(G, B, I);
(I, A) = get_action(B, I);
execute(A);
Observation = observe(A);
B = update_beliefs(Observation);
I = update_intentions(Observation);
until quit
The agent maintains separate lists of drop and pick intentions. Within each list, its
prioritization strategy is very simple: without reordering existing goals, each new goal is
inserted into the list of intentions in order of distance from the current position (closer
before further away). This means the agent maintains a “commitment” to pursuing its
goals (the agent only changes its intention to pick up a stone if new stone appears at a
closer location.
Assignment
You are supplied with a Prolog program in a file gridworld.pl that implements the
experimental setup, including the generation of events (appearance of stones) and the
execution of actions, and the agent’s BDI interpretation cycle and observation
functions.
When executed, the run command loads a file land.pl containing the location of the
monster in the form monster(X,Y), and a list of locations which are on land in the
form land(X,Y). The current location of the agent is specified by a dynamic
predicateagent_at(X,Y).
[4 marks] Write a Prolog procedure
initial_intentions(Intentions)
which binds Intentions to intents(L,[]) with L in the form [[goal(X1,Y1),[]], … ,
[goal(Xn,Yn),[]]]. Here (Xn,Yn) is the location of the monster and (X1,Y1), … , (Xn-1,Yn-1) are
places where the mininum number of stones need to be dropped in order to allow the
agent to move along some path from its current location to that of the monster.
[1 mark] Write a Prolog procedure
trigger(Percepts, Goals)
which takes a list of percepts, each of the form stone(X,Y), and converts it into a
corresponding list of goals, each of the form goal(X,Y).
[4 marks] Write a Prolog procedure
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/gridworld.pl
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/land.pl
incorporate_goals(Goals, Intentions, Intentions1)
This procedure should take two inputs, as follows:
1. a set of Goals in the form of a list [goal(X1,Y1), … , goal(Xn,Yn)]
2. the current Intentions of the agent, in the
form intents(Int_drop,Int_pick) where Int_drop, Int_pick are lists of intentions in
the form [goal(X,Y), Plan]
Your procedure should return the updated Intentions of the agent after inserting the
new goals into Int_pick. The new goals should be inserted into the existing list in
decreasing order of the length of the shortest valid path from the agent’s current
position. A valid path is one which passes through only locations (X,Y) for
which land_or_dropped(X,Y) is true. More precisely, a new goal should be placed
immediately before the first goal in the list whose path length is longer than that of the
new goal (without reordering the current list of goals). If no such valid path exists, then
the new goal should not be inserted. Note that because of repeated perception of the
same event, only goals not already in the list should be inserted into the list of
intentions. The Plan associated with each new goal should be the empty plan
(represented as the empty list []).
[4 marks] Write a Prolog procedure
get_action(Intentions, Intentions1, Action)
which takes the agent’s current Intentions in the form intents(Int_drop,Int_pick) (as
described above) and computes an action to be taken by the agent as well as the
updated Intentions. The agent should select an intention as follows:
If the agent is currently holding a stone, indicated by agent_stones(1), then the
first intention [goal(X,Y), Plan] in the list Int_drop of dropping intentions is
selected;
otherwise, if the list Int_pick of picking intentions is not empty, then its first
item [goal(X,Y), Plan] is selected;
otherwise, no intention is selected; in this case, the agent’s Intentions should
remain as they are, and it should stay in its current location (i.e. action
is move(X,Y) if it is currently at (X,Y)).
The file gridworld.pl includes an applicable() predicate for testing whether an action is
applicable. If the first action in the selected plan is applicable, the agent selects this
action and updates the plan to remove the selected action. If there is no associated plan
(i.e. the plan is the empty list) or the first action in the plan for the selected intention is
not applicable in the current state, the agent should construct a new plan to go from its
current position to the goal location and then either pick or drop a stone at that
location. The plan will be a list of move actions followed by either a pick or drop action.
The agent should then select the first action in this new plan, and update the list of
intentions to incorporate the new plan (minus the selected first action).
[1 mark] Write a Prolog procedure
update_intentions(Observation, Intentions, Intentions1)
to update the agent’s intentions, based on observation. An at(X,Y) observation should
not change the agent’s intentions. In the case of a picked() or dropped() observation,
the agent should remove the corresponding plan from its list of intentions (since this
plan has now successfully been executed).
There are 4 marks allocated for comments and programming style.
In general, a program that attempts a substantial part of the job but does that part
correctly will receive more marks than one attempting to do the entire job but with
many errors.
You can see an example of the output of a trial run by clicking here. Note
that goal(9,2) is not inserted into the list of Intentions until after a stone has been
dropped at (5,3) in Cycle 8 (thus greating a viable path). At Cycle 38, the agent
abandons its Plan for goal(2,3) and instead gives priority to the new stone that just
appeared at (3,7).
Path Search Code
For this assignment, you are free to copy any of the path search code supplied for
Assignment 2, and adapt it for the current task. You might
find pathsearch.pl and ucsdijkstra.pl particularly useful.
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/trial.txt
COMP9414/9814 Artificial Intelligence
Session 1, 2018
Project 3, Option 2: Prolog (BDI Agent)
Introduction
Gridworld
BDI Interpreter
Assignment
Path Search Code