Motion Planning for Hybrid Dynamical Systems: Framework, Algorithm Template, and a Sampling-based Approach

📄 arXiv: 2406.01802v1 📥 PDF

作者: Nan Wang, Ricardo G. Sanfelice

分类: cs.RO, eess.SY

发布日期: 2024-06-03

备注: 33 pages, 8 figures. Submitted to IJRR. arXiv admin note: text overlap with arXiv:2210.15082

💡 一句话要点

提出一种基于RRT的混合动力系统运动规划算法HyRRT，解决复杂系统运动规划问题。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 混合动力系统 运动规划 RRT算法 概率完备性 机器人 优化控制 采样算法

📋 核心要点

  1. 混合动力系统运动规划面临连续与离散行为交织的挑战，传统方法难以有效处理。
  2. 论文提出一种基于RRT的HyRRT算法，通过随机采样和流/跳跃扩展搜索树，实现概率完备性。
  3. 实验验证了HyRRT在弹跳球和步行机器人系统中的有效性，展示了其通用性和计算性能。

📝 摘要（中文）

本文关注于同时展现连续和离散行为的系统的运动规划问题，我们称之为混合动力系统。首先，使用混合方程框架对混合系统的运动规划问题进行建模，该框架具有通用性，可以捕获大多数混合系统。其次，提出了一个传播算法模板，描述了一个解决混合系统运动规划问题的通用框架。第三，设计了所提出的算法模板的快速探索随机树（RRT）实现，以解决混合系统的运动规划问题。在每次迭代中，所提出的算法，称为HyRRT，随机选择一个状态样本，并通过流或跳跃来扩展搜索树，当两种方式都可行时，也会随机选择。通过混合时间域上定义的函数的串联定义，我们证明了HyRRT是概率完备的，也就是说，随着算法迭代次数的增加，找不到运动计划的概率接近于零。在定义运动计划的数据的温和条件下，保证了这一性质，其中包括对经典系统文献中通常施加的正间隙假设的放宽。通过求解两个优化问题来计算运动计划，一个与系统的流相关，另一个与系统的跳跃相关。将所提出的算法应用于受驱动的弹跳球系统和步行机器人系统，以突出其通用性和计算特性。

🔬 方法详解

问题定义：论文旨在解决混合动力系统的运动规划问题。现有方法通常难以处理连续和离散行为的复杂交互，并且对环境有严格的假设（如正间隙假设），限制了其应用范围。

核心思路：论文的核心思路是利用快速探索随机树（RRT）算法的随机探索能力，结合混合动力系统的特性，设计一种能够同时处理连续运动（流）和离散跳跃的运动规划算法。通过随机采样状态空间，并根据系统动力学选择性地进行流或跳跃扩展，逐步构建搜索树，最终找到从起始状态到目标状态的运动轨迹。

技术框架：HyRRT算法的整体框架如下： 1. 初始化：构建初始搜索树，包含起始状态。 2. 迭代：重复以下步骤直到找到解或达到最大迭代次数： a. 随机采样：在状态空间中随机选择一个状态样本。 b. 最近邻搜索：在搜索树中找到距离采样状态最近的节点。 c. 扩展：以一定概率选择流或跳跃方式进行扩展。如果两种方式都可行，则随机选择一种。 d. 添加：将扩展得到的新节点添加到搜索树中。 3. 路径提取：如果找到目标状态附近的节点，则从该节点回溯到起始节点，得到运动规划路径。

关键创新：论文的关键创新在于： 1. 提出了一个通用的混合动力系统运动规划框架，能够处理多种类型的混合系统。 2. 设计了一种基于RRT的HyRRT算法，能够同时处理连续运动和离散跳跃。 3. 通过定义混合时间域上函数的串联，证明了HyRRT算法的概率完备性，并在较宽松的条件下保证了算法的收敛性。

关键设计：HyRRT算法的关键设计包括： 1. 流和跳跃的选择策略：当两种方式都可行时，随机选择一种，保证了搜索的随机性和探索性。 2. 扩展步长的选择：需要根据具体的系统动力学进行调整，以保证扩展的有效性和效率。 3. 优化问题的求解：在进行流和跳跃扩展时，需要求解相应的优化问题，以找到满足系统约束的最优控制输入。论文中没有详细说明具体的优化算法，但指出需要根据具体系统进行选择。

📊 实验亮点

论文通过弹跳球系统和步行机器人系统的实验验证了HyRRT算法的有效性。实验结果表明，HyRRT算法能够成功规划出满足系统约束的运动轨迹，并展示了其在不同类型混合动力系统中的通用性。虽然论文没有给出具体的性能数据，但通过可视化结果展示了算法的规划效果。

🎯 应用场景

该研究成果可应用于机器人、自动化、航空航天等领域，例如：复杂地形下的机器人导航、多模式交通工具的路径规划、以及具有多种工作模式的自动化生产线控制。该算法的概率完备性保证了在足够的时间内找到可行解，具有重要的实际应用价值和潜力。

📄 摘要（原文）

This paper focuses on the motion planning problem for the systems exhibiting both continuous and discrete behaviors, which we refer to as hybrid dynamical systems. Firstly, the motion planning problem for hybrid systems is formulated using the hybrid equation framework, which is general to capture most hybrid systems. Secondly, a propagation algorithm template is proposed that describes a general framework to solve the motion planning problem for hybrid systems. Thirdly, a rapidly-exploring random trees (RRT) implementation of the proposed algorithm template is designed to solve the motion planning problem for hybrid systems. At each iteration, the proposed algorithm, called HyRRT, randomly picks a state sample and extends the search tree by flow or jump, which is also chosen randomly when both regimes are possible. Through a definition of concatenation of functions defined on hybrid time domains, we show that HyRRT is probabilistically complete, namely, the probability of failing to find a motion plan approaches zero as the number of iterations of the algorithm increases. This property is guaranteed under mild conditions on the data defining the motion plan, which include a relaxation of the usual positive clearance assumption imposed in the literature of classical systems. The motion plan is computed through the solution of two optimization problems, one associated with the flow and the other with the jumps of the system. The proposed algorithm is applied to an actuated bouncing ball system and a walking robot system so as to highlight its generality and computational features.