搜索和救援机器人的持续规划

摘要 - 机器人在应急响应任务（如搜索和救援）的部署是机器人技术越来越重要的有前途的应用。 鉴于这些任务的危险性质，自主机器人操作是非常期望的，以便减少施加于人救援队的风险。 虽然已经对创建可以部署用于搜索和救援的机器人系统进行了大量工作，但是有限的工作已经致力于为这些任务设计有效的实时自动计划算法。 在这项工作中，我们提出REDHI，一个有效的算法，用于解决诸如搜索和救援等复杂问题的概率模型。 我们使用抽象域表示法和现有机器人系统的半现实模拟器来评估我们的搜索和救援问题算法。 结果表明，REDHI可以获得接近最佳的性能，可忽略的规划时间。

1．引言

我们关注的是用于应急响应任务的机器人部署，如城市搜索和救援（USAR）^[1]，野外搜索和救援[WiSAR] ^[2]和自然灾害^[3]。机器人可以对这些任务有巨大的价值，帮助人类救援队探索潜在危险的领土，消除环境威胁，并帮助疏散或治疗受害者。鉴于诸如搜索和救援的紧急响应任务的危险性质，自主机器人操作是非常希望的，以减少人类参与任务的风险。在这个意义上，实现自动操作的关键组件是机器人使用的计划算法，其必须考虑到机器人的观察，其动作和环境的基础状态的不确定性。虽然许多工作致力于开发可用于搜索和救援的机器人系统^{[4]，[5]，[6]，[7]，[8]}，有限的工作已经创建自动计划算法问题。概率规划的流行模型是马尔可夫决策过程（MDP）^[9]。 MDP提供了一个高度可表达的表示，可以模拟代理的操作和其周围环境的知识的不确定性。此外，该模型可以扩展到处理部分可观察性^[10]和多个协作代理^[11]。然而，解决MDP在计算上通常难以解决，这是一个问题，已将其应用限于时间敏感的任务，如搜索和救援机器人。我们的工作的贡献是一个有效的方法来解决MDP基于减少模型和后见优化的组合，集成到一个持续（在线）规划框架，以解决MDP的算法，REDHI，能够非常快速和接近最佳性能解决MDP。通过使用简化模型，REDHI可以提高后见性优化方法的可扩展性。我们评估使用我们的算法搜索和救援机器人使用半自动模拟的uBot ^[12]机器人系统。

2．相关工作

使用简化模型来解决MDP在规划领域受到了相当大的关注。基于确定的方法在最近几年得到普及，在确定性在线计划者FF-Replan ^[13]在第一次国际概率计划竞争中取得了令人惊讶的成功^[14]。这种想法的大规模破坏已经发展到现在，面向目标的MDP的最先进的规划者^[15]，[16]。其中一些与我们的工作密切相关，因为使用事后优化^[17]，[18]。此外，我们制定的搜索和救援问题是一个基于成本的一致的概率规划（CPP）问题的变异^[19]。 CPP的最先进的方法使用启发式搜索和加权模型计数^[20]，编译成度量规划问题^[21]，以及相关性分析与规则一致的规划者^[22]。最后两种方法与我们的工作有一些相似之处，因为它们使用一种形式的模型简化来使问题更易于处理 - 尽管与我们提出的方法相比，这种方法是不同类型的。此外，我们的公式试图最大化一些效用的概念，而典型的CPP注重于保证目标可达性。

3．问题制定

在本节中，我们描述在这项工作中使用的数学框架：一种特殊类型的马尔科夫决策过程（MDPs）称为随机最短路径问题（SSPs）。然后我们对搜索和救援情景进行高级描述，这是本工作的重点和其作为SSP的形式描述。

1. 随机最短路径问题

SSP是一个元组hS，A，T，C，s0，Gi，其中S是一组有限状态; A是一组有限的行为; T（s0 | s，a）是指定当在状态s中执行动作a时结果状态s0的概率的平稳过渡函数; C（s，a）是在状态s中执行动作a的正代价; s0isin;S是给定的开始状态;和Gsub;S是一套吸收目标状态。从状态s0开始，目标是达到目标状态之一，同时最小化预期累积成本。 SSP的最优解可以表示为将每个（可达）状态映射到动作pi;*的策略pi;*：S→A。众所周知的贝尔曼方程定义了一个关于状态的值函数V *（s），从中可以提取最优策略pi;*：

1. 搜索和救援方案

