• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Introducing Preferences in Planning as Satisfiability
【24h】

Introducing Preferences in Planning as Satisfiability

机译：在计划中引入偏好作为可满足性

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Planning as Satisfiability is one of the most well-known and effective techniques for classical planning: satplan has been the winning system in the deterministic track for optimal planners in the 4th International Planning Competition (IPC) and a co-winner in the 5th IPC. Given a planning problem Π and a makespan n, the approach based on satisfiability (a.k.a. SAT-based) simply works by (i) constructing a SAT formula Π_n and (ii) checking Π_n for satisfiability: if there is a model for Π_n then we have found a plan, otherwise n is increased. The approach guarantees that the makespan is optimal, i.e. minimum. In this article we extend the Planning as Satisfiability approach in order to handle preferences and satplan in order to solve problems with simple preferences. This allows, e.g. to take into consideration 'plan quality' issues other than makespan, like number of actions and 'soft' goals. The basic idea is to explore the search space of possible plans in accordance with the given partially ordered preferences. We first prove that, at fixed makespan, our approach returns an 'optimal' plan, if any. Then, considering both classical planning problems and problems coming from IPC-5, we show that satplan extended in order to deal with preferences: (i) returns optimal plans that are often of considerable better quality, i.e. with fewer actions or with a belter plan metric on soft goals, than satplan; and (ii) is overall competitive, in terms of plan quality, with sgplan, the winning system in the 'SimplePreferences' category of the IPC-5. Notably, such results are often obtained without sacrificing efficiency.
机译：作为可满足性的计划是经典计划中最著名，最有效的技术之一：satplan一直是第四届国际计划竞赛（IPC）最佳规划者确定性轨道上的获胜系统，并且是第五届IPC的共同获奖者。给定一个计划问题and和一个制造期n，基于可满足性（基于SAT）的方法可以通过（i）构造SAT公式_n和（ii）检查Π_n的可满足性进行工作：如果存在__n的模型，那么我们找到一个计划，否则n增加。该方法保证了制造期是最佳的，即最小的。在本文中，我们扩展了“计划可满足性”方法，以便处理偏好和满足计划，从而解决具有简单偏好的问题。这允许例如除了完成期以外还要考虑“计划质量”问题，例如行动次数和“软”目标。基本思想是根据给定的部分排序的偏好来探索可能的计划的搜索空间。我们首先证明，在固定的制造时间上，我们的方法会返回“最佳”计划（如果有）。然后，同时考虑到经典计划问题和IPC-5产生的问题，我们表明可以扩展饱和计划以应对偏好：（i）返回通常质量较好的最优计划，即减少操作或采用皮带器计划软目标指标，而不是满足计划； （ii）就计划质量而言，与sgplan（IPC-5的“简单首选项”类别中的获胜系统）相比具有总体竞争力。显然，通常在不牺牲效率的情况下获得这种结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号