基于Agent的智能谈判优化方案

1.2.1 Agent的基本概念及主要分类

1.Agent的基本概念

（1）Agent的定义

随着Agent的出现、产生和研究的不断进步，有关Agent的定义也更加丰富，其中有代表性的如M.Wooldrige和Jennings给出的有关Agent的强定义和弱定义[1]。目前较为普遍的是认为Agent是一种计算机系统，它能够根据外部环境的变化，自主地完成预先设定的任务[2]。

（2）Agent的主要特征

目前为止，通常认为Agent应当具有下述部分或全部特征：

①自治性。

运行不需要人或其他Agent的直接干预，Agent能够控制自己的行为和内部状态。

②反应性（交互性）。

能够感知它所存在的环境的变化，并通过行为改变环境。一个不能影响环境的系统不能称为Agent[3]。

③协作性。

往往不是单独存在的，它要通过某种通信语言与其他Agent进行交互，以共同完成预定的任务。

④主动性。

并不是被动地对环境的变化做出反应。它能够自己为行动设定目标，表现出一种有目的的行为。

⑤社会性。

Agent可以与其他Agent（也可能是人）交互，以满足其设计目标。

⑥长寿性（或时间连贯性）。

传统程序由用户在需要时激活，不需要时或运算结束后停止。Agent与之不同，它应该至少在“相当长”的时间内连续地运行。

（3）Agent的主要理论模型

目前，有关Agent的主要理论模型都是建立在普遍认为Agent具有人类所具有的信念、意图、愿望等属性的基础之上的，有代表性的模型主要有如下几种：

Levesque提出的有关信念和感知的逻辑模型主要对显性的信念和隐性的信念作了一个界定，但是没有进行定量分析，也不允许对嵌套的信念进行界定，最重要的是，会使Agent的推理与现实世界不相吻合[4]。因此，为了克服这些负面影响，Fagin和Halpern提出了一种基于一般感知的逻辑模型，试图解决这些问题，但仍很难满足要求[5]。

Konolige提出的有关资源约束的信仰者的演绎模型基本上是对符号人工智能系统中的信念进行建模，并对模型进行一些检验，提出了一系列证明他的逻辑的方法，包括解决（Resolution）系统和生动的场面（Tableau）系统，虽然模型简单，但还是提出了一个比较直接的有关Agent中信念系统的模型，因此具有一定的可取之处[6]。

Cohen等最早提出的有关意图的形式化理论在有关Agent的研究领域中最为著名，也最有影响力，主要使用了信念和目标两个基本的态度，例如意图等更进一步的态度则建立在此基础上，他们的研究对Agent推理和多Agent间对话的冲突解决和合作起到了至关重要的作用[7]。Rao和Georgeff则在此基础上提出了相关的逻辑框架，他们的分支模型融进了时间因素，主要关心现实主义问题，即Agent对其愿望和意图在未来可能对信念产生的影响。此外，他们也在其余的相关工作中考虑将（社会）计划加入其形式化理论中[8]。

Singh提出了一个有趣的逻辑语系，在基于时间分支的框架中表达了意图、信念、知识和通信等，主要建立在Asher-Kamp演说表达理论基础上，研究相当丰富，成果也非常显著[9]。

Wooldridge在其研究中提出了一种表达多Agent系统的逻辑语系，主要目的是为了构建一种形式化的理论，能够在现实的多Agent系统中进行规定和验证，他在给出了合适的符合现实协议的基础上对Agent的合作行为进行了举例说明和验证[10]。

（4）Agent的功能和体系结构

就目前有关Agent的大量研究来看，其所具有的功能包括推理、规划、学习和适应等许多方面。为了实现这些不同的功能，由封装了不同代码的不同模块组成的Agent体系结构也因此而显得纷繁复杂。其中，有代表性的是M.Wooldrige和Jennings从总体上将其划分为如下三种：

①经典结构：慎思结构。

这种结构主要建立在物理—符号系统假设的基础上，这方面的研究最早由Newell和Simon提出，并在1987年被Genesereth引入Agent理论中[11]。他认为，具有慎思结构的Agent指的是能将整个世界用符号模型进行清晰完整地表示，并通过逻辑推理进行决策的Agent。因此，具有这类结构的Agent至少需要解决如下两个方面的问题：一是将现实世界用一种精确且充分的符号规则描述出来，并及时、有效地使用这种规则，即翻译问题，这个问题将会涉及语言的理解、学习等；二是如何符号化地表达复杂的现实世界中实体及过程的相关信息，以及如何使Agent及时、有效地利用这些信息进行推理，即表达和推理问题，这个问题将会涉及知识的表达、自动推理和自动制定计划等。

