This subject will be offered in Semester 2, 2014 by Adrian Pearce & Nir Lipovetzky.
Subject outline
Automated planning is becoming increasingly popular for solving problems for robotic, artificially intelligent or internetworking processes. Autonomous agents are active entities that perceive their environment, reason, plan and execute appropriate actions to achieve their goals, in service of their users.
The subject will show how this work is relevant for many applications beyond the traditional area of artificial intelligence, such as resource scheduling, logistics, process management, service composition, intelligent sensing and robotics.
The subject covers the foundations of automated planning and reasoning techniques that enable agents to reason about actions and knowledge during collaborative task execution. The subject focuses on the fast emerging Golog-family of Situation Calculus-based agent programming languages. A more detailed subject outline is available here.
Readings
The subject does not have any single prescribed text. In general, required readings will be provided ahead of lectures and workshops and are indicated on the Schedule below. Most of the readings are from the following four books, which have been placed on 7 day reserve in the ERC library.
Classical Planning
Hector Geffner and Blai Bonet,
A Concise Introduction to Models and Methods for Automated Planning, Morgan & Claypool, 2013.
e-book in library (unlimited users)
Russell, S. and Norvig, P.,
Artificial Intelligence: A Modern Approach, Third Edition, Pearson, 2010
Rich Planning Formalims & Situation Calculus
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning, Elsevier/Morgan Kaufmann, 2004.
Fagin, R., Halpern, J.Y., Moses, Y., and Vardi, M.Y.
Reasoning about Knowledge. MIT Press, Cambridge, MA, 1995.
Reiter, R.,
Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001. Book home page.
Lectures and workshops
| Day |
Time |
Event |
Location |
Lecturer / Tutor |
| Monday |
11:00am-12:00noon |
Lecture |
Alan Gilbert, Theatre 2
|
Adrian Pearce & Nir Lipovetzky
|
| Wednesday |
10:00am-11:00am |
Lecture |
Doug McDonell-503 (Steve Howard Theatre)
|
Adrian Pearce & Nir Lipovetzky
|
| Wednesday |
3:15pm-4:15pm |
Workshop |
DMD 502 (Comp lab)
|
Toby Davies
|
Schedule (under construction!)
| Wk |
From |
Lectures |
Reading |
Workshop |
Projects |
| 1 |
28 July |
Introduction
Introduction to AI
|
Geffner & Bonet: Chapter 1 Planning and Autonomous Behaviour
|
No workshop (workshops commence in second week)
|
|
| 2 |
4 August |
Introduction to Planning
(slides available under 'Classical Planning Lectures on LMS menu item)
Search Algorithms
|
Geffner & Bonet: Chapter 2 Classical Planning: Full Information and Deterministic Actions
|
Heuristic Search & Pac-Man
Workshop Problems 1
|
|
| 3 |
11 August |
Generating Heuristic Functions
Critical Path Heuristics
|
Geffner & Bonet: Chapter 2 Classical Planning: Full Information and Deterministic Actions
|
Excercises on Heuristic Search
Workshop Problems 2
Workshop 2 solutions are available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
|
|
| 4 |
18 August |
Actions in the Situation Calculus
Planning in the Situation Calculus
|
Brachman: Chapter 14 Actions &
Ryan Kelly's background to thesis (Chapter 2) including references &
Situations (slides by Adrian Pearce) &
Reiter Sections 4.1 The language of the situation calculus;
4.2 Axioms for the situation calculus;
4.3 Reasoning about situations using induction &
4.4 Basic theories of action
Brachman, Chapter 15 Planning
|
Workshop Problems 3
|
Project 1 has been released
|
| 5 |
25 August |
Foundations (Relations between states & possible worlds)
Foundations (States, Intensionality, Partial observability & Epistemic Logic)
|
Section 1 & 2.1 of Logical Foundations of Agent-Based Computing, van der Hoek, W. , Logical Foundations of Agent-Based Computing, LNAI 2086, pp. 50-73 (2001); &
Section 2.2 van der Hoek (Alternating Bit Protocol)
Fagin, Section 1.1 pp. 1-7 (Muddy Children Problem); Sections 2.1-2.3 (Muddy Children Revisited) & 2.4;
|
Excercises on Classical Planning
Workshop Problems 4
|
|
| 6 |
1 September |
Golog & ConGolog (slides by Yves Lespérance)
MIndiGolog (slides by Adrian Pearce)
Delete Relaxation Heuristics
|
Giuseppe De Giacomo, Yves Lespérance, and Hector J. Levesque., ConGolog, a concurrent programming language based on the situation calculus, Artificial Intelligence, 121(1-2):109--169 (2000)
Prolog (Wikipedia)
Primer: Introduction to Prolog; How Prolog Works; Terms in Prolog & Prolog Coding (notes by Peter Schatche)
|
Excercises on PDDL and General Heuristics
Workshop Problems 5
|
Project 1 due
MIndiGolog Paper, by Ryan Kelly and Adrian Pearce
The MINdiGolog interpreter we use can be found here on the Department machines under project resources; it uses SWI Prolog (Multi-threaded, version 5.6.30) which is already installed in the computer labs.
|
| 7 |
8 September |
Regression
Golog & ConGolog (continued)
MIndiGolog(continued)
|
Reiter Section 4.5 Regression
Operational Semantics of ConGolog (slides by Giuseppe De Giacomo)
IndiGolog: Sensing and Planning under incomplete information and dynamic environments (slides by Yves Lespérance)
|
Workshop Problems 6
|
Project 2 has been released
If you use IndiGolog, you can download it at sourceforge.
|
| 8 |
15 September |
Landmark Heuristics
State of the Art in Classical Planning
|
Reiter Chapter 7 Time, Concurrency, and Process
IndiGolog: A High-Level Programming Language for Embedded Reasoning Agents, by Giuseppe De Giacomo, Yves Lesperance, Hector J. Levesque, and Sebastian Sardina
|
Workshop Problems 7
Workshop 2 solutions are available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
|
|
| 9 |
22 September |
Knowledge
Preliminary presentations (project 2)
|
Property persistence
|
Workshop Problems 8
Workshop 2 solutions are available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
|
|
| |
29 September |
Non-teaching period
|
|
No workshop
|
|
| 10 |
6 October |
Classical Planning applications:
Plan Recognition (invited lecture by Miquel Ramirez)
Classical Planning applications:
Fully observalbe non-deterministic planning (guest lecture by Christian Muise)
|
Geffner & Bonet: Section 4.3 - Goal and Plan Recognition
|
Working on project 2
|
|
| 11 |
13 October |
Lectures this week dedicated to working on project 2 with your group members
|
|
Working on project 2
|
Preliminary Electronic submission of Project 2
|
| 12 |
20 October |
Project presentations this week
Project presentations week
|
Syllabus (what is/is not examinable in 2014)
2014 Exam cover page (gives you idea of exam conditions, what is/is not allowed etc.)
Past exam papers (for all subjects) are available here.
|
Project presentations
|
Final Electronic submission of Project 2
|
Marks
Marks will be released here, when the time comes.
Workshop solutions
Workshop 2 solutions are available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
Links and project resources
Links mentioned in Lectures
Patrizi, Lipovezthky, De Giacomo and Geffner,
Computing Infinite Plans for LTL Goals Using a Classical Planner, IJCAI 2011, Barcelona
Project resources
Project resources
here
and on the Departments systems at /home/subjects/482/local.
Adrian's writing resources useful for the project at http://www.cs.mu.oz.au/482/writing.html
Text resources
Knowledge in Action: Resources (including code from book) at www.cs.toronto.edu/cogrobo/kia/.
Related Subject (with additional material)
PhD Course Reasoning about Action and High-level Programs (Roma 2011)
Additional Readings on Artificial Intelligence & Prolog
Leon Sterling and Ehud Shapiro, The Art of Prolog, 3rd Edition, The MIT Press 1994.
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd Edition
Prentice Hall, 2003.
Intelligent Agent Laboratory
Adrian Pearce's Agent bibliography at http://www.cs.mu.oz.au/482/biblio/
For information about research and development of intelligent agent technology at The University of Melbourne, see www.agentlab.unimelb.edu.au
Competitions
2011 General Game Playing Competition
International Planning Competition, 2011
RoboCup Rescue Competition
Links mentioned in lectures
Global Air Traffic (The Swiss Technorama Science Centre)
Past Agent programming language projects (for your interest)
| Authors |
Title |
Report |
Code |
|
Zheng Huang, Ganesh Arunachalam & Ranjani Nagarajan
|
Command-line and visual simulation of kitchen domain
|
ganesha.pdf
|
ganesha_simulation.zip (need to extract files into a local directory to run executable)
|
|
Xiaohui Wu, Wade Huang and Xi Liang
|
A study of MIndiGolog by implementing an extreme kitchen management system
|
xiaohuiw.pdf
|
xiaohuiw.zip (need to extract files into a local directory to run executable)
|
|
Xuqing (Jess) Qi
|
Implementation of agent and resource allocation algorithm in MIndiGolog
|
qix.pdf
|
qix.zip (need to extract files into a local directory to run executable)
|
|
Michelle Blom
|
A comparative analysis of ConGolog and Concurrent METATEM
|
mlblom.pdf
|
|
|
Puming Zhao
|
Concurrent implementation of an extreme kitchen domain
|
zhaop.pdf
|
|
|
Wern Li Wong
|
Resolving taskordering using collaborative inductive logic programming (CILP)
|
wongwl.pdf
|
|
|
Jeremy Nicholson
|
Using Bisimulation to Facilitate Decision-Making in Partially-Observalbe Systems
|
jeremymn.pdf
|
|
|
Kathryn Francis and Richard Wilson
|
Team Formation and Role Allocation in Distributed Multi-Agent Systems
|
rewilson.pdf
|
rewilson.zip
|
|
Jarrod Sibbison & Kong Guan Tan
|
Dynamic skill-based role assignments
|
kgtan.pdf
|
kgtan.zip (need to extract files into a local directory to run executable)
|
|
Edwin Wirawan
|
Optimizing choice between true concurrency and interleaved concurrency
|
ewirawan.pdf
|
ewiriwan.zip (need to extract files into a local directory to run executable)
|
|
Ben White
|
Techniques for controlling non-deterministic procedure selection in high-level programs
|
bmwhite.pdf
|
bmwhite.zip (need to extract files into a local directory to run executable)
|
|
Joseph Donal Paterson & Martin Stradling
|
Real-time and agent-time constraint satisfaction
|
josephdp.pdf
|
josephdp.zip (need to extract files into a local directory to run executable - example of achieving better concurrency)
|
|
Andrew Bakshi
|
Introducing and reasoning about uncertainty in MIndiGolog
|
abakshi.pdf
|
|
|
Benjamin Goudey
|
A comparison ofsituation calculus and event calculus
|
bwgoudey.pdf
|
|
|
Zuiena Hussain & Brendan Moran
|
Comparative report: incremental interpreters and ConGolog+HTN construct
|
hussain.pdf
|
|
|
Xijing Dai & Juxing Wang
|
Prioritised concurrency for multi-agent scheduling
|
juxing.pdf
|
|
|
Olga Ohrimenko
|
Operating system schedulaer in the agent environment
|
olgao.pdf
|
|
|
Paul Bone
|
Extending temporal constraints in MIndiGolog
|
pbone.pdf
|
pbone.zip (need to extract files into a local directory to run executable)
|
|
Qiao Wang & Lei Zhang
|
Priority goal identifying algorithm with weight labeling method
|
qiaow.pdf
|
|
[ Return to top of subject page ]
