COMP9414/9814 Assignment 3
6/6/18, 5(14 pmCOMP9414/9814 Assignment 3
Page 1 of 5file:///Users/yuezhang/Desktop/9414/COMP9414(9814%20Assignment%203.webarchive
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:
6/6/18, 5(14 pmCOMP9414/9814 Assignment 3
Page 2 of 5file:///Users/yuezhang/Desktop/9414/COMP9414(9814%20Assignment%203.webarchive
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,
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/gridworld.pl
6/6/18, 5(14 pmCOMP9414/9814 Assignment 3
Page 3 of 5file:///Users/yuezhang/Desktop/9414/COMP9414(9814%20Assignment%203.webarchive
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 predicate agent_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
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;
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/land.pl
6/6/18, 5(14 pmCOMP9414/9814 Assignment 3
Page 4 of 5file:///Users/yuezhang/Desktop/9414/COMP9414(9814%20Assignment%203.webarchive
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.
Submission
Submit one file called agent.pl using the command
give cs9414 hw3prolog agent.pl
Your solution should work with the supplied file gridworld.pl. Do not change any of the procedures in
this file and do not include the code from this file with your submission.
The submission deadline is Sunday 3 June, 11:59 pm.
15% penalty will be applied to the (maximum) mark for every 24 hours late after the deadline.
Questions relating to the project can be posted to the Forums on the course Web site.
If you have a question that has not already been answered on the Forum, you can email it to
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/trial.txt
http://www.cse.unsw.edu.au/~cs9414/18s1/hw3prolog/gridworld.pl
6/6/18, 5(14 pmCOMP9414/9814 Assignment 3
Page 5 of 5file:///Users/yuezhang/Desktop/9414/COMP9414(9814%20Assignment%203.webarchive
blair@cse.unsw.edu.au
Plagiarism Policy
Your program must be entirely your own work. Plagiarism detection software will be used to compare all
submissions pairwise (including submissions for any similar projects from previous years) and serious
penalties will be applied, particularly in the case of repeat offences.
DO NOT COPY FROM OTHERS; DO NOT ALLOW ANYONE TO SEE YOUR CODE
Please refer to the UNSW Policy on Academic Honesty and Plagiarism if you require further clarification
on this matter.
Good luck!
https://student.unsw.edu.au/plagiarism