Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
复制标题
能量共享低功耗移动机器人协同交付
DOI：
10.1007/978-3-319-72751-6_1
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Christina Karousatou
中科院分区：
文献类型：
--
作者：
E. Bampas;S. Das;D. Dereniowski;Christina Karousatou
我们研究了两种不同类型的能量共享移动机器人的配送问题。每个移动机器人在任何给定的时刻最多可以存储两个单位的能量，当两个机器人在同一位置时，它们可以在彼此之间传递能量，而不考虑最大容量。机器人在一个简单的图表中运行，最初每个机器人有两个能量单位。机器人的单条边遍历减少了一个单位的能量，并且机器人只能在最初具有至少一个单位的能量的情况下执行这种移动。图中有两个不同的节点S和t，机器人的目标是将最初出现在S上的包裹递送到节点t。当一个机器人放置在一起时，包裹可以从一个机器人传递到另一个机器人。在我们研究的第一个问题中，机器人最初被放置在图的某些给定节点上，问题是交付是否可行。我们证明了这个问题是\(\mathsf{NP}\)-完全的。在第二个问题中，机器人的初始位置不是固定的，而是将图中节点H的子集与整数k一起作为输入，问题如下：是否存在k个机器人在H中的节点处的放置使得交付是可能的？我们证明了这个问题可以在多项式时间内求解。
We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one unit and the robot can only perform such move initially having at least one unit of energy. There are two distinguished nodes s and t in the graph and the goal for the robots is to deliver the package initially present on s to the node t. The package can be passed from one robot to another when they are colocated. In the first problem we study, the robots are initially placed at some given nodes of the graph and the question is whether the delivery is feasible. We prove that this problem is \(\mathsf {NP}\)-complete. In the second problem, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is as follows: is there a placement of k robots at nodes in H such that the delivery is possible? We prove that this problem can be solved in polynomial time.