In this paper, we investigate the optimal robot path planning problem for high-level specifications described by co-safe linear temporal logic (LTL) formulae. We consider the scenario where the map geometry of the workspace is partially-known. Specifically, we assume that there are some unknown regions, for which the robot does not know their successor regions a priori unless it reaches these regions physically. In contrast to the standard game-based approach that optimizes the worst-case cost, in the paper, we propose to use regret as a new metric for planning in such a partially-known environment. The regret of a plan under a fixed but unknown environment is the difference between the actual cost incurred and the best-response cost the robot could have achieved if it realizes the actual environment with hindsight. We provide an effective algorithm for finding an optimal plan that satisfies the LTL specification while minimizing its regret. A case study on firefighting robots is provided to illustrate the proposed framework. We argue that the new metric is more suitable for the scenario of partially-known environment since it captures the trade-off between the actual cost spent and the potential benefit one may obtain for exploring an unknown region.
翻译:在本文中,我们调查了以共同安全线性时间逻辑(LTL)公式描述的高规格的机器人最佳路径规划问题。我们考虑了工作空间地图几何部分为人所知的情景。具体地说,我们假设有些未知区域,除非机器人实际到达后方区域,否则机器人不会事先了解其后方区域。与本文中优化最坏情况成本的标准基于游戏的方法相比,我们提议在这种不为人知的环境中将遗憾用作规划的新标准。在固定但未知的环境中,计划的遗憾是实际成本与机器人实现后视实际环境时所能达到的最佳应对成本之间的差异。我们提供了一种有效的算法,以找到一种满足LTL标准的最佳计划,同时尽量减少遗憾。我们提供了关于消防机器人的案例研究,以说明拟议框架。我们争辩说,新指标更适合部分为人知的环境,因为它反映了实际成本与探索未知区域可能获得的潜在利益之间的权衡。