Why Robots Need Maps
Why Robots Need Maps
复制标题
为什么机器人需要地图
DOI：
10.1007/978-3-540-72951-8_5
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
C. Schindelhauer
中科院分区：
文献类型：
--
作者：
Miroslaw Dynia;Jakub Lopuszanski;C. Schindelhauer
一大批自主的移动实体，如机器人，最初被放置在图的任意节点上，必须共同访问所有节点（不一定是所有边），并最终返回到初始位置。图是事先不知道的（在线设置），机器人必须遍历一条边，以发现图的新部分（边）。该团队可以使用无线通信设备在本地交换信息。
A large group of autonomous, mobile entities e.g. robots initially placed at some arbitrary node of the graph has to jointly visit all nodes (not necessarily all edges) and finally return to the initial position. The graph is not known in advance (an online setting) and robots have to traverse an edge in order to discover new parts (edges) of the graph. The team can locally exchange information, using wireless communication devices.
We compare a cost of the online and optimal offline algorithm which knows the graph beforehand (competitive ratio). If the cost is the total time of an exploration, we prove the lower bound of Ω(log k/ log log k) for competitive ratio of any deterministic algorithm (using global communication). This significantly improves the best known constant lower bound. For the cost being the maximal number of edges traversed by a robot (the energy) we present an improved (4- 2/k)-competitive online algorithm for trees.
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C