在有关Agent慎思结构的研究方面，主要有以下两个方面的研究：

●有关能制定计划的Agent的慎思结构研究。即设计一个详细的行为过程，当其被执行时，能使这些被设计的目标实现。目前，在符号人工智能团队领域的研究中，一直以来都认为某种形式的人工智能计划制定系统都将会成为人工智能领域中的Agent的中心组件。最早且知名的计划制定系统是STRIPS，但其中的计划制定机制显得非常简单，并且已经证明，即使是在适度复杂的系统中，这个机制也不太有效。因此，随后的许多研究都致力于开发更加有效的自动计划制定技术，并在分层和非线性计划这两个方面有所创新。20世纪80年代中期，Chapman确立的一些理论结果表明，即使技术如此精炼，在任何受时间约束的系统中也是没有用的，但他的工作导致了其后这个领域内一些更加丰富的研究[12]。尽管上述研究都存在相应的问题，还是有许多系统［如基于复杂非线性计划者理论基础上的IPEM（集成了计划、执行和管理的系统）[13]、在一个能模拟交通环境的高度动态环境下使Agent自动制定计划的AUTODRIVE系统］被开发[14]。

●基于一些有关Agent信念、愿望和意图的理论基础之上的慎思结构研究。其中有代表性的是Bratman、Israel和Pollack的IRMA（受资源约束的智能机制体系结构），包括一个计划库和分别能清晰表达信念、愿望和意图这三者的四个关键的符号数据结构，此外，还包括一个能对现实世界进行推理的推理Agent、一个能选择合适的计划方式来实现其意图的方式选择Agent、一个能对环境进行把握并寻找机会的机会分析Agent、一个筛选处理程序和一个慎思处理程序。这个结构最终在一个称为Tileworld的环境下得到模拟和评估[15]。

②可替代的结构：反应结构。

从以上有关慎思结构的研究来看，在符号人工智能领域内仍有许多问题没有解决，这些问题导致了反应结构的产生和发展，这种结构并不包括任何一种中央的符号世界模型，也没有采用复杂的符号推理。在这方面的研究中，有代表性的是Brooks在行为语言方面提出的包容结构，在此基础上，他设计了许多自动的机械设备，主要建立在将这种结构看成是一种完成任务的行为的分层的基础上，每个行为都必须与其余的行为“竞争”，以实现对整个设备的控制，这种结构相当简单，没有清晰、准确的推理，甚至没有模式的匹配[16]。在此基础上，Steels也作了许多类似的工作，称之为“火星探测系统”，其中包括大量具有包容结构的Agent，在一定的任务制定后能得到近似于最优的结果[17]。

③混合结构。

许多学者认为，用一个完整的慎思结构或一个完整的反应结构来构建Agent都是不合适的，因此提出了混合结构的思想，主要想将这两种方法进行更好地匹配，以得到具有更加完美结构的Agent。在这方面的研究中，有代表性的是Furguson提出的旋转机制（Touring Machine）混合型Agent结构，这种结构主要包括感知和行为两个子系统，系统的界面直接面对Agent所处的环境，有三个独立且能并发执行的控制层，这三个控制层都嵌入在一个能协调各个控制层的控制框架中，通过使用他在研究中所提到的控制规则处理由不同层面而引发的冲突行为[18]。

2.Agent的主要分类

有关Agent的分类随着相关研究的日新月异而变得更加充实，例如，根据Agent的功能，可将其分为演绎推理Agent、实用推理Agent、规划Agent和学习Agent等；根据Agent的体系结构，可将其分为慎思型Agent、反应型Agent、混合型Agent等；根据Agent是否具有社会性，可将其分为非社会性Agent和社会性Agent等。此外，还有一些更为实用或细致的分类，如在信息搜索的过程中有搜索Agent和人机界面Agent等；在工资谈判过程中有代表管理者的Agent和代表工会的Agent等；在具体的工作流过程中有业务管理Agent和实现每个环节正常运作的Agent等。

