Efficient Delivery with Mobile Agents
Efficient Delivery with Mobile Agents
复制标题
通过移动代理实现高效交付
DOI：
10.3929/ethz-b-000232464
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Andreas Bärtschi
中科院分区：
文献类型：
--
作者：
Andreas Bärtschi
最近的技术进步允许低成本大规模生产小型和简单的移动的机器人。电池驱动的自动驾驶汽车和无人机是一些最广泛的例子。最近，有尝试部署这样的自主代理，以提供物理货物-包。在未来，为了在更长的距离上递送包裹，一群代理是一个可能的选择，因为代理的能量供应是有限的，或者代理将被要求在本地操作，或者仅仅因为一些代理的使用比其他代理更昂贵。在这篇论文中，我们考虑的问题，提供m包之间指定的源-目标对在一个无向图，由k个移动的代理最初位于不同的节点。每个智能体ai都有一个权重ωi，它定义了在图中行进一段距离时的能量消耗率，它可以移动的速度β i，以及指定初始可用能量资源的预算βi。这些参数引起了大量的优化和决策问题的代理人的操作。具体来说，我们的目标是奠定理论基础的集中式算法的设计问题，提供所有的包，受一个或多个三个重要的优化目标：能源效率-最大限度地减少所有代理的总能耗。时间效率-最大限度地减少所有包裹的交付时间。资源效率-尊重代理人的有限资源。我们研究计算的易处理性，以及近似和资源增强的解决方案，为每个这些目标单独，并结合能源和时间效率。
Recent technological progress allows for low-cost mass production of small and simple mobile robots. Battery-powered self-driving vehicles and drones are some of the most widely spread examples. Recently, there are attempts to deploy such autonomous agents to deliver physical goods – packages. In the future, for a delivery of packages over longer distances, a swarm of agents is a likely option to be adapted, since the energy supply of the agents is limited, or the agents will be required to operate locally, or simply because the usage of some agents is more costly than others. In this thesis, we consider the problem of delivering m packages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes. Each agent ai has a weight ωi that defines the rate of energy consumption while traveling a distance in the graph, a velocity υi with which it can move, and a budget βi specifying the initially available energy resource. These parameters give rise to plentiful optimization and decision problems regarding the operation of the agents. Specifically, we aim to lay the theoretical foundations for the design of centralized algorithms for the problem of delivering all packages, subject to one or more of three important optimization goals: Energy-efficiency – minimize the total energy consumption of all agents. Time-efficiency – minimize the delivery time of all packages. Resource-efficiency – respect the constrained resources of the agents. We study the computational tractability as well as approximative and resource-augmented solutions for each of these objectives individually, and for combinations of energyand time-efficiency.