# Exam

## 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}$
		- 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, …