Combining Agents, Answer Sets and Planning

Lecture course at
NICTA,
(July/August 2003, Sydney, Australia)

 

 

Lecturer: J. Dix


 

Overview      Lecture Notes s


 

Here is a detailed plan of the various chapters:
     
Chapter 1: Introduction, Terminology, Fundamental Architectures (1 Lecture, 3rd July, 2pm)
     
We illustrate the difference between Multi-Agent Systems and classical distributed AI, give a first definition and introduce the terminology.
1.1 General: Distributed AI I vs. Multi-Agentsystems.
1.2 Intelligent Agents: Intelligent interactive Agents, Definition of an Agent, Properties of the environment, reactive/proactive/social, Agent vs. Object-Orientation, PAGE-Description.
1.3 Formal Definitions: Abstract View of an agent: mathematical functions action: S* --> A, env: SxA --> Pot(S), hist, see: S --> P, next: IxP --> I.

1.4 Reactive Agents: Formal Model, Behaviour, Inhibition Relation, Complexity, Pro/Contra, Example: Polar Lander, Cooperative Programming,
1.5 BDI-Agents: Stubborn vs hesitant Agents (Factor gamma), BDI-Structure
1.6 Layered Architectures: Fig. 2.1 [Fig. 1.6 on p. 62], Touring Machine Fig. 2.2 [Fig. 1.7 on p. 63], Autonomous Vehicle, Planning/Modelling/Control Layers, Interrap: Fig. 2.3 [Fig. 1.8 on p. 65]
     
Chapter 2: Distributed Decision Making (2 Lectures, 4th July and 10th July, 2 pm)
     
We consider the most important techniques for decision making: Voting, auctions and Bargaining.
2.1 Evaluation Criteria: Social welfare, Pareto Efficiency, Individual Rational, Stability: Nash Equilibrium.
2.2 Voting: Arrows Theorem, Ways out, Binary Protocol: Fig. 2.1 [Fig 5.1 on p. 206], Borda Protocol: Fig. 2.2 [Table 5.2 on p. 206].
2.3 Auctions: (4 Types (first price open cry--second price sealed bid), private/common/correlated value, Dominant Strategies, Profit for the Auctioneer, Non optimal allocations, Lying and Counterspeculation at Vickrey, Lookahead).
2.4 Bargaining: axiomatic/strategic, Discountfactor: Table 2.1 [Table 5.4 on p. 222], Table 2.2 [Table 5.5 on p. 222], bargaining costs.

     
Chapter 3: Contract Nets and Coalition Formation (1 Lecture, 11th July, 2 pm)
     
We introduce two of the most important principles developed for Agent systems: Contract Nets (how to determine which contracts should be taken) and Coalition Formation (how to determine if and with whom agents should work together).
3.1 Contract-Nets: Tasc-Allocations Model, IR-Contract, Decision making: MC_add, MC_remove, Gradient-Descent, Maximising social welfare, anytime Algorithm. 4 Types of Nets: O, C, S, M. Problem with local Maxima. OCSM-Contracts: Gradient-Descent without Backtracking.
3.2 Coalition Formation: Nash vs Strong Nash,
3.2.1. Coalition Formation for CFG's: Def. CFG, Super additive Games, Search through the CS-Graph: Fig. 3.1 [Fig. 5.3 on p. 244] , Approximations, Last two Layers: CS-Search 1: Fig. 3.2 [Fig. 5.4 on p. 246] Improving the bound by breadth-first search from the top,
3.2.2. Parallelization of the search:,
3.2.3. Payoff Division: 3 Axioms, Shapley-Value.

     
Chapter 4: Answer Set Programming (2 Lectures, 24th and 25th July, 2pm)
   
We  will introduce the ASP paradigm that evolved in the last few years. Starting with definite programs, we introduce positive disjunctive and finally arbitrary disjunctive programs under the answer semantics. We also introduce two ASP engines and discuss a recent approach to do HTN planning in ASP.
4.1 Definite Logic Programs: The classical least herbrand model semantics.
4.2 Positive Disjunctive Logic Programs: Minimal models: why is it useful?
4.3 AnsProlog and its semantics Stable models, answer sets. 
4.4 Declarative Problem Solving Modules: How to program in answer sets?
4.5 DLV vs smodels: Two ASP engines. 
4.6 HTN Planning in ASP: Realising SHOP within an ASP framework.
     
Chapter 5: IMPACT Architecture (1 Lecture, 31st July, 2 pm)
     
