计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999　Vol.36　No.7　P.776-782



自主机器人自组织结构IRASO的仿真研究
朱淼良　张新晖　吴春明　钱徽
摘　要：自主机器人车辆具有智能性和快速反应的特点，而在精确推理和实时性之间寻求最佳折衷是体系结构的关键.文中提出基于分布式多Agent系统的自组织体系结构 IRASO，Agent之间动态组合以适应环境变化，公告板系统评估环境势态和指导Agent组织，同时设计了Agent协调工作的空间和时间模型.基于TCP／IP的计算联通域为异质分布式多Agent的协作运行提供支持.仿真结果表明该结构在智能性和实时性达到了期望特性.
关键词：自主机器人，多智能体系统，分布式人工智能，公告板系统，势态评估
分类号：TP18；TP242.6
SIMULATION STUDY OF THE SELF-ORGANIZING ARCHITECTURE
IRASO FOR AUTONOMOUS ROBOT VEHICLES
ZHU Miao-Liang
(Institute of Artificial Intelligence, Zhejiang University, Hangzhou 310027)
ZHANG Xin-Hui
(Institute of Artificial Intelligence, Zhejiang University, Hangzhou 310027)
WU Chun-Ming
(Institute of Artificial Intelligence, Zhejiang University, Hangzhou 310027)
QIAN Hui
(Institute of Artificial Intelligence, Zhejiang University, Hangzhou 310027)
Abstract：Intelligence and responsiveness are the two issues in architectures of autonomous robot vehicles. The key is how to make good tradeoff between deliberative reasoning and fast reaction. This paper explores a type of architecture, which is based on a distributed multi-agent system. Agents can be dynamically reorganized to suit the various environments. A bulletin board system plays the role of assessing the surrounding situation and organization of the agents. Several models are designed to coordinate agents both in temporal and spatial.The computing coherent field based on TCP/IP supports agents to work together. The simulation shows that the architecture is desirable both in intelligence and responsibility.
Key words：autonomous robot vehicle， multi-agent system， distributed artificial intelligence， bulletin board system， situation assessment▲
1　引言
　　工作在复杂和动态变化的非结构化环境中的自主机器人车辆(ARV)必须具备足够的智能以便处理和适应各种不可预见势态.有多种使机器人具有智能的方法，通常把任务分解成能被多个模块完成的子任务，这些模块具有专门的领域知识且能单独解决特定的问题，如感知、规划、推理等.体系结构的要点在于组织各功能模块以求得优化功能，使系统在智能和效率方面达到较高的性能，对动态环境作出反应.限于机器人系统的有限资源，有必要在快速反应和精确推理之间寻求最佳折衷.ARV最主要的体系结构可分为分层递解式结构和包容式结构两种.在分层递解式结构中［1］，精确推理在高层，而在线的输入输出在底层，从底层传感器得到的数据经过层层处理传送到高层进行精确评估和推理，生成控制命令再层层下传.这样的结构有足够的智能，但效率会随着层数的增加而降低.包容式结构是另一种形式的分层结构，每层相当于一个行为产生器(如道路跟踪、避障)，能直接感知环境和作出反应.多个行为产生器提供并发的多种行为，使系统更加敏捷.在早期的结构中［2］，多种行为的裁决通过线连接实现，高层覆盖低层.当目标复杂时，该结构暴露了一些问题，且难以利用全局知识.
　　一些实际系统采用一定的办法来结合两者的优点，如美国Demo计划中的SSV［3］，Liscano提出用黑板系统协调系统行为［4］， Rosenblatl 在 DANM系统中用行为器的投票来解决多目标的命令融合和全局导航问题［5］.
　　本文通过考察人的智能行为模型， 提出相应的自主机器人体系结构.首先考虑人驾驶汽车的行为：当行驶在路况良好的结构化道路时，只要简单地跟踪道路两边或中心线，而不需要更多的智能，然而当达到某一分叉点时，驾驶员必须深入思考，包括使车辆减速、判断分叉点的地形，从地图知识中找到正确的分叉方向，然后向左或向右转.从该例中我们可以得到如下结论：
　　(1)当环境势态简单时，驾驶任务也简单，只要执行很少几个操作行为.然而当周围环境变得复杂时，必须执行更多更精巧的任务或子任务；
　　(2)处理不同的势态需不同的任务或子任务的组合，即解决不同状态下问题的智能行为由多种不同的操作行为组合而成；
　　(3)势态的评估对于如何操纵行动以产生智能行为非常重要.
　　因而对于驾驶在不可预见环境中的车辆，势态评估和智能行为组织是非常重要的，这两点是自主和智能控制的内核且依赖于体系结构.本文提出基于分布式多Agent的体系结构：自组织结构 IRASO(Intelligent Robotic Architecture with Self-Organization).该体系结构是分布式人工智能的协同多Agent系统，Agent产生行为，工作中只有必需的Agent被激活来响应当前环境.公告板收集外部和内部事件，进行势态评估，作出决策和协调.仿真结果表明该体系结构在智能性和反应能力上都达到了期望特性.
2　体系结构
　　图1是机器人在执行“道路跟踪”任务时IRASO的组织,它组合了5个Agent以完成该任务.中心信息处理系统公告板显示当前任务(状态)是“道路跟踪”，在当前状态下激活道路检测、路径规划、驾驶命令、移动和定位等Agent分别完成不同的子任务，它们共同合作完成道路跟踪.与此同时障碍检测Agent检测道路前方区域是否有障碍，若发现障碍，就向公告板报告“发现障碍”的事件.公告板评估所有Agent提供的事件，包括新事件“发现障碍”，然后将当前状态转变为“避障”，即机器人前方发现障碍且应采取行动来避开它.在当前状态的指导下，驾驶命令Agent首先送出命令“减速”给移动控制Agent.其他Agent，如融合Agent也被激活并加入来完成避障任务.值得注意的是已激活Agent在新状态下会改变其功能，如障碍检测Agent的功能从检测转变为准确计算障碍物的位置.融合Agent同时接收来自路径检测和障碍检测两个Agent的数据，生成包括道路形状和前方障碍物的局部地图，路径规划Agent改成避障规划算法，全局监控Agent定时接收定位信息并计算机器人是否进入分叉区或达到目的地.其他Agent，如路标定位(图中的虚圆)没有被激活，处于睡眠状态.分叉是更加复杂的任务，不仅需要视觉信息定位分叉点，同时需要全局地图知识.如图2所示，在该状态下有10个Agent从不同方面协作完成分叉任务.系统在不同状态下参与完成任务的Agent不相同，体系结构表现出自组织性.

　　　　
图1　道路跟踪状态下的IRASO结构

　　　　
图2　分叉状态下的IRASO结构
　　以上的描述体现了 IRASO的如下特性：
　　首先IRASO将智能行为分布在Agent中，每个Agent是自主独立工作的问题求解单元，如果需要，它们协作解决复杂的全局任务(如避障).当前状态是关键信号，它告知所有Agent当前的全局任务，在当前状态下，每个 Agent根据其先验知识选取不同的功能(包括睡眠或激活)并决定如何和别的 Agent合作(数据的输入输出). IRASO中 Agent之间是通过公告板来协调的；
　　其次，当前状态必须正确反映当前势态并为所有Agent的工作提供全局指导.公告板收集所有来自 Agent的事件，每个事件描述了处理数据时所发生的结果.如障碍物检测 Agent从激光扫描图像数据中检测到障碍，就向公告板报告“发现障碍”事件.公告板中事件集合提供了车辆系统内外的全局信息.基于先验知识或模型，公告板评价每个事件和全局势态并最终推理出当前状态.势态评估精确地基于全局信息，从而保证了当前状态的正确性.
　　整个系统中有三类消息.第一类是描述图像、路径等对象的对象数据，它们被不同的Agent依次处理且只在Agent之间交换；第二类是Agent对结果数据的简单描述或处理过程评价的事件信号，编码成符号形式且直接提交给公告板；第三类当前状态是当前势态的评估结果并以广播的方式送给所有Agent.
　　系统中存在两个信息／控制流，分别为数据流和信号流.数据流由对象数据组成，形成感知-规划-行为的环路，产生机器人行为.信号流是由Agent与公告板之间的事件和当前状态组成，形成状态-决策-行动的环路.显而易见，后者是比前者更高级的环路，它监控前者，包括激活和组织 Agent.因而系统结构(Agent及它们之间的相互关系)能够根据环境动态重组，表现出自组织性.在不同状态下，系统灵活地组织各Agent形成不同的拓扑结构，如在简单环境下可能只含有一个传感器和一个执行器，而在复杂环境中，为了精确推理，包含了全局和局部规划.该体系结构极大地提高了处理复杂动态环境的能力，而不需要复杂的固定结构.
　　在大多数情况下只有部分必需的Agent需要保持工作，这是由于当前状态可以精确确定当前情况下需要哪些Agent，另外的Agent可以安排睡眠.在计算机系统中，一个Agent可以映射成一个软件模块，睡眠的Agent释放其占用的资源(CPU和网络资源)，使得当前工作的Agent效率更高.
　　下面对构成体系结构的三要素： Agent、联通域和公告板分别加以描述.
2.1　专用Agent
　　Agent是一自主和异质的特定领域的问题求解单元，具有自己的知识模型和 I／O系统，独立工作在计算环境中. Agent的变化从简单的设备驱动器到复杂的专家系统，一个Agent同时有多种功能处理不同的势态.如视觉Agent既要能找到普通路边，同时也能找到道路交叉点. Agent能柔性改变和其它Agent的I/O连接.为了满足上述要求，我们设计了图3所示的IRASO通用Agent结构模型，它包含3个部分；内核、I／O端口和“开关”.内核含有特殊的功能函数库或知识库系统. I／O端口提供了和其它Agent互换消息的多个通道，通道不是线连接，而是软连接，就像软件模块之间的通信一样可以建立任何两个Agent之间的连接通道，计算环境联通域提供了一系列这样的工具.“开关”是 Agent和公告板的接口，接收当前状态和报告事件，由它选择内核功能和建立I／O通道，“开关”的工作模型可以是简单的查表，也可以是复杂的状态自动机.　　

　　　　
图3　Agent结构模型
　　Agent在一般情况下按如下方式工作：首先从公告板的广播中取得当前状态，并由“开关”作出决策，选择特定的内核功能和 I／O通道，内核处理从输入通道来的数据，并把结果输出到相应的输出通道.Agent同时推断出处理结果，对结果数据作出评价作为事件报告给公告板.一个 Agent有两种状态：运行(激活)，睡眠和半睡眠.在半睡眠状态， Agent仍然工作，并向公告板报告事件，但并不输出数据，起到监视器的作用，如在道路跟踪状态下的障碍检测Agent.“开关”可以使Agent睡眠，实际上睡眠的Agent并没有真正睡眠，它仍然从公告板接收当前状态并在必要时唤醒自己.
　　上述的Agent是在一个称为联通域的环境中工作的，联通域是所有Agent和公告板协作运行的分布式计算环境，它所支持的计算机系统从单片机到高级工作站，操作系统都不相同.
　　体系结构的首要任务是把这些异质系统结合到统一的联通环境中，该环境是多Agent协作的基础.在不同的计算机系统上运行的Agent可以以统一的通信和资源共享方式并发，同步工作.
　　联通域底层用网络连接不同的计算机，基于 TCP/IP的网络邮件发送软件支持在网络任何合适的节点加载Agent和实现Agent之间点到点的实时信息传送.联通域的另一个特点是统一的逻辑名字和协议.一旦Agent登记了其逻辑名，就可以“存活”和运行在任何节点.Agent传递消息就是以简单的格式写一封信，传送系统按照名字可以把该消息通过网络送到目的地.由于传送的实时性，Agent可以通过它来协调工作.在联通域中，Agent之间I／O通道的建立只是简单地改变相关Agent的名字就可实现.
2.2　公告板——Agent协调机构
　　公告板是高层的监控器，其功能是收集事件和评估事件所表示的势态，并对当前状态的改变作出决策.当前状态是Agent活动和协作的关键信号，所以状态改变必须相当精确，状态改变依赖于协作模型和执行机制，后者必须高效.公告板系统有和黑板相似的结构，但又不是传统的黑板系统，其结构如图4所示.公告板系统由布告板、知识库和推理机3部分组成.布告板作为中心黑板是所有Agent的共享内存，它分为3部分：第1部分存放全局数据，如机器人系统参数；第2部分存放收集的事件；第3部分是周期性更改的当前状态.一个监控器管理公告板的入口，包括接收事件和广播当前状态.知识库包含势态评估和状态转换模型，采用基于规则的知识库系统来实现精确推理.推理机观察布告板的变化，寻找知识库中的匹配规则并执行匹配规则，该过程重复执行直到得到新的当前状态.由于传统的符号推理系统难以实时实现，设计了基于OPS83系统的Rete网结构和知识编码相结合的快速推理机FRete，推理速度大大提高，通常的状态转变决策可以在毫秒级完成.

　　　　
图4　公告板系统
　　需要指出两点，第一，公告板系统不同于传统的黑板系统，虽然公告板中有中心黑板作为全局共享内存的布告板，但没有传统黑板系统中的知识源，用规则系统执行推理，因而更是一个产生式系统.布告板相当于工作内存，对所有Agent开放，不像普通产生式系统中只对推理机开放.推理过程基于势态评估和状态转换模型，该模型很容易用规则系统表示，且推理速度可以用知识编码技术提高；第二，公告板系统也不同于CMU的Navlab中的白板系统.在白板系统中，知识源用多个并发的专用模块取代，这些模块监视中心白板以决定它们的行为，同时它们也把中心白板作为中心数据库和模块间通信的媒体.中心白板不可避免地成为整个系统的“瓶颈”.相反，公告板系统只是起到收集事件和作出势态评估，当前状态以不占多少带宽的广播方式传送，数据直接从Agent到Agent传送，避免了通信阻塞.
3　协作与协调模型
　　协作和协调是多Agent系统的实质问题.在IRASO中同时存在信号流和数据流.信号流由事件和状态信号组成状态-决策-行动的高层监控回路，机器人的行为由事件驱动，即Agent间的协作是事件驱动的，因而可用离散事件系统理论DES［6］设计Agent的协调模型-行为调度器，该模型用基于规则的知识库表达，由推理机完成.组成感知-规划-行为回路的数据被不同的Agent依次顺序处理，为了提高数据处理能力，设计了流水线导航模型［7］.而冻结坐标模型则用来解决Agent在时间和空间上的同步.3个模型在不同层次上协调多Agent系统，表现出反应的实时性和智能性.
　　调度器完成势态评估和当前状态转变.按照DES理论，整个系统可以看成一个被控对象和监控器，前者是真实系统，可以用有限状态自动机或形式语言加以描述.监控器控制系统中事件的发生，因而使对象跟随期望的状态序列直到目标状态.IRASO中，事件由Agent报告，而期望状态改变可以描述成图5所示的状态变迁图.在通常情况下，机器人可以成功地根据状态变迁图到达最终目标.图5只是原则上描述了控制过程，实际执行模型更加细化.调度器模型用规则库系统实现并考虑了更多的细节.图6是图5中的分叉转弯状态的详细描述.下面是它的解释.

　　　　
图5　调度器模型

　　　　
图6　状态“分叉”的详细描述
　　（1）子状态BT1：警告前方区域可能有分叉道路
　　原因：由全局监控Agent比较机器人当前位置和地图知识，得到事件“进入分叉区”.
　　结果：
　　　　①驾驶命令Agent：发出减速命令；
　　　　②道路检测Agent：集中于道路形状，检查是否有分叉特征；
　　　　③路标检测Agent：被激活检查路标；
　　　　④全局监控Agent：从全局规划中得到全局路径.
　　（2）子状态BT2：检测出可能的分叉路类型
　　原因：道路检测Agent在BT1下发出事件“分叉路类型”.
　　结果：
　　　　①道路检测Agent：仍然集中于路边形状；
　　　　②路标检测Agent：仍然致力于发现路标.
　　（3）子状态BT3：确认车辆已进入分叉，准备转弯
　　原因：路标检测Agent在BT1或BT2状态时发现路标.
　　结果：
　　　　①全局监控Agent：输出全局道路给路径规划；
　　　　②路径规划Agent：作出跟随左(右)边的决定；
　　　　③道路检测Agent：转为集中于左(右)路边；
　　　　④全局监控Agent：进入半睡眠；
　　　　⑤路标检测Agent：进入睡眠.
　　（4）子状态BT4：左(右)转
　　原因；道路检测Agent在BT2或BT3下发出“分叉路类型”事件.
　　结果：
　　　　①道路检测Agent：仍然集中于路边；
　　　　②路径规划Agent：跟随左(右)路边.
　　如果道路检测Agent已经几次发现两条路边平行或全局监控Agent发现机器人已经出了分叉区，状态BT4将改变为路径跟踪.
　　由上可看出，事件、状态和行为相互制约，能够用基于规则的知识库系统方便表达.
4　仿真实现及结果
　　为了验证IRASO的正确性，我们用多台计算机组成“软机器人”进行仿真.仿真实验在由多台PC微机，SGI和SUN工作站组成的网络上完成，操作系统主要有Windows NT和Unix两种，基于TCP／IP协议的联通域Robix使所有的计算机工作在一个统一的逻辑计算环境中.为了保证各计算机的计算均衡，优化网络负载，提高通信速度，将不同Agent按照处理机的效率分布：道路检测和障碍检测两个Agent运行在微机上，SGI工作站上运行的Agent有驾驶命令，移动及全局监控，同时还有一个实时采集各Agent数据的监视Agent，而公告板，融合和路径规划Agent则运行在SUN工作站上.为了仿真的简单起见，还有一些Agent(如路标识别等Agent)没有实现，但已有的Agent足以说明体系结构的问题.首先由全局规划生成一条从起始位置到目的地的全局路径.在机器人行驶过程中，道路检测和障碍检测Agent负责采集前方道路信息，融合Agent根据视觉数据生成局部地图，规划Agent根据局部地图规划局部路径，控制Agent生成驾驶命令送给移动Agent.为了分析仿真结果，所有Agent的处理结果都送给监视Agent.公告板根据Agent所报告的事件作出势态评估，确定当前总体状态，协调各个Agent的运行.仿真结果见图7.


