The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: the nodes represent positions of a mobile vehicle and the arcs are associated to pre-assigned geometric paths that connect these positions. BASP consists in finding the minimum-time path between two nodes. Differently from SP, we require that the vehicle satisfy bounds on maximum and minimum acceleration and speed, that depend on the vehicle position on the currently traveled arc. We prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data.


翻译:这项工作的目的是介绍和说明“环绕加速最短路径”问题,即“最短路径”问题的一般化问题。这个问题与图表有关:节点代表移动车辆的位置,弧与连接这些位置的预先指定的几何路径有关。“最短路径”是指在两个节点之间找到最短时间路径。与“最短路径”不同,我们要求车辆在最大和最低加速速度方面满足限制,这取决于目前行驶弧上的车辆位置。我们证明,“最短路径”是“最硬”的,我们确定解决方案算法,在问题数据的某些额外假设下实现多米时间兼容性。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
43+阅读 · 2020年9月25日
最新《图嵌入组合优化》综述论文,40页pdf
专知会员服务
34+阅读 · 2020年9月7日
专知会员服务
52+阅读 · 2020年9月7日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
后渗透利用msf关闭防火墙
黑白之道
8+阅读 · 2019年8月24日
Kali Linux 渗透测试:密码攻击
计算机与网络安全
16+阅读 · 2019年5月13日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
【关关的刷题日记60】Leetcode 437. Path Sum III
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月27日
Arxiv
0+阅读 · 2021年4月26日
Arxiv
0+阅读 · 2021年4月21日
VIP会员
相关VIP内容
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
后渗透利用msf关闭防火墙
黑白之道
8+阅读 · 2019年8月24日
Kali Linux 渗透测试:密码攻击
计算机与网络安全
16+阅读 · 2019年5月13日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
【关关的刷题日记60】Leetcode 437. Path Sum III
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员