基于多Agent机器人系统的图书归类解决方案

摘 要：现代图书馆的藏书量已成为衡量一个图书馆水平的重要指标之一，而藏书量的增多也意味着图书馆日常管理任务的加重，图书管理人员要耗费巨大的精力去归类、整理图书。移动机器人和多Agent 技术的迅猛发展给这个亟待解决的问题带来了一种新的、可能的解决途径。我们提出一种基于多Agent 技术的机器人软件实现模型，该机器人能自动识别、归类图书，并通过改进BUG 算法导航适宜的行走路线，快速、准确地完成图书馆大量书籍的分类整理工作，极大地简化了传统的人工操作，减轻了管理人员繁重的重复性劳动。

　　随着科学的进步，现代图书馆的藏书量和报刊杂志的种类急剧增加。随之而来的日益繁重的管理任务，仅凭传统的人工操作，不仅耗费越来越多的人力、物力、财力，也降低了图书管理工作的可靠性，特别是有些读者借了多本书后隔天就马上归还，这无形中加重了图书馆理人员的劳动量，因而，让机器代替人类实现图书馆管理的工作是图书馆管理的必然发展趋势。

　　智能机器人是一类能够通过传感器感知环境和自身状态，实现在有障碍物的环境中面向目标的自主运动，从而完成一定作业功能的机器人系统。近年来，机器人技术在工业、农业、航天及空间探测等许多领域都起到了重要的作用，同时又显示了广泛的应用前景，成为人工智能学术界研究和关注的热点问题。而Agent 是处在某个环境中的计算机系统，该系统有能力在这个环境中自主行动以实现其设计目标。多Agent 系统是多个可运作的Agent 的有机结合，通过多Agent 之间的交互将一个复杂的问题简单化。

　　将多Agent 技术应用于移动机器人中使得机器人具有更高的智能性，实现自动感知环境变化、智能识别、归类、传送图书，让机器完成重复、繁重的体力劳动，减轻了图书馆工作人员的工作压力，实现图书馆的智能化。

　　1 Agent与多Agent的机器人系统基本理论

　　1.1 Agent 理论

　　在人工智能研究的进程中，研究者们逐渐认识到应该把人工智能各个领域的研究成果集成为一个具有智能行为概念的"人",更重要的是人们认识到了人类智能的本质是一种社会性的智能，人类绝大部分的活动都涉及多个人构成的社会团体，大型复杂问题的求解需要多个专业人员或组织协作完成。人最重要的和最多的智能是在由众多个体构成的社会中进行各种活动时体现出来的。"协作"、"竞争"、"谈判"等等是人类智能行为的主要表现形式。要对社会性的智能进行研究，构成社会的基本构件"人"的对应物"Agent"理所当然地就成为人工智能研究的基本对象。

　　一般认为，Agent 是一种处于一定环境下包装的计算机系统，为了实现设计目的，它能在那种环境下灵活地、自主地活动。虽然目前还没有一个大家都能接受的关于Agent 的定义，但几乎所有被称为Agent的软件或硬件系统都具有以下的特征： 自治性（Autonomy ） 、社会性（Social Ability） 、反应性（Reactivity）、主动性（Proactivity）、智能性（Intelligence ）、合作性（Collaboration）。

　　1.2 基于多Agent 的机器人系统及其任务模型

　　多机器人系统并非一个简单的多机器人组合系统，而是一个以分布式人工智能为指导，结合计算机、分布式控制、多传感器技术和理论，将多个机器人组织而成的分布式智能系统。多机器人系统在系统功能、并行性、柔性、稳定性以及容错性等方面具有单机器人系统不可比拟的优势，其正得到深入研究和广泛应用。多个机器人在共同的复杂环境中协同工作时，不仅和环境之间有复杂的交互作用，而且相互之间既有分工又有协作，既有合作又有竞争。多机器人系统的研究存在许多与单机器人系统所不同的问题：（1）如何在各机器人间表达、描述问题，分解和分配任务；（2）如何使机器人间相互通讯和相互作用；（3）如何保证各机器人行为协调一致；（4）机器人间如何识别和解决冲突等等。

　　这些问题主要涉及分布式问题的求解，用传统的集中控制理论和机器人理论已难以解决。当前MAS理论的发展及其在分布式系统中的应用给多机器人系统的研究带来了新的思路，并已在一些试验系统的开发中得到了验证。

　　1.3 机器人Agent 的任务模型

