合作者:非完整可替换主体在动态环境中团队的任务

文摘

在我们之前的工作中,我们提出了一个潜在的实地混合路径规划方案达到完全覆盖在不同任务的机器人导航。本文是这项工作的延伸产生一个可替换主体框架,合作者,集成了一个高层negotiation-based任务分配协议底层路径规划方法考虑几个真实的机器人非完整约束等局限性。具体地说,拟议的框架的重点是一类复杂的运动规划问题,机器人需要覆盖整个工作区,协调任务的完成,并动态地改变他们的角色最适合这个任务。应用于这类问题包括炸弹检测和删除以及抢救事故或灾难的幸存者。我们已经测试了该框架在模拟几个任务和表明,合作者可以满足非完整约束,合作完成给定任务的最初未知的动态环境中,同时避免碰撞与其他团队成员。最后,我们证明了该控制律使用李雅普诺夫稳定性理论是稳定的。

1。介绍

在机器人运动规划是一项基本和重要的问题。一种特殊类型的路径规划包括任务如排雷[1)和后寻找受害者的悲剧,这是非常重要的工作,需要完全覆盖的过程中探索。如果时间允许,机器人团队应该进行一次彻底的搜索和覆盖每平方英尺的工作区。虽然覆盖太多的关注不是一个领域,覆盖不足可能导致灾难性的后果。类似的标准适用于许多其他机器人应用,如真空机器人和地雷检测。在一些更复杂的场景中,机器人常常被其他任务。例如,在炸弹检测和删除等工作(2)、救助幸存者的事故或灾害(3),搜索是典型的模式。然而当一个机器人发现一个对象,比如一个幸存者,其搜索阶段是停顿了一下,然后参加救援任务。它只能搜索营救任务完成后恢复。这些任务需要某种形式的角色的变化如从救援搜索转变为成功地完成他们的任务。此外当任务不能通过一个机器人,协调或任务分配问题。在这种情况下,机器人可以协商解决问题和分配任务。

运动的机器人文学包含许多这类任务的规划策略使用神经网络,模糊逻辑,近似细胞分解,准确的细胞分解,和人工潜在的领域。之前大部分工作集中在高级任务分配或低级任务执行。一些作品把任务分配和基于势场的运动计划提供一个整体的解决方案。帕克(2]提供了一个基于行为的体系结构,促进容错:体系结构的有效性证明通过一组移动机器人执行危险废物清理实验室的版本。Gerkey和马塔里奇(4)提出了一种基于拍卖的任务分配,可以实现分布式近似全局最优资源使用。工作的主要贡献是经验表明,分布式协商机制是可行的和有效的协调一个物理multirobot团队。(5]表明,协调反应的机器人可以通过本地交互的开发;然而,它基本上仍在任务分配,不传播任务执行的水平。在我们以前的工作,提出了一种新颖的混合导航方案可替换主体团队目标之间的桥梁高级任务的协调和低级路径规划(6]。这项工作没有关注底层路径规划,认为理想的工作条件,不考虑移动障碍和非完整约束。然而,这些方面的低级路径规划是一个物理实现的关键。在真实的工作环境中,移动障碍往往是不可避免的。例如,清洁机器人常常发现自己在他们需要的情况下避免碰撞与人要对自己的业务。此外,与模拟机器人不同的是,许多物理机器人只能向前或向后移动,受非完整约束,类似于汽车。在本文中,我们扩展我们的以前的结果更现实的环境同时考虑每个单一的约束和限制。

对于一个复杂的系统,如前所述,核心目标是实现系统的稳定性。系统被认为是稳定收敛全局最小值发生时,只能实现在整个任务完成。机器人通常需要在一个工作环境是动态的,嘈杂的和不可预测的。然而,他们应该可靠的完成任务的能力,尽管所有的干扰包括移动障碍的干预。这保证收敛等关键任务是必要的灾后救助受害者。稳定单一代理导航在静态环境中可以通过构建一个简单的李雅普诺夫函数。然而,多重代理团队稳定在动态环境中导航本质上是更困难的主要原因是代理之间的交互和移动障碍的存在。在本文中,我们提出一个合作混合使用模式特定导航方案和构建一个团队李雅普诺夫函数,表明系统稳定在任何时候通过使用参数从混合动力系统理论和李雅普诺夫稳定性理论。

