Exam

Introduction Agent Architectures Game Theory Communication Modelling

Introduction

agent
- physical or virtual entity, has its own resources, possibly a representation of its environment
- acts autonomously to satisfy some tendencies (goals) … proactive
- while taking into account its limited resources, perceptions etc. … reactive
agent architectures
- simple reactive agent
- agent with an internal state
- goal-based agent
- utility-based agent
  - in case of conflicting goals or uncertain effects
properties of environments
- accessibility
  - are all the relevant aspects of the environment instantly available to the agent? → we don't need to maintain an internal state
- determinism
  - is the next state completely determined by the current state and the actions selected by the agents?
- accessible + deterministic → no uncertainty
- episodic vs. sequential environment
  - do future states depend on past actions? → sequential environment
  - episodic environments are simpler, agents can make reactive decisions and do not need to remember the history (example: old chatbots)
- static vs. dynamic environment
  - dynamic environment can change during deliberation → we need to think fast (example: autonomous car)
  - semi-dynamic environment does not change during deliberation but the passage of time is important (e.g. performance score)
  - static environment does not change during deliberation, time does not matter
- discrete vs. continuous
  - discrete environment – limited number of distinct, clearly defined percepts and actions
- examples
  - chess: accessible, deterministic, sequential, static or semi-dynamic (with a clock), discrete
  - poker: inaccessible, indeterministic, sequential
  - taxi driving: inaccessible, indeterministic, sequential, dynamic, continuous
MAS applications
- distributed problem solving
- agent-based modelling and simulation

Agent Architectures

reactive agent vs. cognitive agent
- cognitive agent can reason about the environment
- reactive agent can only move randomly and perform some reactive actions
practical reasoning
- action-oriented reasoning = process of deciding what to do (not what to believe or what is true)
- human practical reasoning
  - deliberation – what state of affairs I want to achieve? (output = intentions)
  - means-end reasoning – how do I get there? (output = plans)
- philosophical foundation: Bratman's theory of practical reasoning
- intentions in practical reasoning
  - effort and resources put into achieving intention
  - no conflict: intentions serve as a filter for adopting new intentions
  - success tracking + persistance after failure
  - possible – intentions are believed to be possible
  - feasibility – not believed to never be reached
  - under some circumstances, agents believe they will reach their intention
  - agents need not intend all the expected side effects of their intentions
BDI architecture
- beliefs
  - representation of the world
  - possible incorrect and incomplete
  - but consistent/rational
- desires
  - our goal (ideal states)
- intentions
  - how to achieve the goal
  - intentions lead to actions
  - in a dynamic environment, we need to reconsider the intentions
    - constraints: resources, time (in real-time envornments)
    - two extreme strategies
      - never reconsider
      - reconsider constantly
    - strategies
      - blind commitment – only reconsider after success / total fail (all plans have failed)
      - single-minded commitment – also reconsider when intention becomes impossible
      - open-minded commitment – explicit meta-level controller that decides if intentions should be reconsidered
- BDI goal-plan diagram (tree)
  - list of all plans we can use to achieve the goal
  - each plan consists of several atomic actions
  - example: gold miners
    - goal: earn money
    - plans: sell gold | other job
    - how to sell gold: have gold & go to market & sell
    - how to have gold: steal gold | pick gold
  - on every level of the tree, we switch between AND and OR
- BDI pros & cons
  - grounded in philosophy, formal logic
  - high level of abstraction, captures folk psychology
  - explains why an agent does something
  - extensible, flexible, robust, failure recovery
  - dedicated programming frameworks (example: GAMA)
  - but complex, may be computationally slow
reflex architecture
- stimulus-action rules
- directly triggered by stimuli in the environment
- less complex than symbolic AI
- example: ants
  - go back to nest = follow pheromones the other way
- finite-state machines
- subsumption architecture
  - hierarchy of competence modules (CM)
  - each module is responsible for a concrete, clearly defined, simple task
  - all modules operate in parallel
  - rather simple rule-like structure
  - lower layers can inhibit higher layers
    - by suppressing input signals or inhibiting output signals
