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

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.

Schedule (under construction!)

Wk From Lectures Reading Workshop Projects
1 27 July Introduction



Possible Worlds


Fagin, Section 1.1 pp. 1-7 (Muddy Children Problem); Sections 2.1-2.3 (Muddy Children Revisited) & 2.4;
No workshop (workshops commence in second week)  
2 3 August Introduction to AI (slides available under 'Classical Planning Lectures on LMS menu item)

Introduction to Planning
(slides available under 'Classical Planning Lectures on LMS menu item)
Geffner & Bonet: Chapter 1 Planning and Autonomous Behaviour

Geffner & Bonet: Chapter 2 Classical Planning: Full Information and Deterministic Actions
Introduction to Pac-Man  
3 10 August Intensionality



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

Geffner & Bonet: Chapter 2 Classical Planning: Full Information and Deterministic Actions
Heuristic Search & Pac-Man

Workshop Problems 1
 
4 17 August Actions in the Situation Calculus



Generating Heuristic Functions
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

Excercises on Heuristic Search

Workshop Problems 2

Workshop 2 solutions will be made available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
Project 1 has been released
5 24 August Planning in the Situation Calculus

Critical Path Heuristics


Brachman, Chapter 15 Planning

Workshop Problems 3  
6 31 August 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 Classical Planning

Workshop Problems 4
Project 1 due

MIndiGolog Paper, by Ryan Kelly and Adrian Pearce

The MINdiGolog interpreter we use can be found by downloading the zip here on the Department machines under project resources; it uses SWI Prolog (stable version) which is already installed in the computer labs.
7 7 September Golog & ConGolog (continued)

Landmark Heuristics (I)
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)
Excercises on PDDL and General Heuristics

Workshop Problems 5

You can use these tools/resources at www.planning.domains (such as editor.planning.domains).


You can see project 2 from 2014

If you use IndiGolog, you can download it at sourceforge.

 
8 14 September Regression


Landmark Heuristics (II)
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 6 Project 2 has been released
9 21 September Golog & ConGolog (Golog Evaluation Semantics - Trans)

Preliminary project discussion (project 2)
Property persistence

Workshop Problems 7
Workshop 2 solutions will be made available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
 
  28 September Non-teaching period   No workshop  
10 5 October State of the Art in Classical Planning

Classical Planning applications:
Fully observalbe non-deterministic planning (guest lecture by Christian Muise)
Geffner & Bonet: Section 4.3 - Goal and Plan Recognition

Workshop Problems 8
Workshop 2 solutions will be made available on the main LMS page link (on the left) "Classical planning lectures & workshop solutions"
Project 1 marks have been released (CSV file)
11 12 October Knowledge (I)

Project & Exam discussion
Revision (read the Syllabus for guidance on what to study for exam!) Working on project 2 Preliminary Electronic submission of Project 2
12 19 October Project presentations this week

Project presentations week
 

Past exam papers (for all subjects) are available here.
Project presentations View the Tournament results (run daily)

Final Electronic submission of Project 2

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

Adrian's writing resources useful for the project at 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 ./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 ]

[an error occurred while processing this directive]


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