1.2.2 谈判与基于Agent的谈判

1.谈判

（1）谈判的基本概念

作为人类社会中一种重要且普遍存在的现象，谈判涉及生活中的方方面面。谈判至少需要两个人类实体参与，即两个或多人以及两个或多个代表团。谈判是把面临分歧并相互依附的两个角色联系起来的一项活动。各方因持有分歧而相互对立，但彼此又相互依存。他们选择策略，谋求达成协议，以便解决分歧。各方在这项活动中不是求助某种解决纠纷的办法，如回避、对抗、行政命令等，而是谋求一个“可接受的结局”，致力于达成某种“一致”，这突出反映了谈判的本质。谈判的另外一个特性就是各方都尽力维护自己的利益。利益、忧虑、目标、愿望和需求是谈判的重要动力，这些都可归纳为一个概念，即利害得失。利害得失代表谈判者立场的合成结果，它是谈判者立场的一种支配因素和动力结构。

（2）谈判的主要分类

谈判和单纯解决问题或全面磋商之间存在很大的差别，谈判始终含有冲突的味道，或至少带点紧张气氛。谈判的活动范围是处于对抗行为和解决问题这两个极限之间的。由此引出合作性（Cooperate）谈判和非合作性（Non-cooperate）谈判两个概念。合作性谈判又称融合性（Integrative）谈判，是指谈判者表现出合作的态度，并具有互惠互利的意愿，这种谈判属于“赢—赢”的类型。非合作性谈判又称竞争性（Distributive）谈判，是指谈判者表现出微弱的合作或根本不合作的态度，他们怀着己方得利的意愿，甚至在必要时准备损坏对方利益或各方的共同目标，这种谈判属于“输—赢”的类型[19]。目前的研究主要集中在合作性谈判方面，本书的研究工作也是建立在合作性谈判的基础之上。

（3）谈判过程及阶段的划分

谈判过程是指整个谈判从开始、实施到结束所经历的完整的过程。根据这个顺序，可以大体上将谈判划分为三个主要阶段：

①谈判的战略（开始）阶段。

这一阶段主要涉及谈判各方利益的明确、谈判目标的制定、有关谈判信息的搜集与研究以及有关谈判的具体计划等。

②谈判的交互（实施）阶段。

这一阶段也就是通常意义上所说的谈判，是谈判具体实施的重要阶段，其间涉及谈判中合作伙伴的选择、有关谈判内容的具体谈判等，充满了不确定性，同时也是整个谈判中最难以把握的一个阶段，充分决定着整个谈判的成功与否，是整个谈判过程中最为重要的阶段。(www.xing528.com)

③谈判的决策（结束）阶段。

这个阶段是谈判各方对谈判结果的判断和分析阶段，主要包括决定是接受谈判还是开始新的谈判等，也是整个谈判过程中的重要阶段。

如果将以上谈判涉及的阶段更进一步细分，将显得更为复杂，因此，本书的工作主要建立在对谈判的重要阶段（即第二阶段和第三阶段）的综合分析和研究的基础之上，具体来说，主要研究谈判交互阶段中合作伙伴选择和有关谈判内容的具体谈判，并对谈判结果进行判断和分析，完成谈判的决策阶段。

（4）谈判主要包括的内容

无论是合作性谈判还是非合作性谈判，具体的谈判过程都包含如下三个主要部分：

①谈判协议。

这是指控制、管理谈判参与者之间交互谈判的规则集合。控制的内容包括谈判参与者的允许类型、谈判状态（如交互报价、谈判结束等）、可触发谈判状态改变的事件（如报价已被接受）、谈判参与者在不同状态下可采取的有效行为（如在哪个阶段可以由谁发出何种讯息）等。

②谈判策略。

这是指能帮助谈判参与者进行具体决策的函数。通过这个函数产生一系列报价以实现谈判目的，其策略模型的复杂程度和决策范围主要受谈判协议设计的影响与制约，而上述谈判目标及可对谈判目标所执行的操作也对其有一定的影响。

③谈判模型。

这是指在规定了一系列谈判协议和相应的谈判策略的基础上所采用的能保证谈判较为顺利地实施的模型。通过合适的模型选用，可以采用与之相匹配的谈判策略及对应的谈判协议，使谈判朝着各方都能接受的方向进行，并使谈判结果最大限度地满足谈判各方的需求，进而使谈判各方最终对谈判结果做出正确的决策。