　　机器人的行为总是带有一定目的性，即与一定的任务或任务目标相联系任务目标。根据其是抽象的还是具体的，可分为隐式任务和显式任务两类：隐式任务一般是指可用自然语言描述的，没有明确数学形式的"抽象"任务，例如，"将图书放到书柜上",或"放到推车".显式任务则一般是具有精确的数学形式描述或量化指标的"具体"任务，如"移动到目标点（3, 7）",或"保持加工精度为土0. 003mm ".可以看到，隐式任务一般是高层任务指令，而显式任务一般是底层具体任务。隐式任务需要结合环境信息以及机器人的自身状态，转化为显示任务序列加以实现。以机器人取书为例，假设机器人位置为（5, 8},书位置为（32, 36），推车位置为（67, 57）。"将书放入推车"为隐式任务目标，其可分解为显示任务目标序列："移动到位置点（32,36）","夹持位置点在（32, 36）的书","移动到位置点（67,57）","放置书到位置点在（67, 57）的推车".一般而言，机器人Agent 的任务可用下式表示：

　　Task=（Goal,Precondition,Body,Effects,Setting）

　　其中Goal 表示任务task 的目标，一般可用自然语言描述；Precondition 表示任务task 实现所需的前提条件；Body 表示任务task 的子任务序列或显式目标序列；Setting 表示任务task 的附加约束条件集；Effects 表示任务task 实现后对环境的效果集。

　　隐式任务在分解转化为显式任务时，也可能生成某些中间隐式任务，从而形成机器人任务分解的一种与/或树结构。其中"与"表示上层任务目标通过实现所有下层任务目标才能完成，"或"表示上层任务目标可通过选择实现下层的某个任务目标加以完成。一般而言，树状结构的最底层分支的端点都是机器人可直接执行的显式任务目标，并且是"与"树结构，即显示任务目标序列。

　　2 基于多Agent的机器人系统的体系设计

　　2.1 环境设置

　　本系统为了便于机器人识别，将图书馆中所有的书柜用阿拉伯数字进行编号，即每一书柜对应相应的标签编码段，跟图书馆中每个柜上设置放置的图书数目一致，并将其存入规则库中。推车设计成具有若干个格子，且设定每个格子只放一本书，便于机器人区分某本书的在推车上的具体位置，推车上的格子也以阿拉伯数字标识，便于机器人存储、记忆。

　　2.2 系统结构

　　本系统利用多Agent 系统减轻人工分类、摆放图书的工作量，其工作流程如图1 所示：

图1 系统体系结构。

（1）当机器人的机械手拿一本图书时，机器手上的自动识别系统即带有传感器的环境识别Agent 立即感知环境变化，且获取图书条形码信息，并将这些信息传递给图书识别Agent.这一过程主要是实现从环境状态（E）到感知（Per）的映射（函数see 的输出是一种感知，即感知的输入）：see : E--> Per.

　　（2）信息库包括了图书信息的集合和图书馆的电子地图，存储着所有图书条形码的信息、书名及其图书标签和图书馆电子地图。通过传感器识别出条形码，图书识别Agent 接收条形码信息，将信息分解，并跟信息库中已有的条形码进行模式匹配，找到符合的样本，返回图书的基本信息，用函数book（馆号，条形码，条形码号，书名，标签）表示，其中标签指的是在图书馆里的位置编码，分为2 大部分，前一部分字母遵循中国图书馆图书分类法，指出图书的类别，而后一部分则为每个图书馆各自的编码方式，存储着每本图书在馆内的具体位置。并将这个函数传递给图书归类Agent.

　　（3）规则库是规则的集合，存储着中国图书馆图书分类法及本地图书馆子规则。

　　图书归类Agent 接收函数book,将对应的标签跟规则库中的规则进行比较得到图书在馆中的位置，并将其分解为某类图书的某个具体书柜，用函数position（编码号，书柜号）将位置函数传递给动作Agent.

　　（4）动作选择函数获得推理结果实现从内部状态到动作（Ac）的映射：action:I--> Ac.动作Agent将图书放入推车的空格子中，并在临时库中记录每本书的书柜号和推车格号，同一书柜号的图书可以记录在一条记录中，在原先记录尾部追加其推车格号即可，那么机器人可将推车中同一个书柜的图书一次性摆放，不需下次折回。临时库见表1 所示。

表1 临时库表一

　　（5）当推车上的格子都摆满后，动作Agent 传递消息给智能决策Agent 图书已摆满，则智能决策Agent查看临时库中的各个书柜号，根据信息库中已存储的图书馆的电子地图即各个书柜的摆放次序利用改进BUG 算法计算出各个目的地的优先次序和机器人的行走路径，并指导动作Agent 到各个目的地完成摆书操作，最后回到还书处等待下一次的摆书动作。

　　3 关键算法分析

　　3.1 图书归类