剩下的论文分为若干部分,解决这个问题的各个方面。节2我们描述分级代理的设计,是这项工作的基础。部分3提出了一个潜在的实地混合导航方案。节4运动控制律是派生、部分5框架扩展到移动的环境障碍。部分6在代理的设计包含了非完整约束,而部分7考虑了机器人的非完整约束和运动障碍。部分8提出了仿真结果multirobot系统受非完整约束在动态环境中。节9团队稳定性进行了分析。最后一节10,我们做总结并讨论未来的研究方向。

2。代理设计

这项工作中使用的多层代理体系结构如图1。每个机器人的团队使用相同的架构和团队没有集中控制。最高水平的任务协调或知识水平。在这个阶段的抽象,代理分析和管理任务使用一个固有的协调机制。中间水平需要路径规划,代理人选择合适的导航功能,追求理想的目标基于知识的积累或团队决策。最后,与一个驱动器和传感器的最低水平管理运动控制。

我们的代理团队完全分散,没有领袖或协调员团队和每个代理分析,使自主导航和协调决策基于自己的知识世界。这个设计本质上是容错,易于配置的任务需求变更(6]。

我们以前的工作详细描述了代理体系结构,以及它是如何用于完成高级任务(6]。这里我们提供一个简要的描述其主要组件以及它们如何协助低级路径规划。一个代理的体系结构由四个层次层:决策(DM),知识库(KBase),交互和沟通。在下面的文章中,我们定义每一层的功能以及各层之间的接口。对于每一个层,控制软件是多线程的,每个主要对象运行在它自己的线程。

的决策(DM)层是系统中智能的主要来源。它执行导航规划基于中存储的信息知识库使用混合方法中描述(6]。在任何时候一个机器人可以在一组有限的模式之一,它代表高级导航目标。基于规则的系统是用来之间的过渡模式基于任务的当前状态。低级的模式定义导航目标路径规划系统。

的知识库包含代理的最新知识世界地图,“集团知识”以及协调的推理规则。这些信息包括所有已知的障碍的位置和任何目标。中的信息知识库建立机器人的的经验,加上其他机器人的沟通。

设备的协调层,在讨论7)独立的交互任务的主要周期运动规划的任务。代理之间的交互执行使用一个明确的通信协议(7]。我们定义接口之间的交互设备和知识库和沟通层。在交互层,设备执行协调以及其他交互任务,并将结果存储在知识库,没有干扰常规决策。结果,这是一个简单的问题,必要时添加新的交互设备的新应用程序。

总之,更高层次的体系结构提供的障碍物和目标的位置低的输入路径规划系统。更高水平确保整个空间搜索和所有的任务完成,而低层次处理导航机器人从当前位置到目标位置。

3所示。潜在的实地导航方案

局部最小自由势场可以用广义球形构造潜在函数或调和函数(8]。在这篇文章中,我们使用一个二维广义高斯函数更容易构建的障碍和更有效的保护领域可以写姓名住址没有重叠的圆圈。

有吸引力的对象集中在由负高斯吗吸引子功能:

令人厌恶的障碍和其他代理为中心与圆形建模,二维广义高斯吗repulsor功能:

对于一些正整数。方差,的大小,是衡量障碍。的参数决定了有效范围(陡度)的障碍,可以不同的修改障碍的排斥效应。我们代表障碍写姓名住址圆的形状。

通过指定一个障碍之间的最小间隙和高度本地化的障碍的影响通过修改参数、广义高斯函数建模可以用来构建潜在的不受欢迎的局部最小值字段,是免费的。图2(一个)使用一个小有局部最小值之间的障碍,通过改变更大的值,从而高度本地化的障碍的影响,局部最小值在图消失2 (b)。

在[6),我们提出了一个模式切换技术,模式切换基于事件如unsearched部门减少和发现对象的数量/障碍增加。使用人工的技术潜在的领域,我们构造一个导航功能,为代理在模式下(可以是任何上面定义的模式)。构建导航功能对于一个给定的模式中,我们使用三个部分公式:

在(3),代表对代理的影响的总和所有的在模式系统的吸引子,因此

