首页> 美国政府科技报告 >Solving a Class of Spatial Reasoning Problems: Minimal-Cost Path Planning in the Cartesian Plane
【24h】

Solving a Class of Spatial Reasoning Problems: Minimal-Cost Path Planning in the Cartesian Plane

机译:解决一类空间推理问题:笛卡尔平面中的最小费用路径规划

获取原文

摘要

This work presents an algorithm to solve a two-dimensional weighted-region problem that requires finding the least-cost regions. Such regions have a constant cost rate per unit distance accrued by paths passing through them. Conventional graph search applies standard search strategies to graphs whose links represent the only possible paths. We use Snell's law as a local-optimality criterion to create corresponding graphs for the weighted-region problem; the nodes in our graphs represent areal subdivisions of the physical environment. The performance of our Snell's-law-based algorithm is compared to that of a dynamic-programming, wavefront-propagation technique. Test results show average-case superiority of the Snell's-law-based algorithm, as measured by time, space and solution-path cost. We present a criterion to predict the time for the wavefront-propagation algorithm and the Snell's-law algorithm to solve problems; this allow the selection of the fastest algorithm. We also develop improvements to the wavefront-propagation algorithm that decrease its average-case time requirements and we prove properties of Snell's law when applied to the weighted-region problem.

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号