• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Australasian joint conference on artificial intelligence >Detecting Mutex Pairs in State Spaces by Sampling
【24h】

Detecting Mutex Pairs in State Spaces by Sampling

机译：通过采样检测状态空间中的互斥对

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the context of state space planning, a mutex pair is a pair of variable-value assignments that does not occur in any reachable state. Detecting mutex pairs is a problem that has been addressed frequently in the planning literature. In this paper, we present the Missing Mass Method (MMM)-a new efficient and domain-independent method for mutex pair detection, based on sampling reachable states. We exploit a recent result from statistical theory, proven by Berend and Kontorovich in [1], that bounds the probability mass of missing events in a sample of a given size. We tested MMM empirically on various sizes of four standard benchmark domains from the planning and heuristic search literature. In many cases, MMM works perfectly, i.e., finds all and only the mutex pairs. In the other cases, it is near-perfect: it correctly labels all mutex pairs and more than 99.99% of all non-mutex pairs.
机译：在状态空间规划的上下文中，互斥体对是一对在任何可达状态中都不会发生的变量值分配。检测互斥对是一个计划文献中经常提到的问题。在本文中，我们提出了“缺失质量法”（MMM），这是一种基于采样可达状态的，有效且与域无关的互斥对检测方法。我们利用了Berend和Kontorovich在[1]中证明的统计理论的最新结果，该结果限制了给定大小的样本中丢失事件的概率质量。我们从规划和启发式搜索文献中对四个标准基准域的各种大小进行了MMM的经验测试。在许多情况下，MMM可以完美地工作，即查找所有且仅互斥对。在其他情况下，它几乎是完美的：它正确标记了所有互斥体对，并标记了所有非互斥体对的99.99％以上。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号