We will introduce two running examples, discuss the underlying agent and server architecture and introduce the language in which services offered by agents can be expressed.
5.1 Szenarios: CFIT, STORE,
5.2 Agent/Server Architecture: Transducers, Wrappers, Mediators, Verb and Noun-Term , Hierarchies, Service names, Distances, Metrics, Matchmaking, composite Distances.
5.3 The Code Call Mechanism:) As one of our main motivation is to "agentize" legacy code, we discuss how we abstract from software (state of an agent) and how we encapsulate real data into a format that is amenable in logic (Code Calls). We also introduce the message box (which is part of each agent), Integrity Constraints
5.4 Message Box:Definition of Msgbox, Associated Functions, Formats.

     
Chapter 6: Actions and Agent Programs (1 Lecture, 1st August, 2pm)
     
After introducing actions and 3 notions of concurrently executing actions, we introduce status action atoms and define what an agent program is. The rest of the lecture is devoted to define various semantics for agent programs: Feasible, Rational, and Reasonable Status Sets.
6.1 Action Base: Actions, action atoms, precondition, add/delete lists.
6.2 Execution and Concurrency: Concurrency notion conc, executability, Weakly-, Sequential-, Full- Concurrent Execution.
6.3 Action Constraints: Satisfaction of action constraints.
6.4 Agent Programs: Syntax: action status atoms, agent rules, safety of rules, agent decision cycle.
6.5 Status Sets: deontic/action consistency, deontic/action closure, Operator App,
6.6 Feasible Status Sets: definition of feasibility.
6.7 Rational Status Sets: definition of rationality.
6.8 Reasonable Status Sets: definition of reasonable.

     
  Chapter 7: Implementing Agents: An Application (1 Lecture, 7th August, 2pm)  
     
  In this lecture, we determine a syntactically defined class of agents which can be efficiently implemented (in polynomial time): regular agents. They satisfy 4 properties: strong safety (to ensure that ccc's can be evaluated in finite time), conflict-freeness (to ensure that agent programs are consistent), deontic stratification (to ensure there are no loops through negation), boundedness (to ensure a program can be unfolded). We also give an application.
7.1 Weakly Regular Agents: Strong Safety, Binding Patterns, Finiteness Table, Conflict Freedom, Deontic Stratification.
7.2 Regular Agents:Unfolding.
7.3 IADE: GUI.
7.4: Gofish Post Office.

     
  Chapter 8: Planning in Agent Systems (1 Lecture, 8th August, 2pm)  
     
In this lecture, we consider how planners can be incorporated into agent systems for their mutual benefit.
8.1 Planners vs. Agents Agents: Assumptions underlying planners.
8.2 HTN Planning: Methods and operators.
8.3 Agentising SHOP: Agentised methods/operators. Ashop algorithm. Soundness/completeness.
8.4 NEO Domain: Data sources involved, phases of the evacuation process.

8.5 Monitoring Agents: Monitoring agents via checking message flow, declarative planning using dlv.
     
  Chapter 9: Extensions of the basic framework (1 Lecture)  
     
  This chapter describe extensions of our approach including Beliefs, Uncertainty and Time. They will be described only on a high level, without going too much into technical details.


9.1 Meta Agent Reasoning
We extend agent programs by beliefs: agents are allowed to have beliefs about others and to use them in their programs: meta agent programs. We illustrate the notion of a belief status set and show that we can implement meta agent programs by ordinary programs using extended code calls.
9.1.1 Belief Language and Data Structures:Belief atoms, Belief Language. Belief- (Semantics-) Table. 9.1.2 Meta Agent Programs and Status Sets:We introduce meta agent programs and illustrate how the semantics looks like.9.1.3 Reduction to ordinary Programs: We show how meta agent programs can be transformed into ordinary agent programs and thus implemented.

9.2 Probabilistic Agent Reasoning
We extend agent programs so that they can deal with uncertainty: code calls now return random variables.
9.2.1 Probabilistic Code Calls: The machinery with random variables. 9.2.2 Probabilistic Agent Programs:We introduce probabilistic programs and illustrate their semantics. 9.2.3 Kripke Style Semantics: We show how to overcome some limitations of the semantics introduced in 6.2. The price to pay is an exponential Kripke semantics.

9.3 Temporal Agent Reasoning
We extend agent programs by incorporating time: agents are allowed to make commitments into the future.
9.3.1 Timed Actions: Actions have a duration and the state needs to be updated at prespecified points, checkpoints. 9.3.2 Temporal Agent Programs:We introduce temporal annotations and temporal programs. 9.3.3 Semantics:The semantics of temporal programs is described.
  Get slides for first two weeks in pdf Get slides for first two weeks in postscript
  Get slides for third week in pdf Get slides for third week in postscript
  Get slides for fourth and fifth week in pdf Get slides for fourth and fifth week in postscript
     
     
     
        Juergen Dix