代表对代理的影响的总和系统中所有已知的静态障碍物的模式。已知的静态障碍物的数量;这是我们可以状态

最后,函数代表repulsor双代理之间的功能和。请注意,不是模式依赖,因为数量的代理是假定为常数。因此,在一般情况下

4所示。运动控制律

使用人工的技术潜在的领域,我们构造一个导航功能,为每一个代理在模式下(可以是任何上面定义的模式)。每个代理的(mode-dependent)运动学是由:

在(7),运营商代表的梯度只对。因此,我们使用梯度下降法来生成一个单位向量方向和恒定速度参数确定代理的速度。我们使用一个单位梯度自Gaussian-like潜在函数衰减很快。

注意,梯度的方法使对目标运动的方向,但这种运动的速度,为代表机器人设计的,是一个函数。也就是说,每个机器人都有一个最大速度,必须占的导航系统。

5。扩展和移动环境障碍

移动机器人避障是非常重要的研究和天生就比只处理静态障碍。许多工作都致力于这个问题(9- - - - - -12]。文学中最相关工作提出了埃斯波西托和库马尔(12]。工作,埃斯波西托和Kumar提出一种非线性规划方法计算移动机器人最优可行的方向。沿着可行方向相反的负梯度方向,机器人可以成功避开所有障碍,同时保持一个稳定的移动轨迹。换句话说,最优方向减少了势函数值最快在可行方向。它不是最优的最短时间或距离。尽管这方法的有效性在许多情况下,它可能无法收敛一些步骤,尤其是在移动障碍的数量增加的情况下(即。非线性约束,更需要考虑)。也该方法计算昂贵由于迭代优化过程中(请参阅[13])。

我们的算法使用几何变换来解决移动避障问题。埃斯波西托和Kumar相似,该算法实现避障运动通过寻找最佳可行解决方案。然而,没有近似方法,只有几种几何转换甚至为最复杂的场景;所以它可以用更少的计算实现准确的解决方案。更重要的是,该方法可以保证当有一个找到一个最佳的解决方案。

该方法的另一个优点是,它更容易把算法融入各种运动规划算法。例如,我们将出现在部分7,该算法可以很容易地纳入非完整机器人的运动规划14),实现避障。

我们与每个移动障碍动态约束(12)以下的形式:

在哪里运动障碍的位置吗,机器人之间的最小安全距离和运动障碍。

当远离机器人移动障碍,他们忽略的规划算法。当阈值内的机器人移动的距离成为制约移动障碍,激活,和机器人沿着可行的运动方向。如果路径是完全被障碍(静态和移动),机器人就会停止,直到清除,这是使用相同的策略,在15]。

在移动环境中避障,可行的运动方向用是方向,可以稳定系统和移动机器人远离激活移动障碍,从而满足下列条件:

在哪里代表了约束的梯度和导航函数的负梯度方向吗的机器人。在(9),我们需要任何控制系统可以稳定积极的投影(朝着我们的目标)。在(10)我们需要任何控制移动机器人的移动障碍有积极的投影(远离移动障碍)。

定理1。可行的运动方向设置只能使用机器人来构造梯度移动导航功能和约束的障碍。(请参阅附录的证据。)

在我们的设置中,机器人将沿着最优可行方向计算构造可行集的最优方向的,它是最接近负梯度方向。我们稍后将显示在这一节中,由此产生的运动方向的优化方法是一样的12优化方法收敛时)。回想一下,一组是一组可行的方向在以下形式的旋转角度对负梯度方向。从基本的几何(参考图13),我们可以看到,如果没有可行的解决方案。如果存在一个可行的解决方案在可行的设置呢是最优可行的梯度方向,否则最优可行的梯度方向可以通过旋转与最小可行方向设置旋转。

如果我们使用表示最佳的旋转角度,下面的公式是由

我们定义的最优可行的梯度方向是 的旋转矩阵是下面的形式:

然后给出了控制律

在图3,我们说明了该算法在一个典型的目标达成的任务。机器人需要达到目标,同时避免运动障碍。

在图4,我们的结果表明,该方法是最优化方法的相同12优化方法收敛时)。图4显示了直方图的轨迹优化方法和该方法在这两个之间的差异和方向,我们可以看到不同的顺序,这并不重要。

