CPT302多代理人系统 个人笔记

admin管理员组

文章数量:1530845

复习建议看tutorial和最后一节复习课，然后建议买个出水流畅的笔（
markdown和pdf版本

文章目录

• Lec01 Agent and MAS （Desc）
• • 1.1. Agent
  • 1.2. Multiagent System(MAS)
  • 1.3. The Subsumption Reactive Architecture(SRA)：
  • 1.4. History of computing
• Lec02 Intelligent Agents
• • 2.1. Agent and Environments
  • 2.2. Varieties of Autonomy自治
  • 2.3. Examples of Agents
  • 2.4. Intelligent Agents
  • 2.5. Agents and Objects
  • 2.6. Agents as Intentional Systems
  • 2.7. Abstract Architectures for Agents
  • 2.8. Agents with State
  • 2.9. Tileworld瓷砖世界
• Lec 03 Deductive Reasoning Agents
• • 3.1. Agents as Theorem Provers 定理证明：
  • 3.2. Vacuum World真空世界
• Lec04 Practical Reasoning Agents
• • 4.1. Intentions and Desires
  • 4.2. Deliberation
  • 4.3. Means-End Reasoning
  • 4.4. The Blocks World
• Lec 5 Multiagent Interactions多代理交互
• • 5.1. The spheres of influence势力范围
  • 5.2. Utilities and preferences
  • • Multiagent Encounter
  • 5.3. Solution Concepts
  • • Dominant strategies主导策略
    • Pareto optimality帕累托最优
    • Nash equilibrium纳什均衡
  • 5.4. The Prisoner’s Dilemma
  • 5.5. Social Welfare
• Lec 6 Reactive and Hybrid Agents
• • 6.1. The Subsumption (Reactive) Architecture
  • 6.2. Mars Explorer
  • 6.3. Hybrid Agent
  • 6.4. TouringMachines
  • 6.5. InteRRaP
• Lec 6 Reaching Agreements
• • 6.6. Auction拍卖
  • 6.7. Issues about Action
• Lec 7 Coalitions, Voting Power, and Computational Social Choice
• • 7.1. Coalitional games联盟博弈
  • • 7.1.1. Coalition Structure Generation
    • 7.1.2. Teamwork（Solving the optimization problem ofeach coalition）
    • 7.1.3. Dividing the benefits of cooperation
  • 7.2. Formalizing Cooperative Scenarios
  • • 7.2.1. Which Coalition Should I Join
    • 7.2.2. Core
    • 7.2.3. Objections and core
    • 7.2.4. Shapley value
  • 7.3. Representing Coalitional Games
  • • 7.3.1. Induced Subgraph
    • 7.3.2. Marginal Contribution Nets（MCN）
• Lec 8 Social Choice
• • 8.1. Plurality- Single-winner voting system
  • 8.2. Sequential Majority Elections
  • 8.3. Pairwise Elections
  • 8.4. The Borda Count
  • • Pareto Condition
    • Condorcet winner condition
    • Independence of irrelevant alternatives（IIA）
    • Non-Dictatorship
  • 8.5. Arrow's Theorem
• Lec 9 Working Together
• • 9.1. benevolent agents
  • 9.2. Self-Interested Agents
  • 9.3. Two main modes of cooperative problem solving
  • 9.4. The Contract Net Protocol
  • • 9.4.1. Recognition任务识别
    • 9.4.2. Announcement广播公告
    • 9.4.3. Bidding代理人竞标
    • 9.4.4. Awarding && Expediting
  • 9.5. Issues for Implementing Contract Net
  • 9.6. Contract Net
  • • 9.6.1. Types of Messages in Contract Net
    • 9.6.2. Efficiency Modifications
• Lec 10 Agent Communication
• • 10.1. Speech Acts
  • • 10.1.1. Plan-Based Semantics
  • 10.2. KQML
  • • 10.3. KQML and KIF
  • 10.3. FIPA & ACL
  • • 10.3.1. Inform and Request

Lec01 Agent and MAS （Desc）

1.1. Agent

Agent: 是一个计算机系统，能够自治（capable of independent action）它的用户或拥有者所派发（delegate）的操作（自己能知道需要完成哪些任务来适应用户的目标，而不是直接被告知需要做什么）。为了完成任务，能够与环境持续地交互。

一个Agent architectures是一个agent的软件设计
Software architectures for decision-making systems that are embedded in an environment
sense→decide→act→sense→decide→…

1.2. Multiagent System(MAS)

Multiagent System(MAS): 多个相互之间能够交流的agent，（拥有互相copperate，coordinate and negotiate的能力）
一些传统例子是空中管制和网购系统

MAS的两个设计要点：

1. Agent design：如何建造可以自治的agent
2. Society design：如何建造可以互相interact的agent

1.3. The Subsumption Reactive Architecture(SRA)：

• 多种行为可以被同时（simultaneously）触发
• 模块被安排成一个SRA，每个模块被排列到层中
• 体系结构中较低的层可以抑制较高的层（层级越低，level0，其优先级越高）

SRA的不同行为action的选择：

1. agent从一组有抑制关系（inhibition relation）的actions中挑选并执行
2. 形如 b1 ◄ b2, 意味着“b1 inhibits b2”，也就是b1抑制b2，b1层级更低。不过通过后面的例子得知道，b1表示的是一个名为b1的事件，1不代表具体层级，抑制关系还是通过三角箭头得出的。

比如在火星上有许多探测车，目的是携带土壤样本，然后根据基地的信号强弱找到并返回基地，其SRA可描述为下图

之前的内容来自“An Introduction to MAS”，下面是Lec1的内容，重复内容不再赘述

1.4. History of computing

1. ubiquity;
2. interconnection;
3. intelligence;
4. delegation; and
5. human-orientation.

接下来就是解释这几个时期，建议自己看看

Lec02 Intelligent Agents

2.1. Agent and Environments

通常情况下agent不可能完全观测附近的实时的环境（accessibility可访问），所以失败在所难免，因此agent必须有能够应对失败的准备。
环境越可被访问，越容易构建一个基于此的agent

