Multi-Agenten Systeme
(VU 2.0, Ausgewaehlte Kapitel der KI
SS 2000, TU Wien)

Kapitel 1:	Introduction and Terminology (Dienstag, 13. Juni, 14ct) We illustrate the difference between Multi-Agent Systems and classical distributed AI, give a first definition and introduce in 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 Mathematical Definitions: Abstract View of an agent: mathematical functions action: S* --> A, env: SxA --> Pot(S), hist, see: S --> P, next: IxP --> I. Get Slides
Kapitel 2:	Fundamental Architectures: (Mittwoch, 14. Juni, 14ct) We illustrate the four main agent architectures. 2.1 Reactive Agents: Formal Model, Behaviour, Inhibition Relation, Complexity, Pro/Contra, Example: Polar Lander, Cooperative Programming, 2.2 BDI-Agents: Sture vs Unsichere Agenten (Factor gamma), BDI-Structure 2.3 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] 2.4 Logic-based Architectures: Symbolic AI, Agent as Theorem Prover, Database as internal state, 2.4.1 Wumpus World in AL 2.4.2 Wumpus World in PL1: Situation-calculus, result-terms, fluents, memory-predicate At(,,,), Qualification-Problem, nonmonotonic logics, Frame-Problem, Successor-State Axioms: Automatic Generation and Reduction of their number: #A + #F instead of #A x #F. Get Slides
Kapitel 3:	Distributed Decision Making (15. Juni, 14ct und 16. Juni, 10ct) We consider the most important techniques for decision making: Voting, auctions and Bargaining. 3.1 Evaluation Criteria: Social welfare, Pareto Efficiency, Individuel Rational, Stability: Nash Equilibrium. 3.2 Voting: Arrows Theorem, Ways out, Binary Protocol: Fig. 3.1 [Fig 5.1 on p. 206], Borda Protocol: Fig. 3.2 [Table 5.2 on p. 206]. 3.3 Auctions: (4 Typen (first price open cry--second price sealed bid), private/common/correlated value, Dominant Strategies, Profit for the Auktioneer, Non optimal allocations, Lying and Counterspeculation at Vickrey, Lookahead). 3.4 Bargaining: axiomatic/strategic, Discountfactor: Table 3.1 [Table 5.4 on p. 222], Table 3.2 [Table 5.5 on p. 222], bargaining costs. Get Slides
Kapitel 4:	Contract Nets and Coalition Formation (16. Juni, 14ct) Wir 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). 4.1 Contract-Nets: Tasc-Allocations Model, IR-Contract, Decision making: MC_add, MC_remove, Gradient-Descent, Maximizing social welfare, anytime Algorithm. 4 Types of Nets: O, C, S, M. Problem with local Maxima. OCSM-Contracts: Gradient-Descent without Backtracking. 4.2 Coalition Formation: Nash vs Strong Nash, 4.2.1. Coalition Formation for CFG's: Def. CFG, Super additive Games, Search through the CS-Graph: Fig. 4.1 [Fig. 5.3 on p. 244] , Approximations, Last two Layers: CS-Search 1: Fig. 4.2 [Fig. 5.4 on p. 246] Improving the bound by breadth-first search from the top, 3.2.2. Paralellization of the search:, 4.2.3. Payoff Division: 3 Axioms, Shapley-Value) Get Slides
Kapitel 5:	IMPACT Architecture (19. Juni, 10ct) We will introduce three running examples, discuss the underlying agent and server architecture and introduce the language in which services offered by agents can be expressed. 5.1 Three Szenarios: CFIT, CHAIN, STORE, 5.2 Agent Architecture: Transducers, Wrappers, Mediators. 5.3 Server Architecture: Verb and Noun-Term , Hierarchies, Service names, Distances. 5.4 Service Description Language: Metrics, Matchmaking, composite Distances.) Get Slides
Kapitel 6:	The Code Call Mechanism (19. Juni, 14ct) 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 and illustrate how services are implemented. 6.1 Software Code Abstraction: Types, Functions, Composition Operators, State of an Agent. 6.2 Code Calls: Code Calls, Variables, Code Call Atoms, Code Call Conditions, Safety. 6.3 Message Box:Definition of Msgbox, Associated Functions, Formats. 6.4 Integrity Constraints: Definition. 6.5 \sdl and Code Calls: Service Rules, Service Definition Program. Get Slides
Kapitel 7:	Actions and Agent Programs (20. Juni, 14ct) 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. 7.1 Action Base: Actions, action atoms, precondition, add/delete lists. 7.2 Execution and Concurrency: Concurrency notion conc, executability, Weakly-, Sequential-, Full- Concurrent Execution. 7.3 Action Constraints: Satisfaction of action constraints. 7.4 Agent Programs: Syntax: action status atoms, agent rules, safety of rules, agent decision cycle. 7.5 Status Sets: deontic/action consistency, deontic/action closure, Operator App, 7.6 Feasible Status Sets: definition of feasibility. 7.7 Rational Status Sets: definition of rationality. 7.8 Reasonable Status Sets: definition of reasonable. Get Slides
Kapitel 8:	Regular Agents (21. Juni, 10ct) 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 experimental results of checking these properties. 8.1 Weakly Regular Agents: Strong Safety, Binding Patterns, Finiteness Table, Conflict Freedom, Deontic Stratification. 8.2 Properties of Weakly Regular Agents: Canonical Layering, computation procedure. 8.3 Regular Agents:Unfolding. 8.4 Compile-Time Algorithms: Check\_WRAP, Check\_Regular, Reasonable-SS. 8.5 IADE: GUI. 8.6 Experimental Results: Performances of algorithms. Get Slides
Kapitel 9:	Meta Agent Programs (21. Juni, 14ct) 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 define the notion of a belief status set and discuss what the analogues of feasibility, rationality and reasonability are. Finally we show that we can implement meta agent programs by ordinary programs using extended code calls. 9.1 Extending CFIT: Szenario with beliefs. 9.2 Belief Language and Data Structures:Belief atoms, Belief Language. Belief- (Semantics-) Table, 9.3 Meta Agent Programs and Status Sets: Meta agent programs, Belief Status Sets, Sequences, Induced Status Sets, Induced States, Extended Code Calls. 9.4 Feasible Status Sets:Old Conditions + New Conditions: Local Coherence, Compatibility. 9.5 Reducing Meta Agent Programs to Ordinary Agent Programs: Definition of Trans, Equivalence wrt. semantics SEM. Get Slides