• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>PRICAI'98 : Topics in artificial intelligence >Time-Constrained Heuristic Search for Practical Route Finding
【24h】

Time-Constrained Heuristic Search for Practical Route Finding

机译：时间约束启发式搜索，用于实际路线查找

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

摘要

In this paper, we describe a heuristic search algorithm that finds a provably optimal solution subject to a specified time interval. While this algorithm is amenable to previous works on an approximate A~* search with a bounded error (ε), it allows us to terminate the search to retain the specified time interval by changing the value of ε during the search. Our basic search strategy is that node expansion around the starting node is pessimistic (exact search), and we accomplish the approximate exploration of nodes around the goal by increasing ε. This strategy is suitable for real-time route finding in automobile navigation systems. We conducted our experiments to clarify the practical features of the algorithm, using a digital map of a commercial automobile navigation system. The resulting advantage is that the estimation of the finishing time of the search is quite accurate, and optimal solutions are produced by making full use of the permissible search time.
机译：在本文中，我们描述了一种启发式搜索算法，该算法可在指定的时间间隔内找到可证明的最优解。虽然此算法适合先前的有界误差（ε）的近似A〜*搜索的工作，但它允许我们通过在搜索过程中更改ε的值来终止搜索以保留指定的时间间隔。我们的基本搜索策略是起始节点周围的节点扩展是悲观的（精确搜索），我们通过增加ε来完成目标周围节点的近似探索。该策略适用于汽车导航系统中的实时路线查找。我们使用商用汽车导航系统的数字地图进行了实验，以阐明算法的实用功能。由此产生的优点是，对搜索完成时间的估算非常准确，并且可以通过充分利用允许的搜索时间来产生最佳解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号