Accessible Environments(可访问环境信息）	Inaccessible Environments
where the agent can obtain complete, accurate, and up-to-date information about the environment’s state	moderately complex environments

Deterministic（一个行动会得到唯一的影响）	Non-deterministic
where any action has a single guaranteed effect (no uncertainty about the state resulting from an action)	the physical world can be regarded as non-deterministic,a greater challenge for agent designers

Static（环境只被agent操作影响）	dynamic
remains unchanged except the performance of actions by the agent	a dynamic environment has other processes operating on it,and it changes in ways beyond the agent’s control, the physical world is a highly dynamic environment

Discrete(环境信息的变化是离散的）	continuous
there are a fixed, nite number of actions and percepts in it, chess game	car driving

2.2. Varieties of Autonomy自治

对于人类来说：信仰，目标和行动的自由
对于软件系统：没有自由，按照人们给定目标去做（知道应该做什么

由于environment本身具有一定的不确定性，我们需要返回的不是一个固定的单一sequence of actions，而是一个处理了不确定性的Solution。—— RESULT <- Percepts模型（知乎）

Adjustable autonomy：
决策权在以下情形会由agent转移到人身上：

1. when the agent beliefs that the human will make a better decision
2. when there is a degree of uncertainty about the environment
3. when the decision may cause harm
4. when the agent lacks the capability to make the decision itself

一个agent有一系列可以影响环境的行动。行动会有对应的先决条件，定义了他们实施的情形。agent面对的主要困难是决定哪一个action可以最好地实施它的目标。

2.3. Examples of Agents

1. 控制系统Control systems
   1. 比如恒温器（thermostat），目标：维持一个确定的温度，行为：加热、不加热
   2. 复杂的系统会有更复杂的决策结构
2. 软件系统服务Software daemons
   1. 任何监控了软件环境并进行某些行动改变它的软件
   2. 比如杀毒软件

2.4. Intelligent Agents

表现出来三种类型的行为：

1. Reactivity反应性 - ability to perceive their environment分析环境, and to respond (quickly) to changes in order to satisfy their objectives
2. Pro-activeness自发行为 - ability to take the initiative 采取行动(goal-directed behavior) in order to satisfy their objectives
3. Social ability社会能力 - ability to interact with other agents 互相交互 (and possibly humans) in order to satisfy their objectives

反应性和自发行为应当有取舍，一般来说agent应该通过构建和遵循复杂的计划来实现其目标，然而，如果很明显计划没用的话，他们不应该盲目地遵循这些计划。那时agent应该能够对新情况做出反应，与此同时，agent不应该为了不放松总体目标而不断作出反应。
社交能力指通过以下行动与别的agent交互：
4. cooperation合作 ： working together as a team to achieve a shared goal
5. coordination协作 ： managing the inter-dependencies between activities
6. negotiation谈判 ： the ability to reach agreements on matters of common interest

2.5. Agents and Objects

Objects：

1. Objects encapsulate some state封装某种状态
2. Objects communicate via message passing通过消息传递进行通讯
3. Objects have methods corresponding to operations that may be performed on this state具有在每个状态上执行的操作

Agent在自治autonomy方面强于objects，尤其是agent可以决策是否执行一个action
Objects do it for free; agents do it because they want to …
Agent可以灵活的控制自己的行为，Object不可以
多代理系统本质上是多线程的，因为每个agent可以视为一个线程

2.6. Agents as Intentional Systems

Intentional System
An entity, whose behavior can be predicted by attributing belief, desires and rational acumen一个实体，其行为可以通过归因于信仰、欲望和理性敏锐性来预测

例子，当描述人类行为：“Jane took her umbrella because she believed it was raining and she wanted to stay dry.” 其中包含了believing，wanting，hoping，fearing

当然，如果能够一个更规范化的语句来描述就好了
Agents (as intentional systems) represent a further and more powerful abstraction to describe, explain and predict the behavior of complex systems

2.7. Abstract Architectures for Agents

符号	解释	表示
E	环境状态E，离散值	E={e,e’,…}
Ac	agent的可能的操作（Agent actions），能够改变环境的状态	Ac={a,a’,…}
r	一个run表示一个agent根据环境状态进行的操作的序列
R	表示所有可能的由E和Ac构成的有穷（finite）序列
-	表示R中末尾是action的序列的集合	RAC
-	表示R中末尾是环境变量的序列的集合	RE
τ	state transformer表示behavior of the environment。如果 τ ® = ∅，则run has ended，没有可能的r能到达的successor state
Env	环境由一个三元组表示，其中，E是一系列环境状态，e0∈E是初始态，τ是状态转换函数（state transformer function）	<E, e0, τ>
Ag	Agent是一个将runs映射到actions的函数，Ag: RE → Ac，Agent根据系统之前记录的历史信息决定执行某个特定的action。AG表示所有agents。	Ag: RE → Ac
-	Purely Reactive Agents，不根据历史信息选择action，只根据现状选择，例子：恒温器	Ag: E→Ac
R(Ag, Env)	一个System包含一个agent和一个环境，任何系统都有一系列可能的runs，我们将代理人Ag在环境Env里的runs集合表示为 R(Ag, Env)。让R(Ag, Env)仅包含已经结束的runs（终止或有穷运行）

环境的类型：

1. history dependent：当前状态由更早之前的actions确定
2. non-deterministic：执行action的结果充满不确定性

正式来说，一个序列（sequence）：
（e0,a0,e1,a1,e2,…）
表示一个代理人Ag在环境Env=<E,e0,τ>的一个run(行动序列），其中e0是环境的初始态，a0=Ag（e0）为某个代理人行为
for u>0, eu∈τ（e0,a0,e1,a1,e2,…）and au=Ag(e0,a0,…,eu)

2.8. Agents with State

为了构建真实的agents，抽象模型需要被分解为若干子系统——data and control structures。
These subsystems constitute an agent architecture
一些代理人能够记录环境的历史信息

解释	表示
观测方法see：表示代理人观测所处环境中的信息，并把它转换成合适的input	see：E → Per
next方法将内部state结合input映射到一个新的state	next: I ✖ Per → I
action-selection，动作选择方法	action：I → Ac

Agent Control Loop：

1. Agent从初始态i0开始
2. 观测环境状态，生产percept see（e）
3. 通过next函数更新内部状态，i1=next(i0,see(e))
4. 选择合适的action，action(i1)
5. 进行action
6. 回到步骤2

Task for Agents代理人的任务：

为了让代理人知道最终目标是什么，并能自己知道如何去实现，我们需要列出tasks

1. 一个可行的方法是给每个state设立一个效用值（utility），然后让代理人将utility最大（效用最大化）。一个task specification简单表示为一个函数：u: E → R
   在某些特定环境下，可以定义一个agent的整体的效用为以下几种：
   • pessimistic approach：一个run过后最差的状态的utility
   • optimistic approach：一个run过后最好的状态的utility
   • 一个run之后的states的效用值之和
   • 一个run之和的states的效用值的平均数
     缺点：给每步后的state设定效用值，很难提供一个长远的视角，不知道几步之后大概效用值是多少，可能这步确实是走的局部最优，但是这步之后没法达到全局最优。
2. 或者给每个run设定一个有效值。表示为u: （花体R） → （粗体R）
   （这符号也太难打了）。这样就可以提供一个long term view

2.9. Tileworld瓷砖世界

1. 模拟的二维网格环境，上面有agent代理人、瓷砖tiles、障碍物obstacles和洞holes。
2. 代理人可以往四个方向移动，如果它位于瓦片旁边则可以推动瓦片。
3. 代理人必须将所有洞用瓷砖填满——代理人通过用瓷砖填充洞来得分，目标是填充尽可能多的洞（作为utility）。
4. 瓷砖世界的洞会随机出现和消失

将代理人放于Tileworld中，运行若干步数之后通过计算代理人填充的洞的数量来衡量代理人的表现performance。

u ( r ) = n u m b e r   o f   h o l e s   f i l l e d   i n   r n u m b e r   o f   h o l e s   t h a t   a p p e r e d   i n   r u(r)=\frac{number\ of\ holes\ filled\ in\ r}{number\ of\ holes\ that\ appered\ in\ r} u(r)=number of holes that appered in rnumber of holes filled in r​

Lec 03 Deductive Reasoning Agents

Agent architecture is a software design for an agent
主要步骤为：perception-state-decision-action
通常代理人架构定义了：

1. 关键数据结构
2. 数据结构上的操作
3. 操作之间的操作流

构建AI系统的传统方式：

1. 环境和行为的符号表示（Symbolic representation，logical formulae逻辑公式）
2. 符号表示的句法操作（Syntactic manipulation，logical deduction逻辑推导）

通常面临以下难题：

1. Transduction Problem：如何将真实世界转换成正确的符号形描述，并使那些描述有用。
2. Representation/Reasoning Problem：如何符号化表示有关复杂现实世界的实体和过程的信息，以及如何让agent及时利用这些信息进行推理，使结果变得有用

3.1. Agents as Theorem Provers 定理证明：

Theory of agency φ：解释了agent如何表现以优化性能度量，被视为可执行的用于生成agent行为的规范

Deleberated agents：简单的基于逻辑的代理人

• 内部状态设为包含公式的数据库（predicate logic，谓词逻辑-知乎，谓语接对象，例如tank776的水压是28 = Pressure(tank776,28)）
• 可能会包含过时的outdated，或无效的invalid信息

假设L为经典一阶逻辑（first-order logic）的公式的集合
假设D=2L是L的所有子集
假设ρ是deduction rules推导规则，模拟agent的决策过程
DB ⊢ \vdash ⊢ ρ φ 意味着公式φ可以从数据库DB中唯一使用推导p证明。

由2.8中提到的Action Selection举例Theorem Proving：

3.2. Vacuum World真空世界

（感觉这个真空世界-（vacuum world）知乎有点类似瓷砖世界)

1. 一个小机器代理人被放置在网格状房间中
2. Agent装备有灰尘检测器和吸尘器
3. Agent能够辨认东南西北
4. Agent能够转弯或前进
5. 假设房间3x3，agent初始时面向北

符号表示：

1. 可能的环境感知percepts：
   Per=｛dirt, null｝
2. 谓语辖域（domain predicated）用于描述agent内部状态
   In（x, y） - agent 处于（x，y）
   Dirt（x，y） - （x，y）处有灰尘
   Facing（d）- agent面朝d方向
3. 可能的动作
   Act=｛forward，suck，turn｝

Deduction rules推导规则（就是如果检测到怎么样接下来干什么）：
In (x, y ) ∧ Dirt (x, y ) → Do (suck)
In (0, 0) ∧ Facing (north) ∧ ¬Dirt (0, 0) → Do (forward )
In (0, 1) ∧ Facing (north) ∧ ¬Dirt (0, 1) → Do (forward )
In (0, 2) ∧ Facing (north) ∧ ¬Dirt (0, 2) → Do (turn)
In (0, 2) ∧ Facing (east) ∧ ¬Dirt (0, 2) → Do (forward )
…

可能面临的难题：

1. 如何把摄像头数据变成｛dirt，null｝这样的表示，如何表示周遭环境
2. 决策的决定假设了一个静止的环境（见#2.1，环境只被agent影响），这里提到了计算合理性（calculative rationality）：
   • 决策就是根据传感器的数据找到那个情景下的最优决策，然而从传感器输入到进行决策的时候，agent所处环境可能继续变化
   • 如果决策的发生是即时的，则可以忽略此问题
3. 通过theorem proving进行决策制定是复杂的，有可能不会停止。

假如一个两个格子的方格世界，那么它有以下8种可能的状态。

然后例子给出这个Vacuum World里的状态转换

Lec04 Practical Reasoning Agents

Practical Reasoning：the process of figuring out what to do
Practical reasoning（directed towards actions） 与 theoretical reasoning（directed towards beliefs）不同

Practical Reasoning = Deliberation + Means-Ends Reasoning

• Deliberation： deciding what state of affairs we want to achieve 想要做到什么
  the outputs of deliberation are intentions
• Means-ends reasoning： deciding how to achieve these states of affairs 如何实现
  the outputs of means-ends reasoning are plans

Computations and Resource Bounds：
由于agent的存储容量和运行内存有限，资源的限制和在实际环境中的响应时间的限制促使了agent的计算量的限制。以上可能会导致：

1. Agent必须高效控制reasoning，来获得一个好的表现
2. Agent不能无休止地考虑，即使那样会导致decided state不是最优了

4.1. Intentions and Desires

在influencing actions中，intentions（决定做某事）强于desires（打算做某事）

1. Intentions drive means-ends reasoning（intension 促进生成目标→手段链）
   如果有了Intention，则下一步就是打算实现achieve它，包括决定如何实现它。如果一种action失败了，那么就尝试其他的操作
2. Intentions persist坚持
   如果没有充分理由，不会轻易放弃intention。Intention会一直存在，直到实现了它们/认为它们无法被实现/认为reason for intention不再存在。
3. Intentions constraint further deliberation制约其他讨论
   不会考虑与现在intention不契合的option——Filter of admissibility
4. Intentions influence beliefs upon which practical reasoning is based
   If I adopt an intention, then I believe I will achieve the intention. However, I must also recognize the possibility that I can fail to bring the intention about

4.2. Deliberation

Agent需要维护符号化表示

符号	意义
B	a variable for current beliefs
Bel	the set of all such beliefs
D	a variable for current desires
Des	the set of all desires
I	a variable for current intentions
Int	the set of all intentions

Deliberation通过两个函数建模表示

1. an option generation function
   options：2Bel x 2Int → 2Des
2. a filtering function
   filter: 2Bel x 2Des x 2Int → 2Int

一个agent的belief update process 通过belief revision function 建模：
brf：2Bel x Per → 2Bel

4.3. Means-End Reasoning

意味着如何achieve一个intention的终结（end），using the available means
Means-End reasoning is better known as planning, planning本质上是automatic programming

Planner：
一个系统，接受如下类型的输入，然后输出一个plan/course of actions/recipe

1. a goal, intention or task
2. the current state of the environment - the agent’s beliefs
3. the actions available to the agent

STRIPS:
第一个planner，包含两个基本组件：

• set of formulas of first-order logic(planner所处世界的模型）
• 描述所有actions的前提（preconditions）和影响（effects）的action schemata

planning algorithm寻找一个当前世界的状态和目标状态的差别，并试图通过一个合适的action来减小这种差别

4.4. The Blocks World

一个机械臂，三个相同大小的小方块，一个平面

Predicate	Meaning
On(x,y)	object x on top of object y
OnTable (x)	object x on the table
Clear (x)	nothing is on the top of object x
Holding (x)	robot arm is holding x
ArmEmpty	robot arm is empty (not holding anything)

上图所示状态：
{Clear(A), On(A,B), OnTable(B), OnTable©, Clear©}∪{ArmEmpty}
A goal to achieve(intention):
{OnTable(A), OnTable(B), OnTable©}

一个Action操作包含

1. name，可能会有参数输入
2. precondition list，前置条件，为真时该操作才能实行
3. delete list，该操作过后，不再为真的条件
4. add list，该操作过后，变为真的条件

Blocks World里的操作们：

1. Stack(x,y)，机械臂把抓取的物体x放置在物体y上
   pre {Clear(y), Holding(x)}
   del {Clear(y), Holding(x)}
   add {ArmEmpty, On(x,y)}
2. UnStack(x,y)，机械臂从物体y上抓取物体x
   pre {On(x,y),Clear(x),ArmEmpty}
   del {On(x,y), ArmEmpty}
   add {Holding(x), Clear(y)}
3. Pickup(x), 机械臂从桌面上抓取物体x
   pre {Clear(x), OnTable(x), ArmEmpty}
   del {onTable(x), ArmEmpty}
   add {Holding(x)}
4. PutDOwn(x), 机械臂把物体x放到桌面上
   pre {Holding(x)}
   del {Holding(x)}
   add {ArmEmpty, OnTable(x)}

Practical Reasoning Agent的基本控制结构是个循环：

1. 观察世界，update beliefs
2. 斟酌去实现哪个intention（先找到所有opitions然后filter出来合适的）
3. 使用means-end reasoning找到一个实现这些intention的计划
4. 实施plan

如何实现一个Practical Reasoning Agent：
Let π be a plan, and Plans be the set of all plans (over some set of actions Ac). Then

• pre (π) is the precondition of π, and body (π) is the body of π
• empty (π) is a Boolean function that indicates whether π is empty or not
• execute (π) is a procedure that executes π without stopping(i.e., executes each action in the plan body in turn)
• hd (π) is the plan made up by the rst action in the body of π
• tail (π) is the plan made up by all but the rst action in the body of π
• correct(π,I,B) is a Boolean function that indicates whether π is a correct plan for intentions I given beliefs B

Commitments to Ends and Means:，对于End和Means的承诺：
当一个option（desire）成功通过过滤并被代理人选择时，代理人就已经做出了承诺Commitment。
承诺意味着时间上的持久性，一个意图（intention）一旦被采纳，就不应该立即消失。
那么，应该维持多久的intention，或者在什么情况下清除（vanish）intention——Commitment strategy

Commitment strategy：

1. Blind commitment（fanatical commitment）：一个盲目承诺的代理人将持续保持一个意图intention，直到它相信这个意图已经实现。
2. SIngle-minded commitment：专一的代理人将继续保持一个意图，直到它相信该意图已经实现，或者不再可能实现
3. Open-minded commitment：一个思想开放的代理人将保持一个意图，只要该意图仍然被认为是可能的。

Intention Reconsideration：何时agent停止重新考虑它的intention

1. An agent that does not stop to reconsider sufficiently通常会继续试图实现其意图，即使很明显该意图无法实现或不再有任何理由去实现。
2. An agent that constantly reconsiders its intentions可能会花费不太充分的（insufficient）时间来实现这些意图，因此有可能永远无法真正实现这些意图

Lec 5 Multiagent Interactions多代理交互

5.1. The spheres of influence势力范围

一个多代理系统包含多个代理，他们：

1. 互相通过交流进行交互
2. 可以在环境中行动
3. 有不同的势力范围，可能互相重合coincide
4. 由其他的关系链接

5.2. Utilities and preferences

Self-interected agents:
每个代理对世界状态都有自己的偏好preference和欲望desires（非合作博弈论non-cooperative game theory）

Modelling preferences：

效用utility直接导致了对outcomes的偏好（preference），从而排出先后顺序

Multiagent Encounter

Interaction as a game:
世界的状态可以被视为游戏的结果

• 假设我们有两个代理 Ag={i,j}
• Ω的最终结果取决于两个代理的选择的综合结果

State transformer function:

Normal-form game (or strategic-form game):
A strategic interaction is familiarly and generally represented in as a tuple (N, A, u), where:

1. N is the set of player
2. A = A1 × A2 × A3 × … × An where Ai is the set of actions available to player i
3. U=(u1, u2, …, un) utility functions of each player

Payoff matrix:
n次方矩阵，单元格中包含每个玩家的效用函数值。(这个大写J应该是小写j

Rational agent’s strategy:

• 给定一个游戏场景，一个rational agent（理智的代理人）将会如何act？

从单个代理的视角来看，它只需要最大化outcome就可以（局部最优）。但当运用到多代理里面(下面讨论），最优选择往往取决于其他人的选择，这样就不能只管自己怎么选最好了

Solution Concepts:三种解决方案
– Dominant strategies
– Pareto optimality
– Nash equilibrium

5.3. Solution Concepts

https://zhuanlan.zhihu/p/467498583

Best response: 给定玩家j的决策sj，那么玩家i的最佳决策是使玩家i的payoff最大

由上图举例：

1. j plays C —> i’s best response =D
2. j plays D —> i’s best response =C

Dominant strategies主导策略

无论代理人i选择什么样的策略，j在使用sj*\时的表现至少与使用其他策略时的表现一样好，那么该策略对j来说就是主导的。 (如果sj* 是对代理人j的所有策略的最佳回应，那么它就是主导策略）。
"我的所有选择之中，那一个肯定能让属于我的的效益变大的选择“

比如：

1. D是j的主导策略。无论i选什么，j选D都不至于让事态变坏
2. 对于i来说，没有主导策略

Pareto optimality帕累托最优

如果没有其他的结果能使一个代理人的处境更好而又不使另一个代理人的处境更差，那么这个游戏的结果就被称为帕累托最优（或帕累托有效）Pareto optimal (or Pareto efficient) 。
If an outcome w is not Pareto optimal, then there is another outcome w’ that makes everyone as happy, if not happier, than w. “Reasonable” agents would agree to move to w’ in this case. (Even if I don’t directly benefit from w’, you can benefit without me suffering.)
”对于帕累托最优的游戏选择来说，在游戏的其他选择中，不会有让每个人都更幸福或不变的选择“

比如：

1. (C, C), (D, C) 和 (C, D)都是Pareto optimal，不存在更好的的不会损害某人利益又能提高总体收益的选择

Nash equilibrium纳什均衡

对于i和j而言，纳什均衡状态表述为：
假定i选择s1，j的局部最优选择是s2 和 假定j选择s2，i的局部最优选择是s1
两个代理人都没有偏离纳什均衡的动机，纳什均衡代表了自利self-interested的代理人的理性选择结果
“互锁。对于一个纳什均衡游戏选择，假定以对方选择达到这个纳什均衡为前提，己方的局部最优选择也是达到该纳什均衡”

并不是每个交互场景都有纳什均衡。一些交互场景有不止一个纳什均衡。

比如：一对夫妻去看电影，wife喜欢A电影，husband喜欢B电影，但是他们又要一起看电影

如何找到pure-strategy Nash equilibria，找到第一个数字是所在列最大，且第二个数字是所在行最大的格子，如(2,1)和(1,2)。
以（2，1）为例：

1. wife的视角：如果husband看电影A，那么我看A电影是最赚的
2. husband视角：如果wife看电影A，那么我看A电影是最赚的

以（1，2）为例：

4. wife的视角：如果husband看电影B，那么我看B电影是最赚的
5. husband视角：如果wife看电影B，那么我看B电影是最赚的

5.4. The Prisoner’s Dilemma

https://zhuanlan.zhihu/p/192852869
纳什均衡的具体例子，每个人把刑期往最小化作为优化方向

5.5. Social Welfare

Outcome ω 的 social welfare 是每个代理从 ω 获得的 utilities 之和： ∑ i ∈ A g u i ( ω ) \sum_{i \in A g} u_{i}(\omega) i∈Ag∑​ui​(ω) 可以把它想象成"系统中的货币总量"。

Social welfare 将所有 agent 看作整体来考虑得失。

Lec 6 Reactive and Hybrid Agents

6.1. The Subsumption (Reactive) Architecture

Problems with symbolic/logica approaches (transduction, computational complexity)导致了反应范式（Reactive Architecture）的出现。就是符号化表达太复杂了所以不使用符号化表达（比如之前lec的Tile World和Block World里就是使用符号化的方法）来完成智能行为

Reactive agent architecture基于以下思想：

1. Intelligent behavior can be generated without explicit representations 智能行为可以脱离显式表达而产生
2. Intelligent behavior can be generated without explicit abstract reasoning 智能行为可以脱离显式抽象推理而产生
3. Intelligence is an emergent property of certain complex systems 智能是复杂系统的特性

Reactive agent architecture有以下特征：

1. 一个agent的决策 是由 一系列 任务完成情况的行为（task-accomplishing behaviors）来决定的
   1. 每个behavior都可以视为独立的选择函数，这些选择函数不断地把输入映射成要做的行动
   2. Behavior modules（行为模块）由有限状态机（finite-state machines/rules）实现，不包含复杂的符号化表示（situation->action rules，之前lecture提到的推理）
2. 多个behavior可以同时触发
   1. 模块module被安排成一个subsumption hierarchy，其行为behavior被安排成layer
   2. 底层的layer可以抑制高层的layer，底层代表高优先级

sensor input：原始的传感器输入，未经处理或转换为符号。
action select：行动选择是通过一组behavior以及他们的抑制关系（inhibition）来实现的
inihibition：We write b1 ≺ b2, and read this as b1 inhibits b2 - b1 is lower in the hierarchy than b2, and will hence get priority over b2. b1比b2低，b1抑制b2

6.2. Mars Explorer

以Mars Explorer举例，目标是从不知道地图的火星上用机器人们采集一块岩石标本到mother ship上。

Mechanisms一些机制：母舰会发生无线电信号，代理人可以往信号增强的方向行进找到母舰

每个agent的behavior如下：

一些limitation：
1 如果代理人不采用他们所处的大环境的模型，那么他们必须在其本地环境中获得足够的信息，以确定可接受的行动 2 很难看到决策如何考虑到非本地信息的（“short term” view） 3 个人行为、环境和整体行为之间的关系无法理解。4 由于不同行为之间相互作用的动态性和复杂性，建立包含许多层次（>10）的代理是困难的。

6.3. Hybrid Agent

现在两种系统都有优劣，一个明显的方法是，从两个（或更多）子系统中建立一个代理。

• 一个是deliberative one（之前的lec），包含一个符号化的世界模型，它以符号化方式提出计划和做出决定；
• 一个是reactive one（本节lec），它能够对事件做出反应，而无需复杂的推理。

这些子系统被排列为layered architectures（Subsystems are arranged into hierarchy of interacting layers），分为以下两种：

1. Horizontal layering水平横向连结：每层都直接连接到输入和输出
2. Vertical layering纵向连结：输入和输出最多连结到一层

Mediator function：调解人功能，横向链接时layer之间没有interaction，那就最后收集他们的输出再考虑

6.4. TouringMachines

一种架构，由三个horizontal activity-producing layer组成，每层都会不断生成代理应该执行何种action的建议

1. Modeling layer
   代表真实世界里的各种实体（包括代理本身），预测并规划目标来解决代理之间的冲突，这些计划被下发到Planning layer
2. Planning layer
   实现代理的主动行为（day to day running of the agent)，利用骨架库(schemas,hierarchically structured plans)来构建计划。在运行时详细阐述以决定施行何种计划。
3. Reactive layer
   提供对环境中发生的变化的即时响应，实现方式是一组situation-action rules，类似subsumption结构（#6.1）
4. Control subsystem
   决定上面三个layer究竟由哪一个layer来控制agent，控制系统本身是一些列的control rules，这些rules要么抑制传感器信息（在传入每层之前），要么检查控制层Control layer的输出（在每层之后）。

6.5. InteRRaP

一种架构，由三个vertical layer组成：

1. cooperative planning layer：处理社会交流
2. local planning layer：处理everyday planning，为了实现代理人的目标
3. behavior-based layer：处理reactive behavior

每层都有各自的knowledge base，各自符合该层的世界的表示，从传感器的原始信息到复杂的model

纵向链接时每层会有interaction，当传感器输入到达最低层时，基本的控制就开始了，而控制可能会到更高的层，然后再回来：

1. Bottom-up activation：a lower layer passes control to a higher layer because it is not competent to deal with the current situation 低层无法处理现状，交给高层处理
2. Top-down execution：a higher layer makes use of the facilities provided by a lower layer to achieve it goals 高层使用低层提供的信息来完成目标

Lec 6 Reaching Agreements

6.6. Auction拍卖

method for allocating scarce resources in a society given preferences of agents，以下几种

1. English (first-price open-cry ascending)
   -每个出价人自由提高他的出价（公开场合），如果没有出价人愿意再提高他的出价，拍卖就会结束 - 相关拍卖中的公开出价过程，可能值得反投机 - 在相关价值拍卖中，拍卖者通常以恒定/适当的速度提高价格，也使用保留价格 - 私人价值EA中的主导策略：出价比当前最高出价高少量，直到达到自己的估值
   优点：- 真实出价是理性和稳定的 - 拍卖师不能说谎（整个过程是公开的）- 激励出价
   缺点：- 可能需要很长时间才能结束 - 泄露信息 - 使用最低价格提价是可能的，以推动价格 - 竞标者合谋
2. Dutch (reverse) auction
   卖方从高价开始，不断压低价格，直到其中一个竞标者接受该价格
3. first-price sealed bid
   竞标者提交竞标，只有拍卖师可以看到，出价最高者获胜（只有一轮竞标），这个和Dutch在战略上等同，竞标时无公开信息，高价者得
   优点：- 高效，不会泄露信息，投标人很难合谋collusion
   缺点：- 无主导策略 - 通常会按低于自己的估价出价 - 拍卖师可能会撒谎（拍卖过程不公开）- 下面Vickrey是解决以上问题的一次尝试 - 投标人合谋
4. Vickrey auction (second-price sealed bid)
   出价最高者获胜，但是支付第二高出价的价格
   优点：- 真实出价是主导策略 - 没有反投机的动机 - 计算效率
   缺点：- 投标人串通 - 撒谎的拍卖师

6.7. Issues about Action

主要是撒谎lying和合谋collusion的问题

Cheating in English auction：
在英语拍卖中作弊的目的是诱使竞标者达到他们的最高估值

• 在多次竞标的情况下，作弊者采用多个（假的）身份提交许多出价
• 其中一些出价高于其个人对产品的估值

Cheating in Sealed-bid Auctions密闭式拍卖：
密封竞价拍卖中的两种作弊形式：

• 出价人在第一价格的拍卖中作弊，在提交自己的出价前检查竞争者的出价
• 卖方在拍卖结束前检查第二价格拍卖的出价，然后提交虚假出价，以增加中标人的付款额

Bidder collusion in Dutch Auction：
竞标者可以协商他们的出价，使价格保持人为的低位

Lec 7 Coalitions, Voting Power, and Computational Social Choice

7.1. Coalitional games联盟博弈

Coalitional games model scenarios where agents can benefit by cooperating联盟博弈中代理可以通过合作从而受益

三个issues：

7.1.1. Coalition Structure Generation
7.1.2. Teamwork
7.1.3. Dividing the benefits of cooperation

7.1.1. Coalition Structure Generation

决定哪些代理将合作——决定每个代理应该加入哪个联盟
结果：将代理划分为不相交的联盟coalitions
整体的分区叫作联盟结构coalition structure

见7.2.1. Which coalition should I Join？

7.1.2. Teamwork（Solving the optimization problem ofeach coalition）

决定如何一起工作 ——解决联盟的 “联合问题”
寻找如何使联盟本身的效用最大化。
通常涉及联合规划joint planning等。

7.1.3. Dividing the benefits of cooperation

决定收益的划分。
联盟成员不能忽视彼此的偏好，因为成员可能会背叛（比如#5.3里的纳什均衡）：如果回报过低，代理人可以退出
需要考虑分配的公平性等问题
见7.2.2. Core

7.2. Formalizing Cooperative Scenarios

一个联盟博弈游戏<Ag, v>中：

• Ag={1,…,n}代表代理人们
• v=2Ag->代表游戏的特征函数characteristic function
• 如果v( C )=k，那么联盟C可以获取到效用值大小为k的效用，并在联盟中分配效用（分蛋糕(°ー°〃)）

7.2.1. Which Coalition Should I Join

Is a coalition stable?联盟是否稳定
联盟的成员留在联盟里是否够理性rational，或者他们是否能通过损害联盟利益从而自己得利
组成联盟需要双方代理有足够的意向
稳定是联盟形成的必要条件，但不是充分条件

7.2.2. Core

联盟博弈的 core 是向联盟成员分配一组可行的报酬分配feasible distributions of payoff，任何子联盟都不能合理地反对这些收益。

联盟博弈游戏中一个联盟C的回报效用outcome是一个向量表示的成员分配，用< x1, …, xk>表示。
v ( C ) ≥ ∑ i ∈ C x i v(C)\ge\sum_{i\in C}x_i v(C)≥∑i∈C​xi​

例子：

7.2.3. Objections and core

对于联盟C，往往会趋向于选择让所有成员都有更好的outcome的选择，”分的蛋糕越大越好“。
形式上来说， C ⊆ A g C \subseteq Ag C⊆Ag 反对一个outcome < x1, …, xk> 如果存在一个更好的 outcome < x’1, …, x‘k>，使得 x i ′ > x i   f o r   a l l   i ∈ C x'_i>x_i\ for\ all\ i\in C xi′​>xi​ for all i∈C。”如果能有一种分法，使每个人蛋糕或增加或不变，则趋向于那种分法“

如果有成员发对某个outcome，则该outcome就不会发生。”如果我单干能拿到的蛋糕比在集体里面拿到的蛋糕多，那我不如单干“

The core is the set of outcomes for the grand coalition to which no coalition objects
Core就是一系列outcome的集合，如果core 非空 ，则大联盟则 稳定 stable，无人可通过叛变defection从而获得更多利益（这里叛变可以理解为分裂，单干）

例子：
两个代理Ag ={1,2}, ν({1}) = 5, ν({2}) = 5, ν({1, 2}) = 20
那么outcome < 20, 0 > 就不在核心中，因为代理2单干都能拿5.（coalition {2} can object)
outcome < 15，5>在core中，此时尽管代理2没多赚，但他也没比出来单干亏，都是5。
同理 outcome< 2, 18>不在core中，因为损害了代理1的利益（coalition {1} can object)

7.2.4. Shapley value

How To Share Benefits of Cooperation：
Shapley value（夏普利值） 是定义如何公平分配合作利益的最著名尝试。它通过考虑每个代理的贡献来做到公平，其中每个代理人i的夏普利值是i为联盟贡献的平均值，符合以下三点

1. symmetry对称：a=b, S(a)=S(b)
2. dummy player无效代理，无贡献则夏普利值为0
3. additivity可加：S(a+b)=S(a)+S(b)

让δi(S)表示i加入 S ⊆ A g S\subseteq Ag S⊆Ag后的效益增量，被称为为marginal contribution边际贡献 of i to S：

那么i的夏普利值为：

其中R是Ag的所有排序的集合，Si®是排序r中在i之前的代理的集合，夏普利值方法加入了顺序的概念，并以此来判断关键加入者，和他的边际贡献。

直接看例子：

S	v(S)
( )	0
(1)	1
(2)	3
(1,2)	6

所有排序的集合R={[1,2],[2,1]},r分别等于[1,2]和[2,1]
对1而言，r=[1,2]时，边际贡献=v{1}-v{ }, r=[2，1]时，边际贡献=v{1，2}-v{2}
所以分子项为1-0 + 6-3
这里注意如果是三个人的话，则应该讨论{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}这几种排序，分母为6

继续例子：

7.3. Representing Coalitional Games

对于代理来说，确定联盟的core是否非空十分重要，然而联盟博弈的计算随着Ag的大小呈指数上升。
解决方法：

1. 尝试找到一个在大多数情况下简明的完整complete表示-7.3.1. Induced Subgraph
2. 尝试找到一个一定简明但不完整的表示-7.3.2. Marginal Contribution Nets

一种常见的方法：在组合结构 combinatorial structure上解释characteristic function

7.3.1. Induced Subgraph

v表示为基于Ag的无向图，其中i和j两个点之间的权重为wi，j，则联盟C的值为C中的各个节点组成的子图中各个边的权重和

7.3.2. Marginal Contribution Nets（MCN）

把characteristic function 表示为规则：pattern → value。

pattern 是agents的结合，如果联盟C是 pattern 中的agents的父集（superset），则规则对这一组代理 C适用。
联盟C的值是所有适用于该联盟的规则的值相加。
如下图对于联盟{a}，没有适用的rule
对于联盟{b}，第二行那个b->2适用，所以总和为2
对于联盟{a,b}，这两行规则都适用，所以总和为5+2=7

我们还可以允许在规则中存在否定 (代表代理不存在，见例子2)。
例子1：

例子2：

Lec 8 Social Choice

刚才讨论的是游戏的结果直接取决于每个代理人的选择。通常会有一种推导集体决策的机制，那么在给定个人选择的情况下，哪些规则适合确定联合决策？

Social Choice Theory is concerned with group decision making (basically analysis of mechanisms for voting)
社会选择理论适用于群体决策，多数用于投票

基本设定：

1. 代理人的偏好preference优先于结果outcome的实际效益
2. 代理人投票以产生想要的结果

符号表达：

1. Ag={1, …, n} voters (有限，奇数）
2. Ω={w1，w2，…} 可能的最终结果或者投票选出的候选人candidates
3. ϖ i ∈ Π ( Ω ) \varpi_i \in \Pi(\Omega) ϖi​∈Π(Ω)，对于代理人i而言的投票偏好

Preference Aggregation偏好聚合：
如何将每个代理人潜在的不同的偏好顺序结合起来，形成一个群组决策

Voting Procedures投票顺序：

最终目的：
推导出全局可接受的投票偏好，或者推导出赢家

8.1. Plurality- Single-winner voting system

每个投票者有一种投票的偏好顺序，持有最多头席票的候选人获胜
例：9个投票者，3个候选人

结果：c胜出
优点：简单实现，易于理解
问题： Tactical voting(voters are pressured to vote投票压力)and tie vote平局

Condorcet’s Paradox
outcome结果：Ω = {ω1, ω2, ω3}
Voters：
1. w1>1 w2 >1 w3
2. w3>2 w1 >2 w2
3. w2>3 w3 >3 w1

如果按照Plurality- Single-winner来投，则三个候选人头席票都是1，平局

Condorcet’s Paradox孔多塞悖论：在有些情况下，无论我们选择哪种结果，大多数选民都会对所选择的结果感到不满意。

8.2. Sequential Majority Elections

多步骤投票，候选人面临多个pairwise elections成对选举（二进一）
Election agenda选举议程可以被可视化为二分投票树binary voting tree

两两对决中怎么判断谁赢了：

假设三种票：

1. A>B>C 40%
2. B>C>A 35%
3. A>C>B 25%	
然后B和C对决的时候只看B,C

1. B>C 40%
2. B>C 35%
3. C>B 25%	
统计下来B赢了75%的票，C赢了有25%的票，所以B赢了

问题：最终投票的结果取决于选举议程，强强对决会提前把强队刷掉、

8.3. Pairwise Elections

Majority Graphs：有向图，用来形象描述成对选举
如果a的投票排名高于b，则存在一条从a到b的边

Condorcet Winners：
将会击败所有其他候选人的候选人，只有出箭头，没有入箭头，下图w1是赢家

8.4. The Borda Count

每个投票人的投票偏好按照排名计算积分，在偏好榜单靠前的位置会加更多的积分，榜单第一位获得m-1分，最后一位不得分
然后将每个候选人得到的分数累加，分数最高的人获胜

一些向往的良好的desirable属性：

Pareto Condition

每个投票者都将候选人wi排在wj前面，那么就称 w i ≻ ∗ w j w_i \succ^* w_j wi​≻∗wj​
适用于plurality和Borda

Condorcet winner condition

最终结果将会击败任意其他结果
适用于sequential

Independence of irrelevant alternatives（IIA）

wi和wj这两种结果的社会（全局）排名仅会唯一依赖于相应的偏好排名
上面三种都不适用

Non-Dictatorship

没有一个投票者能够系统地将他的偏好强加给其他人

8.5. Arrow’s Theorem

社会选择理论的总体愿景：确定 "好的"社会选择程序

• 不幸的是，一个基本的理论结果阻碍了它
• Arrow’s Theorem阿罗定理：
  • 对于有两种以上结果的选举，唯一满足 帕累托条件(##5.3.) 和 IIA 的投票程序是dictatorships
• 令人失望的是，基本上我们永远无法在没有dictatorships的情况下实现以上良好属性的组合

Lec 9 Working Together

代理人为何以及如何一起工作？
需要对以下两种代理人做出区分：

1. benevolent agents
2. self-interested agents

9.1. benevolent agents

如果我们 "拥有 "整个系统，我们可以设计要求代理在任意时刻都能够互相帮助
在这种情况下，我们可以假设代理是仁慈的benevolent：

• 我们的最佳利益就是他们的最佳利益
  仁慈系统benevolent systems中的问题解决方案是合作分布式问题解决（cooperative distributed problem solving，CDPS）
  仁慈极大地简化了系统的设计

9.2. Self-Interested Agents

如果代理人代表每个个人或组织，（更普遍的情况），那么我们就不能做出仁慈的假设
自利的代理人将被认为是为了促进自己的利益，可能会牺牲他人的利益，可能会发生冲突
使设系统计任务非常复杂

9.3. Two main modes of cooperative problem solving

1. task sharing:
   components of a task are distributed to component agents，部分任务被分发给部分代理人
2. result sharing:
   information (partial results, etc.) is distributed，如部分结果/信息被分发给部分代理人

9.4. The Contract Net Protocol

一种用于任务分配的众所周知的任务共享协议，分为五个阶段

9.4.1. Recognition任务识别

在这个阶段，代理意识到自己需要帮助去解决一个问题。
代理有一个goal，并且：

1. 要么意识到自己没有能力维持孤立isolation并达成目标
2. 要么意识到它不希望孤立地实现目标prefer not to achieve the goal in
   isolation（通常是因为解决方案质量、截止日期等原因）

9.4.2. Announcement广播公告

在这个阶段，有任务的代理发出任务公告announcement，其中包括要实现的任务的详细说明 specification
说明必须编码：

• 任务本身的描述（可能是可执行的）
• 任何约束条件（如最后期限、质量约束）
• 元任务meta-task信息（如 “投标必须由…提交”）
  然后广播broadcast该公告

9.4.3. Bidding代理人竞标

收到公告的代理人自行决定是否要竞标bid该任务
因素：

• 代理人必须决定其是否有能力推进expedites任务
• 代理人必须确定质量约束quality constraints和价格信息price
  information（如果相关）
  如果他们选择投标，那么他们就需要提交投标书submit a tender

9.4.4. Awarding && Expediting

发出公告的代理人必须在所有投标中进行选择，并决定将合同 "授予 "谁（award the contract to）
将该结果告知提交了该投标的代理人（successful contractor），该中标的承包商然后推进expedites任务
可能涉及产生进一步嵌套的的经理-承包商关系：分包合同sub-contracting

9.5. Issues for Implementing Contract Net

如何

1. …specify tasks?
2. …specify quality of service?
3. …select between competing offers?
4. …differentiate between offers based on multiple criteria?

The Contract Net:
一种分布式问题解决的方法，重点是任务分配task distribution
任务分配被视为一种合同谈判contract negotiation
"协议Protocol "规定了通信的内容content，而不仅仅是形式
信息（所谓内容）的双向传输是控制机制（所谓协议）传输的自然延伸

Cooperative Distributed Problem Solving(CDPS)
既不是全局控制也不是全局数据存储——没有哪一个代理有足够的信息能解决所有问题
Control and data are distributed，对应之前的result sharing，一般管这叫分布式

通信Communication比计算computation耗时的原因：

1. 松耦合loose coupling
2. 高效协议efficient protocol
3. 模块化问题modular problems
4. 大颗粒度问题problems with large grain size

任何单一unique的节点都是一个潜在的效率的瓶颈：

1. 数据被分散
2. 控制被分散
3. 很难保证有组织的行为（因为没有一个代理人拥有完整的全局信息）

9.6. Contract Net

以Contract Net来看，解决问题主要有四个步骤，而Contract Net主要解决了第二步：

1. Problem Decomposition 大问题分解成小问题
2. Sub-problem distribution 子问题分发给多个代理
3. Sub-problem solution 子问题各自解决
4. Answer synthesis 答案汇总

节点（node，代理人）的集合是”contract net“
每个网络中的节点在不同的时间为了不同的任务，可以分别扮演manager或contractor
当一个节点得到一个复合任务（或者由于任何原因没法完成他受到的任务时），他会将其分解为子任务并broadcast这些任务给承包商（contractors），收到竞标（bids）后他会选出条件好的承包商承包（award）。

例子：网络资源管理，打印机

9.6.1. Types of Messages in Contract Net

• Task announcement
• Bid
• Award
• Interim report (on progress)
• Final report (including result description)
• Termination message (if manager wants to terminate contract)

9.6.2. Efficiency Modifications

一些改良：

1. Focused Addressing集中寻址：如果不需要广播，就定向传输。以前是大喇叭喊，如果知道手机号的话直接打手机号就可以了
2. Directed contracts定向合同：任务发布时直接指定某一个或某些节点干这事，省去了广播后节点自荐的时间
3. Request-response mechanism请求-响应机制：用于简单的信息传输，无需合同开销。任务发布者要什么，直接向节点要，节点收到请求后返回他要的东西
4. Node-available message 节点可用消息：代理人定时向任务分发者汇报自己能干啥，省去广播的时间

Lec 10 Agent Communication

Those issues relating to the agent society, rather than the individual.

10.1. Speech Acts

utterances话语；utter说话

多代理系统的大多数通信处理方法都与speech act theory言语行为理论有关。
言语行为理论尝试解释人们每天如何使用语言来实现他们的目标和意图，是一套关于话语如何被用来实现意图的理论
一些话语更像是”物理行动“，能够改变世界的状态：
比如：

1. 宣战会导致国家的战争状态
2. 神父的誓词会导致婚姻状态成立

更通常的来说，我们所做的一切都是为了实现目的或某种意图。

Locutionary act：话语行为，就是说话是有意义的。“天在下雨”（√） “sdagawegea”（×）
illocutionary act：言外之意，另外的含义。“我下周会还他的钱”——说话人做出承诺
Perlocutionary act：言后行为，就是听到话的人会有影响。给小孩讲鬼故事——小孩晚上会害怕

Speech act的种类：

1. representatives陈述: such as informing, e.g., ‘It is raining’
2. directives指挥: attempts to get the hearer to do something, e.g., ‘please make the tea’
3. commisives保证: which commit the speaker to doing something, e.g., ‘I promise to… ’
4. expressives表达: whereby a speaker expresses a mental state, e.g., ‘thank you!’
5. declarations宣言: such as declaring war or christening

大体来说，speech act可以视为由两部分组成：

1. performative verb （request，inform，promise）
2. propositional content （”the door is closed")

例子：

1. performative = request
   content = “the door is closed”
   speech act = “please close thedoor”
2. performative = inform
   content = “the door is closed”
   speech act = “the door is closed!”
3. performative = inquire
   content = “the door is closed”
   speech act = “is the door closed?”

10.1.1. Plan-Based Semantics

如何定义语义semantics？
When can one say someone has uttered?，e.g.，a request or aninform？
注意，说话者不能（通常）强迫他人接受某些特定的心理状态。
In other words, there is a separation between the illocutionary act(言外之意） and the perlocutionary act（言后行为）

请求request的语义（semantics）：

request(s,h, ϕ \phi ϕ)
pre:

• s believe h can do ϕ \phi ϕ(你不会要求别人做什么，除非你认为他们能做。)
• s believe h believe h can do ϕ \phi ϕ(你不会要求别人做什么，除非他们认为他们能做。)
• s believe s want ϕ \phi ϕ(你不会要求别人做什么，除非你想要完成那件事。)

post：

• h believe s believe s want ϕ \phi ϕ（语言的影响是使得h相信s要完成这件事）

10.2. KQML

agent communication languages (ACLs) ——消息交换的基本格式
其中最有名的是KQML，由两部分组成：

1. the knowledge query and manipulation language(KQML)知识查询和操作语言
2. the knowledge interchange format (KIF)知识交换格式

10.3. KQML and KIF

KQML是一种“外部”语言，它定义了各种可接受的“交际用语communicative verbs”，或表现形式performatives
例如：

ask-if (is it true that ...?)
perform (please perform the following action ...)
tell (it is true that)
reply (the answer is ...)

KIF（Knowledge Interchange Format）是一种表达消息内容content的语言，通常用来说明：

域domain中事物的属性（例如，"Noam is chairman"） 
域中事物之间的关系（例如，"Amnon is Yael’s boss"） 
域的一般属性（例如，"Allstudents are registered for at least onecourse"）

例如：
“The temperature of m1 is 83 Celsius”:
(= (temperature m1) (scalar 83 Celsius))
“An object is a bachelor if the object is a manand is not married”:
(defrelation bachelor (?x) := (and (man ?x) (not (married?x))))
“Any individual with the property of being a person also has the property of being a mammal”:
(defrelation person (?x) :=> (mammal ?x))

Ontology：
为了能够进行交流，代理人必须就一套共同的术语达成一致。这种规定叫做ontology本体论
有个叫ontolingua的工具能够实现定义共同本体论
例子：

10.3. FIPA & ACL

Foundation for Intelligent Physical Agents，
上面这个定义了一个代理人标准：其中心是ACL，其基本结构与KQML相似：

1. performative
   20 performative in FIPA
2. housekeeping
   e.g., sender, etc.
3. content
   the actual content of the message

10.3.1. Inform and Request

"告知inform"和 "请求request"是FIPA中的两个基本的表现形式。所有其他的消息都在这之上进行定义。

告知和请求的含义被定义为两部分：

前提条件pre-condition：为了使言语行为成功，必须是真实的
“合理效果rational effect”：信息的发送者希望带来什么

Inform：
content：statement
Pre-condition is that sender:

• holds that the content is true
• intends that the recipient believe the content
• does not already believe that the recipient收消息方 is aware of whether content is true or not

Request：
content：action
Pre-condition is that sender:

• intends action content to be performed
• believes recipient is capable of performing this action
• does not believe that receiver already intends to perform action

本文标签： 代理人笔记系统