本文研究了运动和环境不确定性的最佳运动规划。通过将系统建模作为概率标记的马尔可夫决策过程(PL-MDP),控制目标是合成有限内存策略,在该策略下,该代理满足具有所需满足的线性时间逻辑(LTL)的高级复杂任务可能性。特别地,考虑了满足无限地平线任务的轨迹的成本优化,分析了降低预期平均成本和最大化任务满意度概率之间的权衡。而不是使用传统的Rabin Automata,LTL公式被转换为限制确定性的B \“UCHI自动机(LDBA),其具有更直接的接受条件和更紧凑的图形结构。这项工作的新颖性在于考虑案件LTL规范可能是不可行的,并且在PL-MDP和LDBA之间的轻松产品MDP的开发可能是不可行的和开发。放松的产品MDP允许代理在任务不完全可行的情况下进行修改其运动计划,并量化修订计划的违规测量。然后配制多目标优化问题,共同考虑任务满意度的概率,违反原始任务限制的违规以及策略执行的实施成本,通过耦合的线性计划解决。据最好我们的知识,它是第一个弥合规划修订版和计划前缀和计划的最佳控制合成之间的差距的工作在无限地平线上修复代理轨迹。提供实验结果以证明所提出的框架的有效性。
translated by 谷歌翻译
强化学习(RL)是一种有希望的方法,对现实世界的应用程序取得有限,因为确保安全探索或促进充分利用是控制具有未知模型和测量不确定性的机器人系统的挑战。这种学习问题对于连续空间(状态空间和动作空间)的复杂任务变得更加棘手。在本文中,我们提出了一种由几个方面组成的基于学习的控制框架:(1)线性时间逻辑(LTL)被利用,以便于可以通过无限视野的复杂任务转换为新颖的自动化结构; (2)我们为RL-Agent提出了一种创新的奖励计划,正式保证,使全球最佳政策最大化满足LTL规范的概率; (3)基于奖励塑造技术,我们开发了利用自动机构结构的好处进行了模块化的政策梯度架构来分解整体任务,并促进学习控制器的性能; (4)通过纳入高斯过程(GPS)来估计不确定的动态系统,我们使用指数控制屏障功能(ECBF)综合基于模型的保障措施来解决高阶相对度的问题。此外,我们利用LTL自动化和ECBF的性质来构建引导过程,以进一步提高勘探效率。最后,我们通过多个机器人环境展示了框架的有效性。我们展示了这种基于ECBF的模块化深RL算法在训练期间实现了近乎完美的成功率和保护安全性,并且在训练期间具有很高的概率信心。
translated by 谷歌翻译
本文研究了Markov决策过程(MDP)建模的自主动态系统的运动规划,在连续状态和动作空间上具有未知的过渡概率。线性时间逻辑(LTL)用于指定无限地平线上的高级任务,可以转换为具有几种接受集的极限确定性广义B \“UCHI Automaton(LDGBA)。新颖性是设计嵌入式产品MDP(通过结合同步跟踪 - 前沿函数来记录自动化的同步跟踪 - 前沿函数,并促进接受条件的满足感。基于LDGBA的奖励塑造和折扣方案的模型的满足 - 免费加强学习(RL)仅取决于EP-MDP状态,并可以克服稀疏奖励的问题。严格的分析表明,任何优化预期折扣返回的RL方法都保证找到最佳策略,其迹线最大化满意度概率。然后开发模块化深度确定性政策梯度(DDPG)以在连续状态和行动空间上生成此类策略。我们的f Ramework通过一系列Openai健身房环境进行评估。
translated by 谷歌翻译
具有高级别规格的自治系统的运动规划具有广泛的应用。然而,涉及定时时间逻辑的正式语言的研究仍在调查中。此外,许多现有结果依赖于用户指定的任务在给定环境中可行的关键假设。当操作环境是动态和未知的挑战时,由于环境可以找到禁止,导致预先定时定时任务无法完全满足潜在冲突的任务。在考虑时间束缚要求时,这些问题变得更具挑战性。为了解决这些挑战,这项工作提出了一种控制框架,其考虑了强制限制来强制执行安全要求和软限制,以启用任务放松。使用度量间隔时间逻辑(MITL)规范来处理时间限制约束。通过构建轻松的定时产品自动机,在线运动规划策略与后退地平线控制器合成以产生政策,以减少优先顺序的降低方式实现多重目标1)正式保证了对硬安全限制的满足感; 2)主要满足软定时任务; 3)尽可能收集时变奖励。放松结构的另一个新颖性是考虑违反时间和任务的不可行情况。提供仿真结果以验证所提出的方法。
translated by 谷歌翻译
勘探是基于深入强化学习(DRL)的无模型导航控制的基本挑战,因为针对目标驱动的导航任务的典型勘探技术依赖于噪声或贪婪的政策,这些策略对奖励的密度敏感。实际上,机器人总是在复杂的混乱环境中部署,其中包含密集的障碍和狭窄的通道,从而提高了很难探索训练的自然备用奖励。当预定义的任务复杂并且具有丰富的表现力时,这种问题变得更加严重。在本文中,我们专注于这两个方面,并为任务指导的机器人提供了一种深层的政策梯度算法,该机器人在复杂的混乱环境中部署了未知的动态系统。线性时间逻辑(LTL)用于表达丰富的机器人规范。为了克服训练期间探索的环境挑战,我们提出了一种新颖的路径计划引导奖励方案,该方案在状态空间上密集,并且至关重要的是,由于黑盒动力学而导致计算的几何路径的不可行性。为了促进LTL满意度,我们的方法将LTL任务分解为使用分布式DRL解决的子任务,在该子任务中,可以使用深层政策梯度算法并行培训子任务。我们的框架被证明可显着提高性能(有效性,效率)和对大规模复杂环境中复杂任务的机器人的探索。可以在YouTube频道上找到视频演示:https://youtu.be/yqrq2-ymtik。
translated by 谷歌翻译
本文解决了以未知的马尔可夫决策过程(MDP)建模的移动机器人的学习控制策略的问题,该问题负责为时间逻辑任务,例如测序,覆盖或监视。 MDP捕获工作空间结构的不确定性和控制决策的结果。控制目标是合成一个控制策略,该策略最大化完成高级任务的可能性,该任务指定为线性时间逻辑(LTL)公式。为了解决这个问题,我们提出了一种针对LTL控制目标的新型基于模型的增强算法(RL)算法,该算法能够比相关方法更快地学习控制策略。它的样本效率依赖于偏见探索可能导致任务满意度的方向。这是通过利用LTL任务的自动机表示以及连续学习的MDP模型来完成的。最后,我们提供了比较实验,这些实验证明了针对LTL目标的最新RL方法的样本效率。
translated by 谷歌翻译
本文在具有部分未知语义的环境中解决了多机器人规划问题。假设环境具有已知的几何结构(例如,墙壁),并且由具有不确定位置和类的静态标记的地标占用。这种建模方法引发了语义SLAM算法生成的不确定语义地图。我们的目标是为配备有嘈杂感知系统的机器人设计控制策略,以便他们可以完成全局时间逻辑规范捕获的协同任务。为了指定考虑环境和感知不确定性的任务,我们采用了线性时间逻辑(LTL)的片段,称为CO-Safe LTL,定义了基于感知的原子谓性建模概率满意度要求。基于感知的LTL规划问题产生了通过新型采样的算法解决的最佳控制问题,它产生了在线更新的开环控制策略,以适应连续学习的语义地图。我们提供广泛的实验,以证明拟议的规划架构的效率。
translated by 谷歌翻译
In inverse reinforcement learning (IRL), a learning agent infers a reward function encoding the underlying task using demonstrations from experts. However, many existing IRL techniques make the often unrealistic assumption that the agent has access to full information about the environment. We remove this assumption by developing an algorithm for IRL in partially observable Markov decision processes (POMDPs). We address two limitations of existing IRL techniques. First, they require an excessive amount of data due to the information asymmetry between the expert and the learner. Second, most of these IRL techniques require solving the computationally intractable forward problem -- computing an optimal policy given a reward function -- in POMDPs. The developed algorithm reduces the information asymmetry while increasing the data efficiency by incorporating task specifications expressed in temporal logic into IRL. Such specifications may be interpreted as side information available to the learner a priori in addition to the demonstrations. Further, the algorithm avoids a common source of algorithmic complexity by building on causal entropy as the measure of the likelihood of the demonstrations as opposed to entropy. Nevertheless, the resulting problem is nonconvex due to the so-called forward problem. We solve the intrinsic nonconvexity of the forward problem in a scalable manner through a sequential linear programming scheme that guarantees to converge to a locally optimal policy. In a series of examples, including experiments in a high-fidelity Unity simulator, we demonstrate that even with a limited amount of data and POMDPs with tens of thousands of states, our algorithm learns reward functions and policies that satisfy the task while inducing similar behavior to the expert by leveraging the provided side information.
translated by 谷歌翻译
在本文中,我们研究了以马尔可夫决策过程(MDP)为模型的随机系统中的计划,其偏好比时间扩展的目标。偏好的时间计划上的先前工作假定用户偏好形成总订单,这意味着每对结果彼此相当。在这项工作中,我们考虑了对可能结果的偏好是部分顺序而不是总订单的情况。我们首先引入了确定性有限自动机的变体,称为偏好DFA,用于指定用户对时间扩展目标的偏好。基于顺序理论,我们将偏好DFA转化为与标记为MDP中概率计划的策略相比的偏好关系。在这种处理中,最优选的策略会在MDP中的有限路径上引起弱化的非主导概率分布。拟议的计划算法取决于建造多目标MDP。我们证明,考虑到偏好规范的弱化的非主导政策在构建的多目标MDP中是帕特托最佳的,反之亦然。在整篇论文中,我们采用一个运行的示例来演示提出的偏好规范和解决方案方法。我们使用该示例和详细分析显示了算法的功效,然后讨论可能的未来方向。
translated by 谷歌翻译
我们使用线性时间逻辑(LTL)约束研究策略优化问题(PO)。LTL的语言允许灵活描述可能不自然的任务,以编码为标量成本函数。我们将LTL受限的PO视为系统框架,将任务规范与策略选择解耦,以及成本塑造标准的替代方案。通过访问生成模型,我们开发了一种基于模型的方法,该方法享有样本复杂性分析,以确保任务满意度和成本最佳性(通过减少到可达性问题)。从经验上讲,即使在低样本制度中,我们的算法也可以实现强大的性能。
translated by 谷歌翻译
我们研究了由测量和过程噪声引起的不确定性的动态系统的规划问题。测量噪声导致系统状态可观察性有限,并且过程噪声在给定控制的结果中导致不确定性。问题是找到一个控制器,保证系统在有限时间内达到所需的目标状态,同时避免障碍物,至少需要一些所需的概率。由于噪音,此问题不承认一般的精确算法或闭合性解决方案。我们的主要贡献是一种新颖的规划方案,采用卡尔曼滤波作为状态估计器,以获得动态系统的有限状态抽象,我们将作为马尔可夫决策过程(MDP)正式化。通过延长概率间隔的MDP,我们可以增强模型对近似过渡概率的数值不精确的鲁棒性。对于这种所谓的间隔MDP(IMDP),我们采用最先进的验证技术来有效地计算最大化目标状态概率的计划。我们展示了抽象的正确性,并提供了几种优化,旨在平衡计划的质量和方法的可扩展性。我们展示我们的方法能够处理具有6维状态的系统,该系统导致具有数万个状态和数百万个过渡的IMDP。
translated by 谷歌翻译
在以并发方式解决团队范围的任务时,多机构系统可能非常有效。但是,如果没有正确的同步,则很难保证合并行为的正确性,例如遵循子任务的特定顺序或同时进行协作。这项工作解决了在复杂的全球任务下,将最低时间的任务计划问题称为线性时间逻辑(LTL)公式。这些任务包括独立本地动作和直接子团队合作的时间和空间要求。提出的解决方案是一种随时随地的算法,结合了对任务分解的基础任务自动机的部分顺序分析,以及用于任务分配的分支和绑定(BNB)搜索方法。提供最小的完成时间的合理性,完整性和最佳性分析。还表明,在搜索范围内持续在时间预算之内,可以迅速达成可行且近乎最佳的解决方案。此外,为了处理在线执行期间任务持续时间和代理失败的波动,提出了适应算法来同步执行状态并动态地重新分配未完成的子任务以保持正确性和最佳性。两种算法通过数值模拟和硬件实验在大规模系统上进行了严格的验证,该算法对几个强基地进行了验证。
translated by 谷歌翻译
意图欺骗涉及计算一项策略,该战略欺骗对手对代理人的意图或客观的错误信念。本文研究了一类概率的计划问题和意图欺骗,并研究了攻击者几乎可以肯定地(具有概率)来实现其攻击目标的有限感应方式,同时隐藏了其意图。特别是,我们将攻击计划建模为以马尔可夫决策过程(MDP)为模型的随机系统。攻击者将到达某些目标状态,同时避免系统中不安全的状态,并知道他的行为是由有部分观察的后卫监控的。鉴于对辩护人的部分状态观察,我们开发了定性意图欺骗计划算法,以构建攻击策略,以分别对抗动作可见的辩护人和动作无关的辩护人。合成的攻击策略不仅确保了攻击目标几乎可以肯定地满足,而且还欺骗了辩护人,认为观察到的行为是由普通/合法用户产生的,因此未能检测到攻击的存在。我们显示所提出的算法是正确和完整的,并用示例说明了欺骗性的计划方法。
translated by 谷歌翻译
近年来,研究人员在设计了用于优化线性时间逻辑(LTL)目标和LTL的目标中的增强学习算法方面取得了重大进展。尽管有这些进步,但解决了这个问题的基本限制,以至于以前的研究暗示,但对我们的知识而言,尚未深入检查。在本文中,我们通过一般的LTL目标理解了学习的硬度。我们在马尔可夫决策过程(PAC-MDP)框架(PAC-MDP)框架中可能大致正确学习的问题正式化,这是一种测量加固学习中的样本复杂性的标准框架。在这一形式化中,我们证明,只有在LTL层次结构中最有限的类别中,才有于仅当公式中的最有限的类别,因此才能获得PAC-MDP的最佳政策。实际上,我们的结果意味着加强学习算法无法在与非有限范围可解除的LTL目标的无限环境的相互作用之后获得其学习政策的性能的PAC-MDP保证。
translated by 谷歌翻译
Besides the recent impressive results on reinforcement learning (RL), safety is still one of the major research challenges in RL. RL is a machine-learning approach to determine near-optimal policies in Markov decision processes (MDPs). In this paper, we consider the setting where the safety-relevant fragment of the MDP together with a temporal logic safety specification is given and many safety violations can be avoided by planning ahead a short time into the future. We propose an approach for online safety shielding of RL agents. During runtime, the shield analyses the safety of each available action. For any action, the shield computes the maximal probability to not violate the safety specification within the next $k$ steps when executing this action. Based on this probability and a given threshold, the shield decides whether to block an action from the agent. Existing offline shielding approaches compute exhaustively the safety of all state-action combinations ahead of time, resulting in huge computation times and large memory consumption. The intuition behind online shielding is to compute at runtime the set of all states that could be reached in the near future. For each of these states, the safety of all available actions is analysed and used for shielding as soon as one of the considered states is reached. Our approach is well suited for high-level planning problems where the time between decisions can be used for safety computations and it is sustainable for the agent to wait until these computations are finished. For our evaluation, we selected a 2-player version of the classical computer game SNAKE. The game represents a high-level planning problem that requires fast decisions and the multiplayer setting induces a large state space, which is computationally expensive to analyse exhaustively.
translated by 谷歌翻译
马尔可夫决策过程通常用于不确定性下的顺序决策。然而,对于许多方面,从受约束或安全规范到任务和奖励结构中的各种时间(非Markovian)依赖性,需要扩展。为此,近年来,兴趣已经发展成为强化学习和时间逻辑的组合,即灵活的行为学习方法的组合,具有稳健的验证和保证。在本文中,我们描述了最近引入的常规决策过程的实验调查,该过程支持非马洛维亚奖励功能以及过渡职能。特别是,我们为常规决策过程,与在线,增量学习有关的算法扩展,对无模型和基于模型的解决方案算法的实证评估,以及以常规但非马尔维亚,网格世界的应用程序的算法扩展。
translated by 谷歌翻译
我们研究了逆钢筋学习的问题(IRL),学习代理使用专家演示恢复奖励功能。大多数现有的IRL技术使代理商可以访问有关环境的完整信息,这使得经常不切实际的假设。我们通过在部分可观察到的马尔可夫决策过程(POMDPS)中开发IRL算法来消除此假设。该算法解决了现有技术的若干限制,这些技术不会考虑专家和学习者之间的信息不对称。首先,它采用因果熵作为专家演示的可能性,而不是在大多数现有的IRL技术中熵,避免了算法复杂性的共同来源。其次,它包含以时间逻辑表示的任务规范。除了演示之外,这些规范可以被解释为对学习者可用的侧面信息,并且可以减少信息不对称。然而,由于所谓的前向问题的内在非凸起,即计算最佳政策,在POMDPS中计算最佳政策,所得到的制剂仍然是非凸的。通过顺序凸编程来解决这种非凸起,并介绍几个扩展以以可扩展的方式解决前向问题。这种可扩展性允许计算策略,以牺牲添加的计算成本为代价也越优于无记忆策略。我们证明,即使具有严重限制的数据,算法也会了解满足任务的奖励函数和策略,并通过利用侧面信息并将内存结合到策略中来对专家引起类似的行为。
translated by 谷歌翻译
当环境稀疏和非马克维亚奖励时,使用标量奖励信号的训练加强学习(RL)代理通常是不可行的。此外,在训练之前对这些奖励功能进行手工制作很容易指定,尤其是当环境的动态仅部分知道时。本文提出了一条新型的管道,用于学习非马克维亚任务规格,作为简洁的有限状态“任务自动机”,从未知环境中的代理体验情节中。我们利用两种关键算法的见解。首先,我们通过将其视为部分可观察到的MDP并为隐藏的Markov模型使用现成的算法,从而学习了由规范的自动机和环境MDP组成的产品MDP,该模型是由规范的自动机和环境MDP组成的。其次,我们提出了一种从学习的产品MDP中提取任务自动机(假定为确定性有限自动机)的新方法。我们学到的任务自动机可以使任务分解为其组成子任务,从而提高了RL代理以后可以合成最佳策略的速率。它还提供了高级环境和任务功能的可解释编码,因此人可以轻松地验证代理商是否在没有错误的情况下学习了连贯的任务。此外,我们采取步骤确保学识渊博的自动机是环境不可静止的,使其非常适合用于转移学习。最后,我们提供实验结果,以说明我们在不同环境和任务中的算法的性能及其合并先前的领域知识以促进更有效学习的能力。
translated by 谷歌翻译
在安全关键方案中利用自主系统需要在存在影响系统动态的不确定性和黑匣子组件存在下验证其行为。在本文中,我们开发了一个框架,用于验证部分可观察到的离散时间动态系统,从给定的输入输出数据集中具有针对时间逻辑规范的未暗模式可分散的动态系统。验证框架采用高斯进程(GP)回归,以了解数据集中的未知动态,并将连续空间系统抽象为有限状态,不确定的马尔可夫决策过程(MDP)。这种抽象依赖于通过使用可重复的内核Hilbert空间分析以及通过离散化引起的不确定性来捕获由于GP回归中的错误而捕获不确定性的过渡概率间隔。该框架利用现有的模型检查工具来验证对给定时间逻辑规范的不确定MDP抽象。我们建立将验证结果扩展到潜在部分可观察系统的抽象结果的正确性。我们表明框架的计算复杂性在数据集和离散抽象的大小中是多项式。复杂性分析说明了验证结果质量与处理较大数据集和更精细抽象的计算负担之间的权衡。最后,我们展示了我们的学习和验证框架在具有线性,非线性和切换动力系统的几种案例研究中的功效。
translated by 谷歌翻译
This work considers the path planning problem for a team of identical robots evolving in a known environment. The robots should satisfy a global specification given as a Linear Temporal Logic (LTL) formula over a set of regions of interest. The proposed method exploits the advantages of Petri net models for the team of robots and B\"uchi automata modeling the specification. The approach in this paper consists in combining the two models into one, denoted Composed Petri net and use it to find a sequence of action movements for the mobile robots, providing collision free trajectories to fulfill the specification. The solution results from a set of Mixed Integer Linear Programming (MILP) problems. The main advantage of the proposed solution is the completeness of the algorithm, meaning that a solution is found when exists, this representing the key difference with our previous work in [1]. The simulations illustrate comparison results between current and previous approaches, focusing on the computational complexity.
translated by 谷歌翻译