该算法计算起来更有效的优化方法。我们使用移动障碍与随机生成的位置和运行程序50次(完全350步)简单的场景如图3,平均迭代次数高于5优化方法,我们知道,当涉及到一些复杂的场景中,迭代的数量将大幅增加。然而,该算法总是计算的复杂性,所以至少5倍的平均优化方法。

6。非完整机器人

我们考虑本文的非完整机器人Hilare类型移动机器人,具有最典型的中性约束。这个机器人有两个平行的车轮可以独立控制。通过指挥这两个轮子的速度相同,机器人直线移动。通过指挥速度大小相同,但方向相反的方向,机器人对其轴轴心。中性约束力量移动机器人只有向前或向后移动。我们解决约束通过选择基于哪个向前或向后的方向有一个积极的投影梯度下降方向,然后更新标题尽可能快来匹配我们的梯度下降方向。如果我们假设它是一个运动系统,输入线速度和角速度。

我们定义的角度对应的负梯度的导航功能作为

和定义之间的角度负梯度和标题。在设置通过建设(请参考图5)。的角速度控制律

和的线速度控制律 在哪里和恒速参数和吗

图6(一)显示了该算法的有效性在多个避障任务。一个非完整机器人成功达到目标后横向的工作区挤满了不同大小的随机生成障碍。图6 (b)特写视图的图吗6(一)显示相当平滑运动机器人的障碍。

7所示。非完整约束和运动障碍

在本节中,我们考虑到运动控制问题受非完整约束和运动障碍。我们将首先找到一个可行的方向设置,这样各个方向在这个集合中可以移动机器人对目标,同时远离运动障碍。我们定义的最优可行方向的方向最近的可行集和梯度下降方向。如果机器人的前进方向是可行的,机器人将前进;如果机器人的向后方向是可行的,机器人将向后(注意,不能后退方向和前进方向的可行的设置在同一时间)。当这两个方向的可行集,机器人不会生成线速度但会对最优可行方向旋转。通过这种方式,机器人可以实现(考虑位置和方向)的目标,避免障碍同时移动。

如果我们使用表示最佳的旋转角度,下面的公式是由

(参考图13),我们定义可行的最速下降方向是

在哪里定义如下:

运动控制律
(mode-dependent)运动学的然后给每个代理 在哪里被定义为取向的角度最优可行方向: 的旋转矩阵被定义为 在哪里被定义为负梯度方向的旋转角吗实际运动方向(正向或反向方向)。请注意,我们需要在一组;机器人会向前前进方向是一个可行的方向,向后移动,如果向后方向是一个可行的方向。设置为零矩阵在正向和反向方向是可行的。在这种情况下,机器人不会有任何线速度。

图7显示的比较两个场景,第一个场景是达到目标的任务,没有障碍。第二个场景是目标与一个移动的障碍达成任务,总是每一步的机器人的运动。的数据,很明显,机器人可以达到目标的六个步骤,如果路线清晰,而需要80步的影响下移动的障碍。

图8显示了机器人运动的差异和不动障碍的任务静态避障。第一个图显示,机器人可以绕过静态障碍在60步骤,然而移动障碍,机器人在第二个图需要90步。

8。仿真结果

在本节中,我们展示了这个框架成功在一个典型的导航和协调任务:search-and-transport。我们已经在几个环境模拟代理执行团队。图9显示了一个典型的仿真的结果,在一个(代表网格包含6个静态障碍符号)和2(代表移动障碍符号)与一组3特工试图找到3小物体(由@符号)和三大对象(所代表的符号)。的符号也代表职位的大对象是捡起,和符号也代表职位小物体在哪里捡起。附近的实线移动障碍轨迹移动的障碍。机器人开始的位置,机器人开始的位置,机器人开始的位置。小的对象集合位置和大对象集合地点。

在图9,我们说明了search-and-transport任务。只有的轨迹显示在图(用虚线表示)9以减少混乱。

数据10 ()- - - - - -10 (c)是模拟的一部分。我们用它来说明之间的协调代理通过显示路径后面跟着三个代理和移动的障碍。代理的轨迹,,实线表示,分别dash-dot线,虚线。从这个图中,我们可以看到发现了一个大对象”“点,来帮助他们返回大对象回大对象集合一起的位置。发现了一个小对象在“@”点,并带着它回到小对象集合的位置。图也说明了所有代理商如何避免静态和运动障碍。

