An Efficient Algorithm for the Fast Delivery Problem

We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, init...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-08
Main Authors: Carvalho, Iago A, Erlebach, Thomas, Papadopoulos, Kleitos
Format: Article
Language:English
Subjects:
Agents (artificial intelligence)
Algorithms
Delivery scheduling
Graph theory
Intelligent agents
Nodes
Schedules
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in a source node s, to a destination node y. The delivery is achieved by the collective effort of the autonomous mobile agents, which can carry and exchange the package among them. The objective is to compute a delivery schedule that minimizes the delivery time of the package. In this paper, we propose an O(kn log n + km) time algorithm for this problem. This improves the previous state-of-the-art O(k^2 m + k n^2 + APSP) time algorithm for this problem, where APSP stands for the running-time of an algorithm for the All-Pairs Shortest Paths problem.
ISSN:2331-8422
DOI:10.48550/arxiv.1904.09142