图7　仿真结果
　　在仿真中，道路的宽度设为12m，摄像机的有效范围为40m×40m.在直道行驶时，机器人的最大速度为40kmh-1，而在分叉行驶时机器人的速度为15kmh-1.从图7中可以看出，在直道行驶时机器人的速度明显比分叉行驶时快.根据3.1节的讨论，分叉状态是公告板根据道路检测和全局监控所报告的事件而得到的，在黑板收到这些事件后马上通知控制Agent减速，同时全局监控Agent将全局道路输出给规划Agent，向正确的方向行驶，车辆的及时减速对正确分叉有很大的帮助.
5　结论
　　IRASO体系结构中，公告板、调度器模型起了关键作用.从仿真结果知IRASO有如下特点：
　　(1)该模式在智能和效率之间有较好的平衡.Agent根据不同的环境和势态动态配置，在简单势态时，安排紧缩配置实现快速驾驶，用复杂的组织处理复杂的环境；
　　(2)调度器以DES理论的事件-状态转变为知识模型，通过精确推理得到合理状态，保证任何环境下Agent组织的正确性.
　　IRASO是基于多 Agent系统的柔性自组织体系结构，采用分布式智能系统解决动态复杂势态评估和快速反应的难题.中心公告板实现势态评估和多Agent的协调，在公告板的协调下，对于不同的势态，Agent能柔性重组，形成不同的车辆行为.和其它体系结构相比，IRASO有精确推理和反应快速的特点.
　　仿真结果表明IRASO在高层智能和快速反应上都达到期望特性，通过仿真同时发现IRASO允许自主机器人运行在大多数地形中，如高速公路，普通道路和越野行驶.■
基金项目：本课题得到国防科工委“九五”攻关项目基金资助.
作者简介：朱淼良，男，1946年2月生，教授，博士生导师，主要研究方向为人工智能、计算　　　　　　机视觉、智能机器人.
　　　　　张新晖，男，1970年12月生，博士研究生，主要研究方向为分布式实时智能系统、　　　　　　智能机器人.
　　　　　吴春明，男，1967年6月生，博士，副教授，主要研究方向为人工智能、智能机器人.
　　　　　钱徽，男，1974年11月生，博士研究生，主要研究方向为人工智能、图像处理.
作者单位：朱淼良(浙江大学人工智能研究所　杭州　310027)
　　　　　张新晖(浙江大学人工智能研究所　杭州　310027)
　　　　　吴春明(浙江大学人工智能研究所　杭州　310027)
　　　　　钱徽(浙江大学人工智能研究所　杭州　310027)
参考文献：
［1］Albus J, McCain H, Lumia R. NASA/NAS standard reference model for telerobot control system architecture(NASREM), NBS Tech Note l235. 1987
［2］Brooks R. A robust layered control system for a mobile robot.IEEE Journal of Robotics and Automation(Series A),1986,2(1):14～23
［3］Chun W H, Jochem T M. Unmanned Ground Vehicle Demo II: Demonstration A. In: Proc of SPIE Mobile Robot IX, SPIE Press，1995, 180～191
［4］Liscano R et al. Using a blackboard to integrate multiple actives and achieve strategic reasoning for mobile navigation. IEEE Expert, 1995, 10(2): 24～36
［5］Rosenblatt J D. A distributed architecture for mobile navigation. In: Proc of AAAI Sympo on LLISAPA, AAAI Press, 1995
［6］Ramadge P J, Wonham W M. The control of discrete event systems. Proc of IEEE，1989, 77(1): 81～98
收稿日期：1998-12-02
修稿日期：1999-03-29
