In this work, we consider the problem of planning for temporal logic tasks in large robot environments. When full task compliance is unattainable, we aim to achieve the best possible task satisfaction by integrating user preferences for relaxation into the planning process. Utilizing the automata-based representations for temporal logic goals and user preferences, we propose an A*-based planning framework. This approach effectively tackles large-scale problems while generating near-optimal high-level trajectories. To facilitate this, we propose a simple, efficient heuristic that allows for planning over large robot environments in a fraction of time and search memory as compared to uninformed search algorithms. We present extensive case studies to demonstrate the scalability, runtime analysis as well as empirical bounds on the suboptimality of the proposed heuristic.

翻译：本文研究了大规模机器人环境中时序逻辑任务的规划问题。当任务无法完全满足时，我们通过将用户对任务松弛的偏好整合到规划过程中，旨在实现最优的任务满足度。利用基于自动机的时序逻辑目标与用户偏好表示，我们提出了一种基于A*算法的规划框架。该方法能有效处理大规模问题，同时生成接近最优的高层轨迹。为此，我们设计了一种简单高效的启发式函数，相较于无启发式搜索算法，该函数能以更短的时间和更少的内存在大规模机器人环境中进行规划。我们通过大量案例研究，展示了所提方法的可扩展性、运行时间分析以及启发式函数次优性的经验界限。