In the minimum constraint removal ($MCR$), there is no feasible path to move from the starting point towards the goal and, the minimum constraints should be removed in order to find a collision-free path. It has been proved that $MCR$ problem is $NP-hard$ when constraints have arbitrary shapes or even they are in shape of convex polygons. However, it has a simple linear solution when constraints are lines and the problem is open for other cases yet. In this paper, using a reduction from Subset Sum problem, in three steps, we show that the problem is NP-hard for both weighted and unweighted line segments.


翻译:在最低限度限制清除($MCR$)中,没有可行的途径可以从起点走向目标,而且,为了找到一条无碰撞的道路,应该消除最低限度限制,已经证明,当限制有任意的形状,甚至有锥形多边形的形状时,$MCR$问题就是$NP-hard$,然而,当限制是线条,问题尚未解决到其他情况时,它有一个简单的线性解决办法。在本文中,通过减少子元件问题,分三个步骤,我们表明,对于加权和未加权线段来说,问题都很难解决。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
15+阅读 · 2021年3月4日
【开源书】PyTorch深度学习起步,零基础入门(附pdf下载)
专知会员服务
110+阅读 · 2019年10月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Arxiv
0+阅读 · 2021年9月9日
Arxiv
7+阅读 · 2020年6月29日
VIP会员
相关VIP内容
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Top
微信扫码咨询专知VIP会员