在搜索和救援问题中，机器人必须探索由已知地图描述的环境，目标是找到并救出未知数的受害者在一定的时间限制Tmax。机器人被给予一组可能包含受害者的L个位置，并且它在另一个称为BASE的特殊位置开始执行。可以存在两种类型的受害者：可移动的受害者是可以在机器人的辅助下移动的受害者，而不可移动的受害者不能移动，并且他们必须在现场接受治疗。此外，环境可能包含危险，必须通过将其带到指定位置来清除。这个问题可以表示为SSP。状态被定义为元组（l，t，hb1，b2，...，bLi），其中lisin;{BASE，1，...，L}表示机器人的位置，t是从机器人开始执行以来经过的时间（以一些离散单位测量），hb1，b2，...，bLi是表示机器人对环境中存在的物体（受害者或危险）的知识的向量。每个bi都可以有一个可能的值：unknown，vict-amb，vict-non-amb，hazard和nothing;我们将这些值的集合表示为O.初始状态s0由l = BASE，t = 0和forall;1le;ile;Lbi=未知定义。

机器人可以在4种不同类型的动作之间进行选择：

bull;移动到任何位置l，使得bl 6 =无。

bull;通过将受害者移动到基地来消除机器人位置处的移动受害者。

bull;在特定地点对待非流动受害者。机器人移动到基地，拿起药物，并将药物带回指定地点的受害者。

bull;通过将机器人的位置移动到基地，来消除危险。

除了MOVE操作之外，所有操作都是确定性的，在执行之后，它们所执行的对象（受害者/危险）在执行剩余的时候被忽略。另一方面，在MOVE动作的情况下，假设完全感测，则机器人在到达目标位置时将观察什么是不确定的。这种不确定性由大小为Ltimes;4的矩阵Pobs描述，该矩阵为每个位置指定其包含移动受害者，非移动受害者，危险或没有什么的概率。基本假设是位置l包含受害者/危险的概率独立于包含受害者/危险的其他位置的概率。因此，用于移动到位置l的转移函数被定义为使得对于每个xisin;O，它产生后继具有概率P obs [l，y]，其中y是对应于观察值x的矩阵P obs中的列。关于时间增量，每个动作a具有与所行进的距离相关联的一些时间长度Delta;Ta以及用于拾取受害者/危险的时间。也就是说，对于在时间步骤t处采取的任何动作a，所得到的状态将具有时间t0 = t Delta;Ta。在时间t0gt; Tmax之后，机器人不能采取任何更多的正常动作。为了避免由此产生的计划死端，机器人会被给予一个特殊的动作，END，这将导致一个吸收的目标状态，没有成本。所有动作的成本与从机器人开始操作起经过的时间直接相关。我们奖励机器人抢救受害者和尽快清除危险，没有与移动直接相关的惩罚;也就是说，没有与诸如能量消耗的因素相关联的成本。因此，MOVE动作的成本被设置为0，而在时间t采取的任何其他动作a的成本是（t Delta;Ta）-Tmax -Ra if（t Delta;Ta）le;Tmax，否则为0; Ra是与机器人执行的动作类型相关的恒定奖励。换句话说，机器人完成救援/净化动作的时间越长，该动作所产生的成本就越高。注意，在该公式下，动作成本总是为负的，因此机器人具有采取救援/净化动作的动机，以便最小化在其结束操作之前所发生的成本（负成本公式等同于最大化通过拯救受害者早）。

4．解决方法

解决SSP通常是难以解决的，因为状态空间的大小随任何紧凑问题表示的大小成指数地增长。这阻碍了使用SSPs的高度时间敏感性搜索和防御。为了应对这一挑战，在这项工作中，我们采用了一个持续的规划范例。持续规划是指在完全规划不能解决所有运行时意外事件的情况下交错规划和规划执行的各种方法[23]。通常，连续规划方法对原始问题的简化版本进行规划，以便可以更快地进行规划。如果执行超过该缩减模型，则更新计划以解决先前不可预见的事件，并且使用新计划继续执行。

1. 减少模型

我们的连续规划方法是基于MDP的Mk1减少^[25]。 AnMk l -reduction将每个动作的结果集分为两种类型：主要和异常。主要结果假定发生无限次，而假设异常发生到某个预定界限。状态空间被增加了到目前为止已经发生了多少异常的计数器，并且转换函数被修改，使得只有当发生到异常的转换时计数器增加1。当计数器达到预定界限k时，转换函数仅允许转换到

