.png){kind=icon}
返回
Deterministic Robot-Network Localization is Hard
.png){kind=icon}
PRE
AI
DOI：10.1109/TRO.2010.2042753.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper provides a complexity study of the deterministic localization problem in robot networks using local and relative observations only. This is an important issue in collective and cooperative robotics where global positioning systems (GPS) are not available, and the basic premise is the localization ability of the group. We prove that given a set of relative observations made by the robots, the unique unambiguous pose estimation of the robot network in a deterministic way is an NP-hard problem. This means that no polynomial-time algorithm can deterministically solve the unique pose estimation problem based on relative observations unless P = NP. The consequence is that no guarantee can be provided, in a polynomial time, that the possibly estimated poses of the robots will correspond to the effective (actual) ones. The proof is based on complexity theory where we build appropriate polynomial-time reductions interrelating the multirobot localization problem to a well-known NP-complete problem (the partition problem). This NP-hardness result opens questions and perspectives for research into approximations to overcome its intractability.
Keyword:
Computational complexity
distributed robot systems
localization
networked robots
relative observations
期刊
IF:
10.5
论文数:
3.3K
被引数:
2.8W
机构
引用论文
Optimised Anaesthesia to Reduce Post Operative Cognitive Decline (POCD) in Older Patients Undergoing Elective Surgery, a Randomised Controlled Trial.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAI分享收藏Spatial–Temporal Model to Identify the Deformation of Underlying High-Speed Railway Infrastructure
PREAI
分享收藏
查看更多内容