...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Automatic Control >Traveling Salesperson Problems for the Dubins Vehicle
【24h】

Traveling Salesperson Problems for the Dubins Vehicle

机译：杜宾斯汽车的旅行销售人员问题

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

摘要

In this paper, we study minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction. Motivated by autonomous aerial vehicle applications, we consider the traveling salesperson problem for the Dubins vehicle (DTSP): given n points on a plane, what is the shortest Dubins tour through these points, and what is its length? First, we show that the worst-case length of such a tour grows linearly with n and we propose a novel algorithm with performance within a constant factor of the optimum for the worst-case point sets. In doing this, we also obtain an upper bound on the optimal length in the classical point-to-point problem. Second, we study a stochastic version of the DTSP where the n targets are randomly and independently sampled from a uniform distribution. We show that the expected length of such a tour is of order at least n 2/3 and we propose a novel algorithm yielding a solution with length of order n 2/3 with probability one. Third and finally, we study a dynamic version of the DTSP: given a stochastic process that generates target points, is there a policy that guarantees that the number of unvisited points does not diverge over time? If such stable policies exist, what is the minimum expected time that a newly generated target waits before being visited by the vehicle? We propose a novel stabilizing algorithm such that the expected wait time is provably within a constant factor from the optimum.
机译：在本文中，我们研究了Dubins车辆（即非完整车辆）的最短时间运动规划和路线选择问题，该车辆必须沿有界曲率的平面路径移动而不会反转方向。受自动驾驶飞行器应用的推动，我们考虑了杜宾斯飞机（DTSP）的旅行销售人员问题：给定飞机上的n个点，经过这些点最短的杜宾斯旅行是什么，它的长度是多少？首先，我们证明了这种巡演的最坏情况长度随n线性增长，并且我们提出了一种新算法，其性能在最坏情况点集的最优常数范围内。在此过程中，我们还获得了经典点对点问题中最佳长度的上限。其次，我们研究了DTSP的随机版本，其中从均匀分布中随机且独立地采样了n个目标。我们证明了这种巡回的预期长度至少约为n 2/3，并且我们提出了一种新颖的算法，该算法以概率1产生了长度为n 2/3的解。第三，也是最后，我们研究了动态DTSP：在产生目标点的随机过程中，是否有一项政策可以保证未访问点的数量不会随时间变化？如果存在这种稳定的策略，那么新生成的目标在被车辆访问之前等待的最短预期时间是多少？我们提出了一种新颖的稳定算法，以使预期的等待时间可证明在距最佳值恒定的范围内。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号