- example: Mars explorer (Steels)
  - highest priority: obstacle avoidance
  - drop carried samples at base
  - return to base when carrying sample
  - collect found samples
  - lowest priority: exploration
- how can reactive agent locate the base?
  - gradient field – the base emits radio signal
- how can robots communicate together?
  - we want to tell the other robots where the clusters are
  - we use “feromones” – stigmergy (indirect communication through environment)
    - robots drop radioactive crumbs
    - other robots need to pick them to make the trace “fade away”
  - https://nausikaa.net/wp-content/uploads/2022/09/steels-mars-explorer-02.html
- for reactive agents, the environment has to be accessible
hybrid architectures
- reactive and deliberative layers
  - obstacle avoidance can be reactive
- how to handle interaction between layers?
  - horizontal layers – each layer produces output, they are merged
  - vertical layers – layers pass inputs in one direction and outputs in the other
- Ferguson – TouringMachines
  - three control layers: reactive, planning, modelling

Game Theory

applications
- biology – survival of the fittest (winners)
- political sciences – military strategy, Cold War
typology of games
- zero-sum games
- cooperative vs. competitive
- simultaneous vs. sequential
- information available – complete information, incomplete information (Bayesian games), imperfect information
examples
- shifumi (rock-paper-scissors)
- chicken game
notation
- players $i,j$
- results $W=\set{w_1,\dots,w_n}$
agents maximize utility
- absolute values of utility does not convey much meaning, we are more interested in relative comparison (which action has more utility for the agent)
simplified environment model
- possible actions $Ac=\set{C,D}$ $A c = {C, D}$
  - cooperate $(C)$ , defect $(D)$
- the environment is…
  - sensitive – if each combination of actions leads to a different result
  - insensitive
  - controlled – if one player can influence the result
representation
- extensive form – decision tree
- strategic form – matrix
notions
- pure or mixed strategy
- equilibria
  - Nash equilibrium – no agent can improve his payoff by changing his own strategy
  - Bayesian equilibrium – extension of NE to incomplete information games