2.基于Agent的谈判

目前，基于Agent的谈判主要定义为“多个Agent之间（其中的某个或某些Agent也可以是人）为了就某些问题达成一个可共同接受的协议而进行的交流过程”，谈判各方的目的都是在谈判过程中实现其自身利益的最大化[20]。因此，从理论上说，基于Agent的谈判都可以将以上人类的谈判及相关理论以Agent间谈判的形式来实现。

1.2.3 基于Agent的谈判的主要理论及相关模型

最初，人们只是将谈判看成是一门简单的艺术，并没有将其作为一门科学看待，这同样反映在基于Agent的谈判中，因此，相关的理论模型显得极为有限，且不实用。随着社会和各门学科的发展，人们越来越意识到基于Agent的谈判除了是一门艺术之外，更大程度上还体现了其作为科学的一面，相关的理论模型也随之丰富起来。本书对这方面的划分主要建立在较有代表性的根据其应用领域的不同而将其分类的基础之上[21]。

1.博弈论及相关模型

博弈论是研究冲突解决的数学方法，而基于Agent的谈判的目的就是要解决Agent之间的冲突。因此，这个理论最早被引入基于Agent的谈判过程的分析中，主要集中在对代表谈判各方的Agent最终是否达成一致的预测和判断这两个方面[22]。此外，博弈论还被用来进行相关的机制设计，使代表谈判各方的Agent最终达到所谓的“帕累托最优”。

2.对策论及相关模型

Von Neumann和Morgenstern在《对策论与经济行为》一书中奠定了对策论的理论基础。20世纪50年代，Nash发表了谈判对策理论方面的文章，提出Nash均衡解，为对策论在基于Agent的谈判的主要理论模型的研究方面奠定了基础。20世纪70年代以来，冲突分析方法对这方面的理论模型进行了更进一步的充实。较有代表性的有Bennett提出的超对策分析模型[23]和Fang等提出的解决冲突的模型[24]等。

3.社会学理论及相关模型

有关基于Agent的谈判的社会学模型所涉及的理论主要有社会学、心理学等，由于这些学科知识的特殊性，这类模型都是描述性（即形式化）的，它们从不同角度来描述或解释整个谈判过程。较有代表性的有Bartos从社会学观点提出的有关谈判的理论模型和Spector从心理学观点提出的有关谈判的理论模型等。

4.经济学理论及相关模型

与对策论模型相比，基于Agent的谈判的经济学模型是动态模型，既注重谈判过程，又注重谈判的最终结果，而对策论模型基本上是静态模型。经济学模型和对策论模型的另一个重要区别是前者倾向于强调谈判对方期望行为的形成过程；后者既强调每个局中人怎样预测对方的行为，又强调怎样产生确定的输出。较有代表性的有Zeuthen关于在双边垄断条件下的经济冲突解决模型等。

5.政治学理论及相关模型

这方面的理论模型主要是通过对利益冲突的测试来对政治行为进行预测。较有代表性的是Axelrod利用诸如谈判对策和囚徒困境问题的抽象来建立不同政治过程的政治模型等，该模型提出了一些值得借鉴的思路，如如何确定可能性的输出、参与者对这些输出的效用评价以及在不同利益冲突下的行为观测等。

[1] Wooldrige M.J.，Jennings N.R.，Intelligent agent：theory and practice， Knowledge Engineering Review，Vol.10，Iss.2，1995，pp.120-145.

[2] Jennings N.R.，Sycara K.，Wooldrige M.J.，A roadmap of agent research and development，Autonomous Agents and Multi-Agent Systems，Vol.，Iss.1，1998， pp.275-306.

[3] 史忠植等，《高级人工智能》，科学出版社，1997年。

[4] H.J.Levesque，A logic of implicit and explicit belief，In Proceedings of the Fourth National Conference on Artificial Intelligence（AAAI-84），Austin，TX，1984， pp.205-225.

[5] R.Fagin and J.Y.Halpern，Belief，awareness，and limited reasoning，In Proceedings of the Ninth International Joint Conference on Artificial Intelligence（IJCAI-85），Los Angeles，CA，1985，pp.345-389.