图11说明了我们的移动避障技术。当点移动障碍M所代表的符号,一个移动的避障算法纳入导航功能。总是沿着可行的方向,可以取得进步的目标,同时避免碰撞与障碍。

在图12我们说明我们的方法使用更复杂的场景。环境扩大从10×10到50 50。工作区是更多的集群和障碍有更大的规模和假设不同的形状。结果表明,本文给出的算法都不受到这些变化的影响。三个机器人仍然可以协调和完成search-and-transport任务。新工作区包含八个紧密放置静态障碍不同形状和两个移动的障碍(代表符号)。大对象的数量仍然是三个和小物体的数量增加到四个。在最后的场景中,实线附近的移动障碍的轨迹移动的障碍。机器人开始的位置,机器人开始的位置,机器人开始的位置。小的对象集合位置和大对象集合地点。

9。团队稳定性分析

模态导航功能的定义,我们的模式切换规则,允许我们显示系统(整个代理团队)是全局稳定的,在所有国家16]。

定义了模式切换技术(6),我们可以保证模式切换发生在有限时间如下。虽然模式切换的顺序事先无法预测,我们的切换技术保证了模式转换图无环因为模式切换只发生在整个团队取得了进展解决任务,没有一个给定的模式是进来。因此直接表明我们的混合动力系统的切换系统中定义(16]。

现在,我们只需要表明,本文提供的低级的路径规划方案是稳定的。

9.1。不稳定约束

在每一个模式,我们可以定义一个使用模式特定的李雅普诺夫函数形式如下:

的步骤(25)(26)是合理的,因为事实上。在这些方程是机器人的数量。

显示内部李雅普诺夫稳定性,我们被要求表演对所有和对所有。遵循自然的定义在(26)。表明总是减少,我们首先使用(25)。为了方便起见,在推导过程,我们已经取代了下列形式的条件以简短的形式:

现在,观察到只出现在通过项,第二项(27)可以写成

因此,第二个和第三个条件(27)将取消,我们会

如果我们的替代品使用动力学中定义(7),我们会有 我们将会有对所有是必需的。

备注1。构造李雅普诺夫函数是一个广义能量函数。第一项减少意味着代理接近流动。第二项减少意味着代理摆脱静态障碍。第三项减少意味着代理尽量远离其他团队成员。

9.2。稳定性受非完整约束

如果我们代入(29日)使用动力学中定义(17),我们会有

如果我们表示和

注意,通过建设,因此,我们将对所有是必需的。

9.3。与运动障碍

从(29日),我们有

如果我们的替代品使用动力学中定义(14),我们会有

根据可行方向的定义(指(9)),我们有对所有是必需的。

9.4。运动障碍和非完整约束

如果我们的替代品使用动力学中定义(23),我们会有

如果我们表示和

注意,通过建设,。因此,我们将对所有是必需的。

10。结论和未来的工作

在我们之前的工作中,我们提出了一个软件框架和一种混合导航方案多个代理导航和协调。然而,有几个未解决的问题在前面的工作。具体来说,机器人和环境是现实世界的抽象。例如,机器人有能力向各个方向和环境只包含固定障碍。在本文中,我们扩展我们的工作通过消除这些理想的特点,考虑机器人的挑战可能会遇到在现实世界中。特别是,我们建议geometric-based方法避免移动障碍和满足非完整约束。我们的方法适用于快速在线计算和他们彼此很容易结合来解决更复杂的问题,如非完整约束的移动障碍。此外,我们的控制框架适用于广泛的场景。我们演示了search-and-transport问题相互依赖关系的多重代理团队。这个框架,适用于更大范围的任务比本文所讨论的,由于我们的分层设计和完全分布式组织和因为我们的稳定性证明没有假设的性质的团队成员。

附录

