Multi-Agent Pickup And Delivery Planning With Transfers
Multi-Agent Pickup And Delivery Planning With Transfers
复制标题
DOI：
10.1184/r1/6720740.v1
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
B. Coltin
中科院分区：
文献类型：
--
作者：
B. Coltin
许多物流问题要求移动代理检索和交付一组项目。例如，邮政服务和快递员检索并交付了信件和包裹，而出租车接送乘客。这些问题是接送和交付问题（PDP）的实例，其中一组移动代理服务一组空间位置的请求。目的是找到一个时间表，以最大程度地减少燃料使用时间或交付时间，这是在时间，车辆能力和任务优先级等限制下。普通PDP是一个经过良好研究的NP困难问题。随着自动移动机器人的功能越来越强大，它们提供了PDP的新应用。实际上，机器人已经部署在仓库中，以检索和准备运输货物，而我们的Cobot机器人自主向办公楼的居住者发送邮件。 PDP的某些变体存在近似算法和启发式方法，其有效性水平不同。在这篇论文中，我将介绍一种新颖的方法，以计划进行多代理检索和传递。每个代理可以将项目转移到其他代理（或代理链）以进行交付的情况下，而不是让单个移动代理检索并交付每个项目。通过在移动代理之间转移项目，可以减少燃油成本和时间。允许转移会增加可能的交付时间表，并导致一个特别具有挑战性的计划问题。在本文中，我将解决在各种约束（例如能力，时间和任务优先级）下进行转移的计划问题。我将同时考虑离线和在线案例，其中未知这些任务。我将评估模拟和物理机器人中转移的计划算法。我已经完成了几个步骤，朝着计划取回和交付转移的物品的整体论文目标。首先，我基于最小跨越树的构造开发了一种近似算法，用于检索一组物品并将其交付到中心位置，仅在拾音器和下降点进行转移。我证明了该算法对最佳解决方案是两种评价的，并且表明只有在这些固定点处传输的最佳解决方案又为最佳解决方案提供了两种适应性，并带有可能发生在任何地方的传输。我表明，转移物品减少了所花费的时间和距离，并演示了Cobot和Crebot机器人上的算法，这些算法执行了办公楼中用户要求的送货任务。 Crebot机器人通过对齐其定制的倾斜托盘自动传输项目。其次，我开发了三种算法来计划使用转移的乘车共享，其中乘客计划从一系列驱动程序中骑行：一种贪婪算法，拍卖算法和基于图中最短路径的算法。这些算法中的每一个都在计算成本和解决方案有效性之间提供了一个权衡。我在旧金山司机采用的路线上证明，在车辆之间转移乘客可以减少燃油使用情况。此外，我已经开发了一种分布式算法来派遣移动机器人来处理由无线传感器网络检测到的事件。在这篇论文中，我将扩展这项工作以开发分布式算法，以计划带有转移的交付。我提出的本文剩下的工作将包括研究问题的在线版本，其中交付任务（以及车辆本身，在
Many logistics problems require mobile agents to retrieve and deliver a set of items. For example, postal services and couriers retrieve and deliver letters and packages, while taxis pick up and drop off passengers. These problems are instances of the Pickup and Delivery Problem (PDP), in which a set of mobile agents services a set of spatially-located requests. The goal is to find a schedule that minimizes fuel usage or delivery time, under constraints such as time, vehicle capacities, and task priorities. The general PDP is a well-studied, NP-hard problem. As autonomous mobile robots become increasingly capable and available, they offer new applications of the PDP. In fact, robots are already deployed in warehouses to retrieve and prepare goods for shipping, and our CoBot robots autonomously deliver mail to occupants of an office building. Approximation algorithms and heuristics exist for some variants of the PDP, with varying levels of effectiveness. In this thesis, I will introduce a novel approach to plan for multi-agent retrievals and deliveries with transfers. Instead of having a single mobile agent retrieve and deliver each item, each agent can transfer items to other agents (or chains of agents) for delivery. By transferring items between mobile agents, a reduction in fuel cost and time is possible. Allowing transfers increases the number of possible delivery schedules exponentially, and leads to an especially challenging planning problem. In this thesis, I will address the problem of planning with transfers under various constraints, such as capacities, times, and task priorities. I will consider both the offline and the online cases, where the tasks are not known beforehand. I will evaluate the algorithms for planning with transfers both in simulation and on physical robots. I have already accomplished several steps towards my overall thesis goal of planning to retrieve and deliver items with transfers. First, I have developed an approximation algorithm, based on the construction of a minimum spanning tree, for retrieving a set of items and delivering them to a central location, with transfers only at pickup and dropoff points. I proved that this algorithm is two-approximate to the optimal solution, and showed that the optimal solution with transfers only at these fixed points in turn gives a two-approximation to the optimal solution with transfers that can occur anywhere. I showed that transferring items reduces the time taken and distance traveled, and demonstrated the algorithm on the CoBot and the CreBot robots, which perform delivery tasks requested by users in an office building. The CreBot robots transfer items autonomously by aligning their custom-built tilting trays. Second, I have developed three algorithms to plan for ridesharing with transfers, in which passengers plan to catch rides from a sequence of drivers: a greedy algorithm, an auction algorithm, and an algorithm based on finding the shortest path in a graph. Each of these algorithms provides a tradeoff between computational cost and solution effectiveness. I demonstrated on routes taken by San Francisco drivers that transferring passengers between vehicles can reduce total fuel use. Furthermore, I have developed a distributed algorithm to dispatch mobile robots to handle events detected by a wireless sensor network. In this thesis, I will extend this work to develop a distributed algorithm to plan for deliveries with transfers. My proposed remaining work for this thesis will include studying the online version of the problem, in which the delivery tasks (and the vehicle routes themselves, in the