[subject outline] [links and resources] [Workshop solutions] [previous announcements] [handbook entry] [2013 COMP90054 page] [Department of Computer Science and Software Engineering]

  • 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.


    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)
    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 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


    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 ]

  • [an error occurred while processing this directive]

    Maintained by Adrian Pearce Copyright: © 2014 Department of Computer Science and Software Engineering
    Disclaimer and Copyright Information Privacy Policy