证明。(为简单起见,我们把下标”我”,指的是我th机器人在本证明。)首先我们表示对应的角约束的梯度通过和定义如下: 在哪里。为了更好地说明我们的方法,我们代表所有方向以下形式的旋转角度与尊重。被定义为之间的角度和。我们这个角度定义为积极的如果一个逆时针旋转来和消极的,否则: 结果落在区间我们变换间隔由以下公式: 接下来,我们构建一套可行的方向每个激活的移动障碍: 注意,设置可行的方向为每个激活移动障碍约束的一个子集因为所有可行的方向必须躺在half-tangent飞机一样。接下来,我们找到的十字路口集的可行方向这适用于所有运动障碍: 通过建设,我们知道也是一个子集的。

引用

1. s . Hirose横田,a鸟居et al .,“四足步行机器人集中排雷TITAN-IX及其操作系统开发,”诉讼的IEEE机器人与自动化国际会议上' 05)举行(“国际机器人与自动化会议”卷,2005年,第1290 - 1284页,2005年。视图:出版商的网站|谷歌学术搜索
2. l·e·帕克,”联盟:一个容错multirobot合作架构,”IEEE机器人和自动化,14卷,不。2、220 - 240年,1998页。视图:谷歌学术搜索
3. 答:大卫,“城市搜救机器人:从悲剧到技术,”IEEE智能系统,17卷,不。2、81 - 83年,2002页。视图:出版商的网站|谷歌学术搜索
4. b . p . Gerkey和m·j·马塔里奇”出售!:auction methods for multirobot coordination,”IEEE机器人和自动化,18卷,不。5,758 - 768年,2002页。视图:出版商的网站|谷歌学术搜索
5. a . j . Ijspeert。马蒂努里,a .台球和l . m . Gambardella”通过剥削当地互动合作自主机器人:木棍拉实验,”自主机器人,11卷,不。2、149 - 171年,2001页。视图:出版商的网站|谷歌学术搜索
6. j . Ren k . McIsaac, r . v . Patel”小说混合导航方案可重构多代理团队,“机器人与自动化国际杂志》上,21卷,不。2、100 - 109年,2006页。视图:谷歌学术搜索
7. h . Ghenniwa和m·卡迈勒”交互设备协调合作的分布式系统智能自动化和软计算》第六卷,没有。3、173 - 184年,2000页。视图:谷歌学术搜索
8. J.-O。金和p·k·斯拉”,使用谐波潜在函数实时避障”,IEEE机器人和自动化,8卷,不。3、338 - 349年,1992页。视图:出版商的网站|谷歌学术搜索
9. n . Kiryati Kimmel r ., a . m . Bruckstein”多值距离地图运动规划在表面上移动障碍,”IEEE机器人和自动化,14卷,不。3、427 - 436年,1998页。视图:谷歌学术搜索
10. k》和h·萨梅特”分层路径规划策略在移动障碍,”IEEE机器人和自动化,5卷,不。1,第69 - 61页,1989。视图:出版商的网站|谷歌学术搜索
11. 康涅狄格州r . a和m .锦”,机器人运动规划在n维星世界中移动障碍,”IEEE机器人和自动化,14卷,不。2、320 - 325年,1998页。视图:谷歌学术搜索
12. j·m·埃斯波西托,诉Kumar的方法修改闭环运动计划来满足不可预知的动态约束在运行时,”诉讼的IEEE机器人与自动化国际会议的举行(“国际机器人与自动化会议”02)华盛顿特区,页1691 - 1696,美国2002年。视图:谷歌学术搜索
13. m . Bazaraa h . Sherali, c·谢蒂非线性规划理论和算法约翰·威利& Sons,纽约,纽约,美国,1995年。
14. H.-S。垫片和Y.-G。唱,“稳定和four-posture针对非完整移动机器人控制,”IEEE机器人和自动化,20卷,不。1,第154 - 148页,2004。视图:出版商的网站|谷歌学术搜索
15. j·埃文斯,b••b•巴罗斯t . Skewis诉Lumelsky,“处理真实世界的运动规划:医院运输机器人,”IEEE控制系统杂志,12卷,不。1、15 - 19,1992页。视图:谷歌学术搜索
16. m . s . Branicky”,多李雅普诺夫函数和其他分析工具切换和混合动力系统”IEEE自动控制,43卷,不。4、475 - 482年,1998页。视图:谷歌学术搜索

版权

版权©2009年京任和马克绿色。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。