论文标题
用于大规模系统中有效最佳计划的分层有限状态机器
Hierarchical Finite State Machines for Efficient Optimal Planning in Large-scale Systems
论文作者
论文摘要
在本文中，我们考虑了层次有限状态机（HFSM）的计划问题，并开发了一种算法，以有效地计算任意两种状态之间的最佳计划。该算法由一个离线和在线步骤组成。在离线步骤中，一个人计算HFSM中每台机器的退出成本。对于给定的HFSM，仅需要一次完成一次，并且证明它具有时间复杂性与HFSM中的机器数量线性缩放。在在线步骤中，人们首先降低HFSM（使用退出成本），计算减少HFSM的最佳轨迹，然后将此轨迹扩展到原始HFSM的最佳计划，从而计算从初始状态到目标状态的最佳计划。时间复杂性与HFSM的深度接近线性。有人认为，大规模控制系统自然出现了HFSM，这是由机器人在房屋之间移动以完成任务的应用的例证。我们将算法与Dijkstra在HFSM上的算法进行了比较，该算法由多达200万个州组成，我们的算法在该算法上比后者的表现优于后者，速度更快。
In this paper, we consider a planning problem for a hierarchical finite state machine (HFSM) and develop an algorithm for efficiently computing optimal plans between any two states. The algorithm consists of an offline and an online step. In the offline step, one computes exit costs for each machine in the HFSM. It needs to be done only once for a given HFSM, and it is shown to have time complexity scaling linearly with the number of machines in the HFSM. In the online step, one computes an optimal plan from an initial state to a goal state, by first reducing the HFSM (using the exit costs), computing an optimal trajectory for the reduced HFSM, and then expand this trajectory to an optimal plan for the original HFSM. The time complexity is near-linearly with the depth of the HFSM. It is argued that HFSMs arise naturally for large-scale control systems, exemplified by an application where a robot moves between houses to complete tasks. We compare our algorithm with Dijkstra's algorithm on HFSMs consisting of up to 2 million states, where our algorithm outperforms the latter, being several orders of magnitude faster.