- dominant strategy – $s_1$ dominates $s_2$ if $s_1$ always leads to a better utility (regardles of the other players' strategies)
- Pareto optimality – outcome cannot be improved without hurting at least one player
- social vs. individual benefit
prisoners' dilemma
- happens in every situation where $T\gt R\gt P\gt S$
- $T$ … temptation (successful betrayal)
- $R$ … reward (we both cooperated)
- $P$ … punishment
- $S$ … sucker (I was betrayed)
how can we establish cooperation in multi-agent systems?
- iterated prisoners' dilemma
- Axelrod's tournament
  - winner – tit for tat
tragedy of the commons, free riders
- shared resources
- benefits are individual, costs are shared
humans are not always economically rational

Communication

Shannon's model
- source
- transmitter
- channel
- receiver
- destination
Berlo's model
- sender
- message
- channel
- receiver
types
- point to point × broadcast
- broker
- propagation in environment
message meaning
- intentional – sender intends the meaning of the message
- incident – receiver interprets (gives a meaning to the message)
7 steps
- speaker
  - intention – what information is the speaker trying to communicate
  - generation – generate the message
  - synthesis – send the message (say it…)
- hearer
  - perception – receive the signal
  - analysis – infer possible meanings
  - disambiguation – try to choose the most probable meaning
  - incorporation – decide to believe the communicated information (or not)
communication problems
- technical – message does not arrive at all
- semantic – hearer does not understand the meaning
- efficiency – message does not have the intended effect (the hearer chooses not to believe it…)
misunderstading, potential meanings
- M1 … original intention (meaning)
- M2 … meaning that the hearer infers
- M3 … what the speaker believes that the hearer inferred
speech acts theory: Austin
- locutionary act – utterance
- illocutionary act – intent
- perlocutionary act – result
Searle: categories of illocutionary acts
- assertives – commit the speaker to the truth of the proposition
- commissives – commit the speaker to a future action
- directives – cause the hearer to take an action
- declaratives – change the reality in accord with the content of the declaration
- expressives – express the speaker's attitudes/emotions
Vanderveken
- decomposition into illocutionary force (F) and propositional content (P)
  - F … general intent (inform, ask-to-do, request, answer, …)
  - P … specific content
- success and satisfaction conditions
  - success if the hearer recognizes the intention
  - satisfaction if the speaker's intention is achieved
we need to know the preconditions and the effects of each speech act
- we also need boolean conditions to see if a speech act is successful and/or satisfied
agent communication languages
- human languages are ambiguous → agents use interaction languages
- approaches
  - mentalist(ic) approach
    - based on beliefs
    - FIPA-ACL
    - some strong assumptions/hypotheses – agents are sincere and willing to cooperate
  - social approach
    - based on commitment
    - commitments are public
    - are there two contradictory commitments?
  - public approach – based on grounding
  - deontic approach – based on norms
interaction protocols
- shown on KQML
  - direct (point to point)
  - through a matchmaker
  - through a broker
  - through a feeder
- example: typical request protocol (agents are taking turns)
  - request → accept, refuse, or modify
  - accept → inform-done or inform-failure
  - modify → accept, refuse, or modify
- contract net
  - “I need help for a task”
  - 5 stages
  - bidding, contracts
- dependence based coalition (DBC), social reasoning
programming communication
- keyword-based chatbots
- logical programming
- LLMs
simulating communication
- with neighbours vs. with acquaintances

Modelling

agent-based modelling and simulation
- model – simplified abstraction of reality
- macro patterns emerge from individual decisions
7 goals of simulation (Axelrod)
- prediction – e.g. weather
- task performance – we want to mimic a human performing the task
- training – e.g. flight simulator
- entertainment – imaginary virtual world, for amusement
- education – users can learn what happens if they do this or that in the simulation
- proof – prove existence/conjecture
- discovery – discover new knowledge
social simulation
- model should be valid (faithful to reality)
how to build a model
- preparation
  - define research question
  - formulate hypothesis
  - define (input) parameters and output indicators
  - find relevant literature/insights describing the modelled behaviour
  - define rules of the system
  - formulate what is important (and what is not) – start simple
- who are the agents? what is the environment?
- simulator
  - inputs
  - outputs
  - what we show?
- implementation
  - NetLogo, GAMA
examples
- boid simulation in movies
- Game of Life
- Schelling's segregation model
- crowd simulation
- traffic simulation
- urban planning
  - Acteur project, multi-level decision-making
    - strategical – establish list of destinations and try to reach them
    - tactical – adjust plans to implement strategy
      - ordinary situation – adjust to traffic, choose best trajectory, less populated roads, …
      - extraordinary situation – escaper (flee danger), bystander, random wanderer, road runner (less congested), sheep (follow crowd), …
    - operational
  - HIANIC project
    - shared space (cars, pedestrians, bikes)
    - autonomous car navigation
  - Switch project
    - car → bike?
    - 4 mobility modes (walk, bike, bus, car)
    - 6 criteria (comfort, ecology, price, simplicity, safety, time)
      - every agent has priorities
    - decision model with habits
      - with some probability, we rationally reevaluate (if the context has changed – price of gas went up…)
      - otherwise, we stick to our habit
- evacuation modelling, crisis management
  - evacuation – zigzag stairs may be better
  - flood risk management, communication
  - epidemics
  - earthquake
    - Solace – testing the role of social attachment
  - you need realistic cognitive agents
    - take human factors into account
- not all models require the same level of realism
  - entertainment models do not have to be that much realistic
human factors
- emotions, empathy, mood, personality
- trust, moral values, ethics
- cognitive biases
- motivation, engagement
- memory, attention, distraction, tiredness, focus, stress
- social links, attachment, altruism, cohesion
- we need to simulate emotions
  - BDI logical model of emotions
  - book: The Cognitive Structure of Emotions
  - example: distress … agent believes that $\varphi$ , but desires $\neg\varphi$
- biases – confirmation bias, …