　　依据图书馆给图书分类编码的标准，参照中国图书馆图书分类法，因为国家图书馆图书分类法，从首字符可以分出大的图书所属类别，从一级类别中再细分，部分首字符，例如：E、U、V 就代表一类，不需要再细分，而有些要细分出来，则需要首四位字符的判断才能分析出来，更特别的是审计类编码规则，要有前六位才可以分辨出来。据此我们设计图书分类编码，共12 位，由26 个大写字母和十个数字0~9 组成，前四位代表图书的类别，如果按照中国图书馆分类法，字符不足四位的用通用字符*补足，例如：U 代表交通运输类，一本书的分类编码前四位可以设计为U***;TP1 代表自动化基础理论，该类别一本书的分类编码前四位可以设计为：TP1*,后8 位按照各个不同图书馆的不同要求进行编码，从而根据类别和后八位的编码确定某本书所在的码段，接着确定具体的位置和所在柜。

　　我们根据该编码规则来设计图书分类规则库。我们设计四个子规则库：

　　唯一字符规则库：

　　r1: IF 第一个字符是U/E/P/Q/R/V THEN 该本书是所对应的某一大类。

　　两个字符规则库：

　　r1: IF 第一个字符是某个字母 THEN 该本书是某种一级类；

　　r2: IF 第二个字符是某个字母或数字 THEN 该本书是二级类；

　　三个字符规则库：

　　r1: IF 第一个字符是某个字母 THEN 该本书是某种一级类；

　　r2: IF 第二个字符是某个字母或数字 THEN该本书是某二级类；

　　r3: IF 第三个字符是某个字母或数字 THEN该本书是某三级类；

　　四个字符规则库：

　　r41: IF 第一个字符是某个字母 THEN 该本书是某种一级类；

　　r42: IF 第二个字符是某个字母或数字 THEN该本书是某二级类；

　　r43: IF 第三个字符是某个字母或数字 THEN该本书是某三级类；

　　r44: IF 第四个字符是某个字母或数字 THEN该本书是某四级类；

　　r45: IF 第五字符是点 THEN 根据前四位已判断类别和后8 位字符的范围找到该书相应的柜子的编码 AND 跳出规则库；

　　ELSE 第五个字符是某个字母或数字 THEN该S 本书是某五级类；

　　r46: IF 第6 个字符是点 THEN 根据前五位已判断类别和后7 字符的范围找到该书相应的柜子的编码 AND 跳出规则库；

　　根据上述规则库我们给出编码和对应书柜编号的识别通用算法如下：

　　If（第二个字符=*）

　　{ 转入唯一字符规则库；

　　根据该类别和后8 位字符的范围找到该书相应书柜的编码；}

　　Else if（第三个字符=*）

　　{ 转入两个字符规则库；

　　根据该类别和后8 位字符的范围找到该书相应书柜的编码 ;}

　　Else if（第四个字符=*）

　　{ 转入三个字符规则库

　　根据该类别和后8 位字符的范围找到该书相应书柜的编码 ;}

　　Else 转入四个字符规则库；

　　我们以一个例子具体说明编码规则：

　　假设某一高校图书馆给出非审计类8 位的编码规则是，对于U 类书籍，编码范围U***00000000-U***00000200 内的书籍放在1 号柜。我们对一本编码为U***00000023 使用本文所述的分类算法进行分类。首先，判断第二位字符，根据算法第二位是*,转入唯一字符规则库，首先根据规则r11,判断出该本书是交通运输类，结合后八位0000023,该编码在U***0000000-U***0000200 范围内，判断出该书所在的位置为1 号柜。

3.2 智能寻线导航

　　所谓路径规划是指移动机器人按照某一性能指标（如距离、时间、能量等）搜索一条从起始状态到目标状态的最优或次优路径。路径规划主要涉及的问题包括：

　　利用获得的移动机器人环境信息建立较为合理的模型，再用某种算法寻找一条从起始状态到目标状态的最优或近似最优的无碰撞路径；能够处理环境模型中的不确定因素和路径跟踪中出现的误差，使外界物体对机器人的影响降到最小；如何利用已知的所有信息来引导机器人的动作，从而得到相对更优的行为决策。

　　路径规划是移动机器人研究中的一个基本且重要的问题。路径规划的第一步是确定地图的表示方法，其目的是将机器人和障碍物所在的物理空间的显著特征描述出来，使之更适合于规划。本文中将地图置于信息库中，智能决策Agent 根据临时库中的各个目的地在电子地图中的位置，确定物体或自身的位姿（位置和姿态），制订出他们的优先次序。

　　由于机器人工作的环境是动态变化的，环境中的障碍物不全是已知的、静止的。这就要求机器人要不断地对周围环境进行探测，并对探测到的障碍物进行实时处理，即要求机器人具备局部规划的能力。机器人在运行过程中，通常会发生如下几种类型的冲突：

　　碰撞、拥塞以及死锁。