主要结果，并在其中重新分配全套概率。值l决定了每个操作可以考虑的主要结果的最大数量。更详细的解释可以在[25]中找到。第一眼看来，Mk-1减少似乎比原始的MDP复杂。然而，良好选择的减少可以显着地减少可达状态空间的大小（即，可以从s0到达的状态），这在使用启发式搜索MDP求解器例如LAO * [26]和LRTDP [27]。注意，不同的MDP减少的特征有两个选择：标记为主要的结果集合和k的选择。在搜索和救援问题中，主要结果的集合包括机器人在MOVE后没有观察到的所有结果，而观察受害者/危险被认为是例外。因此，这种简化的模型通过假设在环境中至多存在k个受害者/危害来简化该问题。持续规划中的一种常见方法是为简化模型计算完整的最优计划，然后将最终计划应用于原始问题。该计划的执行继续，直到达到目标，或者直到遇到在缩减模型之外的状态。在这种情况下，从当前执行状态开始创建新的简化模型，然后最优地解决该新模型以产生更新的计划，并且重新开始执行。然而，搜索和救援场景中的状态空间的大小是棘手的，即使当使用Mk1减少时也是如此。具体地，利用L个位置，T个时间步长和关于受害者/危险的数量的界限k，状态空间具有大小O（TLk2L）。对于10个位置的中等问题大小，20个时间步长和k = 1，这已经是105个状态的顺序。因此，即使具有M1 1减少，完全最佳规划仍然不实用。

1. 后视优化

我们可以利用减少的模型，通过注意到机器人可以工作的可能的环境配置（通常称为“世界”）的数量。特别地，在k个受害者/危险的假设下，可能世界的数量为O（TLk 1）的数量级，每个组合的时间，位置和k个位置的集合可以是受害者/危险。这大大小于原始SSP模型下可能的O（4LTL）世界，并且远小于缩减模型的状态空间。注意机器人可能的世界数量和机器人可以观察的世界的可能信念数量之间的差异。大量的信念是为什么计划优化缩减模型仍然难以解决的原因;缩减模型中的每个状态表示对当前世界配置的信念。通过使用后验优化（HOP）[17]，可以利用减少模型产生的可能世界的小数量。在HOP中，在某种状态下采取行动的预期成本通过与当前信念一致的抽样世界来估计

结果确定性规划问题和结果的平均。我们可以通过以下等式表达这种方法：

其中W是也与当前置信状态一致的可能世界的集合，P（w | s）当前状态是s并且动作a被采用，并且V *（w）是用于世界w的最优计划的成本。注意，可以非常容易地计算值V *（w），因为所得到的问题是确定性的。此外，在应用HOP之前使用简化模型的优点是对于小的k值，我们不需要使用采样，因为我们可以快速枚举与当前状态一致的所有世界，因此高效地计算平均值（2）。这个方法有一个警告。后视最优化假定在采取行动之后，机器人立即完全可以观察到世界。这是一个过于乐观的假设，一般来说，会导致任意坏的计划。直观地，原因是该方法忽略了收集信息的动作的影响。然而，如我们的实验所示，该算法对于搜索和救援场景执行得很好，可能是因为该问题中的每个动作必须在收集信息的动作之前（例如，在拯救位置A处的受害者之前，机器人必须移动到位置A并收集关于该位置中的对象的信息）。为了计算概率P（w | s），我们依赖于关于对象观测概率的独立性假设。请注意，值P（w）仅取决于它在每个位置指定的对象类型。让hw.x1，w.x2，...，w.xLibe描述这些对象的向量，w.yi对应于Pobs上的条目w.xi的列索引。然后，通过独立假设我们有：

状态指定了一些关于世界中存在的对象的知识。令hb1，b2，...，bLi对应于状态s的信念向量，并且K = {i：bi 6 =未知}。世界w被认为与状态s一致，如果w = xi。当w与s一致时，可以计算P（w | s）：

其中W是与s一致的世界集合。

1. 持续规划

算法1总结了我们的完整方法REDHI（还原 后视）。主要思想是每次出现异常时增加Mk-l的复制值

在执行期间发生，对于搜救问题，这相当于对目前为止所观察到的k个更多的受害者/危害的规划。 作为输入的一部分给出的集合Pa代表了Mk1减少的主要结果的选择。 如前所述，在这项工作中，主要的结果是机器人在移动到未开发的地点后什么也没有观察到。

5．实验结果

在本节中，我们将对我们的方法进行实验评估。 我们首先对搜索和救援问题的抽象领域表示进行评估，这样可以更容易地测试不同的环境配置并与现有的MDP解算器进行比较。 然后，我们对使用ROS实现的搜索和救援方案的半现实模拟评估计划者。

A.抽象域表示

我们在C 中实现了搜索和救援场景的抽象表示。 搜索和救援问题由2D平面上的一组位置，概率Pobs矩阵和表示机器人操作的最大时间步长数值Tmax描述。 由于没有底层的地图，所以位置是任意指定的，并且移动发生在位置之间的直线之后。 我们假设机器人以恒定速度v = 5（随时间步长测量）移动，使得在两个距离d之间取得的时间是d / v时间步长; 因此，所有MOVE操作都具有Delta;Ta= dd / ve时间步长。 另外，我们假设Delta;Ta= 4时间

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138932]，资料为PDF文档或Word文档，PDF文档可免费转换为Word