COMPSCI 367 Artificial Intelligence Assignment 2: PDDL
School of Computer Science
COMPSCI 367 Assignment 2
Total marks: 10.
Weighting: This assignment counts toward 10% of your final mark.
Question 1 [4 marks]
For this question, you are asked to solve a classical planning problem using PDDL. Read the problem description carefully.
Polynesian navigators trained in schools (wānanga) to learn a body of wayfinding techniques that provided the skills necessary to travel to other locations throughout the Pacific, including over vast distances.
Jeff Evans describes the general process as follows:
A voyage is divided into three main stages. First there is the departure and the setting of the primary course. This primary course takes into account any local sea or wind conditions likely to push the waka off course as it departs land. The second challenge for the navigator is to maintain the appropriate course en route, while the third objective is to reach the destination successfully. (Polynesian navigation and the discovery of New Zealand pp. 58-59)
Wayfinding required the ability to interpret reliable environmental signs. For our purposes, we are going to divide this into three actions representing groups of signs to look out for at different degrees of proximity to the destination:
-
1) Navigatorswouldmemoriseastarpath—anumberofstarsthatcanbeseenrisingfromthe same point on the horizon each night—to guide them in their direction of sail. They would also have an understanding of familiar currents and techniques to detect ocean swells that allows them to know more about the general region they are travelling toward. We will call this action schema: check_currents_star_map.
-
2) Whennavigatorswerenearingthelocalityoftheirdestination,theywouldcheckfor signs including cloud formations that typically indicate a land mass is near. It has also been recorded that certain signs of phosphorescence under the water could provide direction toward the nearest land mass. We will call this action schema: check_clouds_phosphoresence.
-
3) Asnavigatorswerenearingtheisland,othersignswouldindicatewherethelandmass was. Certain birds that returned to land at night could provide direction based on their flight
COMPSCI 367 Assignment 2 Page 1 of 5
path. Skilled navigators could identify colours reflecting on the horizon that are indicative of land. Weeds and logs in the water would also indicate that land was close. These signs would result in landfall at their destination. We will call this action schema: check_birds_horizon_detritus.
Our planning problem is represented by the diagram below. We are considering a wayfinder- in-training who is attempting to sail from the origin to the destination.
The vessel will always be at one of the locations on this map.
You should note in this diagram that only the moves indicated by arrows are possible (e.g., you can move from region1 directly to region2 but you cannot move directly from locality1 to locality2). Each of the arrows in the diagram represents a possiblemove. The colours of the arrows also indicate which specific actions need to be performed to move into a new region or to move to a new locality or to land at an island.
For your reference, here is a key to the objects in this diagram:
COMPSCI 367 Assignment 2 Page 2 of 5
Note that for the action check_currents_star_map, the position that the vessel will end up at must be a region. For the action check_clouds_phosphoresence, the position that the vessel will end up at must be a locality. For the action check_birds_horizon_detritus, the position that the vessel will end up at must be an island.
For this assignment, you will write PDDL code to represent this problem and successfully generate a plan to travel from the origin to the destination. All of the terms that have appeared in these instructions so far in bold courier new font and also in the diagrams should also appear in your code as predicates, objects, and actions.
-
(a) Write a PDDL domain file wayfinding_domain.pddl that specifies predicates and the three action schemas: check_currents_star_map, check_clouds_phosphoresence and check_birds_horizon_detritus. (2 marks)
-
(b) Write a PDDL problem file wayfinding_task.pddl that defines all components of the task, including specifying the objects, initial state and the goal state. (2 marks)
Submit the two files wayfinding_domain.pddl and wayfinding_task.pddl. You may use the PDDL Editor to test your code: http://editor.planning.domains/
COMPSCI 367 Assignment 2 Page 3 of 5
Question 2 [3 marks total]
Lots of people training for marathons have a goal, for example, to run a sub-four-hour marathon. When runners talk about running a sub-four-hour marathon, this implies that they will achieve a time 3 hours or over but below four hours. Below are the probabilities associated with the finishing times for runners in marathons.
-
1 Sub-one-hour range (Less than 1 hour) 0
-
2 Sub-two-hour range (1 hour or over but less than 2 hours) 0
-
3 Sub-three-hour range (2 hours or over but less than 3 hours) 0.1
-
4 Sub-four-hour range (3 hours or over but less than 4 hours) 0.4
-
5 Sub-five-hour range (4 hours or over but less than 5 hours) 0.35
-
6 Sub-six-hour range (5 hours or over but less than 6 hours) 0.15
It was found that people who run their first marathon will either get the same time or faster in their second marathon.
Write ProbLog code for this scenario to generate answers for the questions below.
-
(a) Based on the output of your ProbLog program, what is the probability that a runner will run in
the sub-four-hour range in both their first and second marathon? (2 marks)
-
(b) Based on the output of your ProbLog program, what is the probability that a runner will improve their run time so that they fall in the next-shortest sub-hour range in their second marathon. (E.g., if their time is in the sub-hour 6 range in the first marathon, their time will be in the sub-hour 5 range in the second marathon; if their time is in the sub-hour 5 range in the first marathon, their time will be in the sub-hour 4 range in the second marathon; and so on.) (1 mark)
You may use the ProbLog editor: https://dtai.cs.kuleuven.be/problog/editor.html. Please save your code as marathon.txt and submit this file.
Question 3 [3 marks total]
We are analysing the expression of various genes and their relationships to one another.
The following facts are found: The expression of GeneA and/or GeneB regulates the expression of
GeneC. The expression of GeneC regulates the expression of GeneD.
-
(a) Consider the following facts: P(GeneA) = 0.2
P(GeneB) = 0.5
P(GeneC | GeneA, GeneB) = 0.8 P(GeneC | GeneA, ¬GeneB) = 0.1 P(GeneC | ¬GeneA, GeneB) = 0.25 P(GeneC | ¬GeneA, ¬GeneB) = 0
P(GeneD | ¬GeneC) = 0.85 P(GeneD | GeneC) = 0.1
A gene may be in a state of “on” (=1) or “off (=0). Given this information, draw the full conditional probability tables for the following probability distributions: P(GeneA), P(GeneB), P(GeneC), and P(GeneD). (1 mark)
-
(b) Use the variable elimination algorithm to calculate the probability that gene B is “on” given that we have found that gene D is “on”. I.e., What is P(GeneB | GeneD)? Show all working. (2 marks)
COMPSCI 367 Assignment 2 Page 5 of 5