　　碰撞：一个运动物体在另一个运动物体运行路线上的相同位置同时出现。拥塞：其它运动物体妨碍当前运动物体按要求到达目标。死锁：运动物体无法进行各自的下一步动作。这些冲突的产生主要是由于机器人对环境信息缺乏详细了解造成的。因此，当环境动态变化时，往往采用依赖传感器的局部路径规划方法进行冲突消解。

　　由于本文中设计的机器人个数比较少，就将环境中其他机器人视为环境中的障碍物，而且环境比较简单，因而采用无通讯的避碰力一法的机器人，不需要与其他机器人的通讯，完全依靠机器人的传感器获取其他机器人的运动信息。

　　本文采用改进BUG 算法计算两点间的最短路径，即计算出离当前点路径最短的目标点，具体算法如下：

　　根据电子地图，智能策略Agent 初步给出各个目的点的优先次序及其行走路线，但是实际行走中还可以会遇到其他不可预知的障碍，这里改进BUG 算法考虑到了这些因素，具体算法如下：

　　S=起始点，T=终点

　　设M 为空矩阵，i=1; V（1）为空集

　　MAP_R 为与矩阵M 对应的二维位图，Pi 为机器人在地图中的即时位置

　　While（T<>Pi） //当T==Pi 表示机器人到达终点

　　{ V（i<--由EPC 方式采集的数据） // EPC 为端点采集法

　　M<--M∪V（i）

　　位图MAP_R 随之不断更新

　　IF（线段Pi T 和障碍物边界相交） THEN

　　由COD 计算出方向 // COD 为最近方向判决

　　ELSE

　　机器人沿方向移动到点Pi+1

　　i++;}

　　3.3 动作选择

　　根据内部状态的变化，动作Agent 指导机器人该采取什么样的动作，具体流程如下：

　　IF（传感器感知到有书到来）THEN 触发机械手拿书

　　ELSE

　　IF（图书归类完成） THEN

　　{ 触发机器手将书放置在推车格子中，并将临时库中的已满格子数加1;

　　IF（已满格子数==总格子数） THEN 机器人不再接收其他图书，触发机器人根据智能策略Agent

　　提供的路线推动推车向各个目的地前进。}

　　FOR（i=1;i<=临时库中的总目的地数；i++）

　　{ IF（到达临时库中记录的第i 个目的地）THEN

　　{ 机器人停止行走，触发机械手将对应图书摆在相关的柜子上

　　摆书动作完成，停止机械手动作，触发机器人推车向着新目的地前行 }

　　ELSE 继续根据路径前行 }

　　3.4 多Agent 之间的通信

　　当环境变化的时候，环境感知Agent 会自动检测到环境状态，比如有新书到时，环境感知Agent 获取图书信息，并向图书识别Agent 提出合作请求，且将图书信息传递给它，环境感知Agent 继续检测环境变化。Agent 之间的合作提高了工作效率和准确度，且保证了库中信息的有效共享，避免资源浪费。

　　Agent 之间的交互与合作是多Agent 系统中核心问题之一，而Agent 通信语言是实现交互与合作的基础。根据目前Agent 的应用环境， KQML 是主流的通信语言之一。因KQML 既是一种通信语言，又是一种通信协议和标准，故每个Agent 只要遵守该协议，即可受到它所提供的通信支持，若要遵守协议，每个Agent 必须添加一个KQML 语言解释器。

　　概念上，可以把一条KQML 消息分为三层：内容层、通信层和消息层。内容层由关键词：content 标志；:reply-with, : sender, and : receiver 关键词标志了通信层； :performative 与：language, : ontology 形成消息层。全部技术通信参数都在通信层规定，消息层规定与消息有关的言语行为的类型，内容层规定消息内容。以环境感知Agent 与图书识别Agent 之间的沟通为例说明KQML通信语言的方法。

　　（tell

　　: sender 环境感知Agent

　　: receiver 图书识别Agent

　　: reply-with information storehouse

　　: content （new book's information）

　　: language java

　　: ontology bar code of book）

　　4 结语

　　本文中我们在图书馆管理系统中引入人工智能的概念，并给出了基于多Agent 的机器人系统在图书归类中的模型。智能机器人能自动识别图书条形码，且结合中国图书馆图书分类法给出归类算法。根据此算法可计算出图书的具体位置，将所有推车中同类书籍进行关联，机器人就可以一次性摆放所有同类书籍，而不需要多次折回，实现对图书的归类。改进BUG 算法给出了路径规划方案，指导机器人沿着路径正确、快捷地找到各个目的地。通过机器人和多Agent 技术的结合，极大地提高了图书管理的效率，减轻了工作人员繁重的整理工作，对将人工智能技术引入日常生活中产生深远的现实意义。