...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Conflict-directed A* and its role in model-based embedded systems
【24h】

Conflict-directed A* and its role in model-based embedded systems

机译：冲突导向的A *及其在基于模型的嵌入式系统中的作用

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

摘要

Artificial Intelligence has traditionally used constraint satisfaction and logic to frame a wide range of problems, including planning, diagnosis, cognitive robotics and embedded systems control. However, many decision making problems are now being re-framed as optimization problems, involving a search over a discrete space for the best solution that satisfies a set of constraints. The best methods for finding optimal solutions, such as A(*), explore the space of solutions one state at a time. This paper introduces conflict-directed A(*), a method for solving optimal constraint satisfaction problems. Conflict-directed A(*) searches the state space in best first order, but accelerates the search process by eliminating subspaces around each state that are inconsistent. This elimination process builds upon the concepts of conflict and kernel diagnosis used in model-based diagnosis [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(1) (1987) 97-130; J. de Kleer, A. Mackworth, R. Reiter, Characterizing diagnoses and systems, Artif. Intell. 56 (1992) 197-222] and in dependency-directed search [R. Stallman, G.J. Sussman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artif. Intell. 9 (1977) 135-196; J. Gaschnig, Performance measurement and analysis of certain search algorithms, Technical Report CMU-CS-79-124, Carnegie-Mellon University, Pittsburgh, PA, 1979; J. de Kleer, B.C. Williams, Back to backtracking: controlling the ATMS, in: Proceedings of AAAI-86, 1986, pp. 910-917; M. Ginsberg, Dynamic backtracking, J. Artif. Intell. Res. 1 (1993) 25-46]. Conflict-directed A* is a fundamental tool for building model-based embedded systems, and has been used to solve a range of problems, including fault isolation [J. de Kleer, B.C. Williams, Diagnosing multiple faults, Artif. Intell. 32(l) (1987) 97-130], diagnosis [J. de Kleer, B.C. Williams, Diagnosis with behavioral modes, in: Proceedings of IJCAI-89, 1989, pp. 1324-1330], mode estimation and repair [B.C. Williams, P. Nayak, A model-based approach to reactive self-configuring systems, in: Proceedings of AAAI-96, 1996, pp. 971-978], model-compilation [B.C. Williams, P. Nayak, A reactive planner for a model-based executive, in: Proceedings of IJCAI-97, 1997] and model-based programming [M. Ingham, R. Ragno, B.C. Williams, A reactive model-based programming language for robotic space explorers, in: Proceedings of ISAIRAS-0 1, 2001]. 0 2006 Elsevier BX All rights reserved.
机译：人工智能传统上使用约束满足和逻辑来解决各种问题，包括计划，诊断，认知机器人和嵌入式系统控制。但是，许多决策问题现在都被重新定义为优化问题，涉及在离散空间中搜索满足一组约束的最佳解决方案。查找最佳解的最佳方法（例如A（*））一次探索一个状态的解空间。本文介绍了冲突导向的A（*），一种解决最佳约束满足问题的方法。冲突导向的A（*）以最佳的一阶顺序搜索状态空间，但是通过消除每个状态周围不一致的子空间来加速搜索过程。这种消除过程建立在基于模型的诊断中所使用的冲突和内核诊断的概念之上[J．德·克莱尔（B.C.）威廉姆斯，《诊断多个故障》，Artif。智力32（1）（1987）97-130; J. de Kleer，A。Mackworth，R。Reiter，“表征诊断和系统”，Artif。智力56（1992）197-222]和在依存关系导向的搜索中[R.斯托曼（G.J. Sussman，用于计算机辅助电路分析的系统中的正向推理和依赖关系定向回溯，Artif。智力9（1977）135-196; J. Gaschnig，某些搜索算法的性能测量和分析，技术报告CMU-CS-79-124，卡内基-梅隆大学，宾夕法尼亚州匹兹堡，1979年;卑诗省J. de Kleer威廉姆斯（Williams），《回溯：控制ATMS》，载于：AAAI-86会议录，1986年，第910-917页; M. Ginsberg，动态回溯，J。Artif。智力Res。 1（1993）25-46]。冲突导向的A *是构建基于模型的嵌入式系统的基本工具，并已用于解决一系列问题，包括故障隔离[J.德·克莱尔（B.C.）威廉姆斯，《诊断多个故障》，Artif。智力32（l）（1987）97-130]，诊断[J.德·克莱尔（B.C.）威廉姆斯（Williams），《行为模式的诊断》，载于：IJCAI-89会议录，1989年，第1324-1330页]，模式估计和修复[B.C. Williams，P.Nayak，一种基于模型的反应式自配置系统方法，于：AAAI-96，1996，pp。971-978），模型编译[B.C.威廉姆斯·P·纳亚克（Williams，P. Nayak），基于模型的主管的被动计划者，见：IJCAI-97会议录，1997年]和基于模型的编程[M. Ingham，R.Ragno，B.C.威廉姆斯，一种针对机器人太空探索者的基于反应模型的编程语言，见：ISAIRAS-0 1，2001的论文集]。 0 2006 Elsevier BX保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号