[6] K.Konolige，A deduction model of belief，Pitman／Morgan Kaufmann，1986， pp.268-305.

[7] P.R.Cohen and H.J.Levesque，Intention is choice with commitment， Artificial Intelligence，Vol.42，1990，pp.213-261.

[8] A.S.Rao and M.P.Georgeff，Social plans：preliminary report，In E.Werner and Y.Demazeau，editors，Decentralized AI 3—Proceedings of the Third European Workshop on Modelling Autonomous Agents and Multi-Agent Worlds（MAAMAW-91），Elsevier／North Holland，1992，pp.57-76；A.S.Rao and M.P.Georgeff，A model-theoretic approach to the verification of situated reasoning systems，In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence （IJCAI-93），Chambery，France，1993，pp.318-324.

[9] M.P.Singh，Group ability and structure，In Y.Demazeau and J.-P.Müller， editors，Decentralized AI 2—Proceedings of the Second European Workshop on Modelling Autonomous Agents and Multi-Agent Worlds（MAAMAW-90），Elsevier／North Holland，1991，pp.127-146；M.P.Singh，A critical examination of the Cohen-Levesque theory of intention，In B.Neumann，editor，Proceedings of the Tenth European Conference on Artificial Intelligence（ECAI-92），John Wiley &Sons， 1992，pp.364-368.

[10] M.Wooldridge and M.Fisher，A first-order branching time logic of multi-agent systems，In B.Neumann，editor，Proceedings of the Tenth European Conference on Artificial Intelligence（ECAI-92），John Wiley &Sons，1992，pp.234-238.

[11] M.R.Genesereth and N.Nilsson，Logical foundations of artificial intelligence，Morgan Kaufmann Publishers，Inc.，1987，pp.568-612.

[12] D.Chapman，Planning for conjunctive goals，Artificial Intelligence，1987，pp. 32-44.

[13] J.Ambros-Ingerson and S.Steel，Integrating planning，execution and monitoring，Proceedings of the Seventh National Conference on Artificial Intelligence （AAAI-88），St.Paul，MN，1988，pp.568-589.

[14] S.Wood，Planning and decision making in dynamic domains，Ellis Horwood Ltd.，1993，pp.332-346.

[15] A.S.Rao and M.P.Georgeff，Modeling rational agents in a BDI-architecture， In R.Fikes and E.Sandewall，editors，Proceedings of Knowledge Representation and Reasoning（KR&R-91），Morgan Kaufmann Publishers，Inc.1991，pp.473-484.

[16] R.A.Brooks，Elephants don't play chess，In P.Maes，editor，Designing Autonomous Agents，The MIT Press，1990，pp.3-15.

[17] L.Steels，Cooperation between distributed agents through self organization，In Y.Demazeau and J.-P.Müller，editors，Decentralized AI—Proceedings of the First European Workshop on Modelling Autonomous Agents in Multi-Agent Worlds （MAAMAW-89），Elsevier／North Holland，1990，pp.175-196.

[18] I.A.Ferguson，Towards an architecture for adaptive，rational，mobile agents， In E.Werner and Y.Demazeau，editors，Decentralized AI 3—Proceedings of the Third European Workshop on Modelling Autonomous Agents and Multi-Agent Worlds （MAAMAW-91），Elsevier／North Holland，1992，pp.249-262.

[19] 杨子晨、孟波、熊德林、肖延松，“谈判支持系统研究综述”，《系统工程理论方法应用》，2002年第2期。

[20] 高璐、毛波、王方，“基于MAS的企业供应链模型中谈判过程的研究”，《系统工程理论方法应用》，2002年第4期。

[21] 唐卫东，《谈判支持系统的理论与设计研究》，天津大学博士论文，2003年。

[22] N.R.Jennings，P.Faratin，A.R.Lomuscio，S.Parsons，C.Sierra，and M. Wooldridge，Automated negotiation：prospects，methods and challenges，Group Decision and Negotiation，Vol.10，Iss.2，2001，pp.199-215.

[23] Bennett P.G.，Tait A，Interact，software technical note，Group Decision and Negotiation，Vol.2，1993，pp.175-182.

[24] Fang L.，Hipel K.W.，Kilgour D.M.，Interactive decision making：the graph model for conflict resolution，John Wiley &Sons，New York，1993，pp.245-298.