Nazim Haouchine

Parikshit Juvekar

Alexandra Golby

William M Wells

Stephane Cotin

Sarah Frisken

Alignment of Cortical Vessels viewed through the Surgical Microscope with Preoperative Imaging to Compensate for Brain Shift

Keywords: Brain Shift, Non-rigid registration, Biomechanical Modelling, Augmented Reality, Image-guided Neurosurgery

Brain shift is a non-rigid deformation of brain tissue that is affected by loss of cerebrospinal fluid, tissue manipulation and gravity among other phenomena. This deformation can negatively influence the outcome of a surgical procedure since surgical planning based on pre-operative image becomes less valid. We present a novel method to compensate for brain shift that maps preoperative image data to the deformed brain during intra-operative neurosurgical procedures and thus increases the likelihood of achieving a gross total resection while decreasing the risk to healthy tissue surrounding the tumor. Through a 3D/2D non-rigid registration process, a 3D articulated model derived from pre-operative imaging is aligned onto 2D images of the vessels viewed through the surgical miscroscopic intra-operatively. The articulated 3D vessels constrain a volumetric biomechanical model of the brain to propagate cortical vessel deformation to the parenchyma and in turn to the tumor. The 3D/2D non-rigid registration is performed using an energy minimization approach that satisfies both projective and physical constraints. Our method is evaluated on real and synthetic data of human brain showing both quantitative and qualitative results and exhibiting its particular suitability for real-time surgical guidance.

INTRODUCTION

Intra-operative brain shift is a well-known phenomenon that describes movement and deformation of the brain in terms of its anatomical and physiological position in the skull during neurosurgery. [START_REF] Bayer | Intraoperative imaging modalities and compensation for brain shift in tumor resection surgery[END_REF][START_REF] Miga | Clinical evaluation of a model-updated image-guidance approach to brain shift compensation: experience in 16 cases[END_REF] Several methods have been proposed in the literature to estimate brain shift using pre-operative and intra-operative image data using various types of imaging techniques such as Cone-Beam Computed Tomography, [START_REF] Pereira | Volumetric Measurements of Brain Shift Using Intraoperative Cone-Beam Computed Tomography: Preliminary Study[END_REF] B-mode ultra-sound [START_REF] Ji | Mutual-information-based image to patient reregistration using intraoperative ultrasound in image-guided neurosurgery[END_REF] , 5 Doppler ultra-sound, [START_REF] Reinertsen | Intra-operative correction of brain-shift[END_REF] Laser range scanner [START_REF] Sun | Near real-time computer assisted surgery for brain shift correction using biomechanical models[END_REF] or intra-operative MRI. [START_REF] Kuhnt | Brain shift compensation and neurosurgical image fusion using intraoperative mri: Current status and future challenges[END_REF] Most of these methods are solely based on image processing since they do not involve additional pre-operative preparation. In Filipe et al., [START_REF] Marreiros | Non-rigid deformation pipeline for compensation of superficial brain shift[END_REF] a non-rigid deformation pipeline using superficial vessel centerlines have been proposed. The method uses Thin Plate Spline (TPS) to compute the deformation and Coherent Point Drift (CPD) for centerline registration. More advanced methods than CPD have been evaluated for the non-rigid registration stage. In Bayer et al., [START_REF] Bayer | Intraoperative brain shift compensation using a hybrid mixture model[END_REF] a Hybrid Mixture Model is used and outperforms the classic CPD approach. This method is combined with TPS-like interpolation to generate a dense deformation field. In Machado et al., [START_REF] Machado | Non-rigid registration of 3d ultrasound for neurosurgery using automatic feature detection and matching[END_REF] a feature-based active registration method is proposed. 3D SIFT-Rank is used to find correspondences and estimate dense mappings throughout the image. This method was shown to be robust in clinical routines and can benefits from additional landmarks selected by surgeons thanks to an active framework. [START_REF] Luo | A feature-driven active framework for ultrasound-based brain shift compensation[END_REF] Instead of using geometric models such as TPS to compute deformation, several approaches proposed to use biomechanical models. [START_REF] Sun | Near real-time computer assisted surgery for brain shift correction using biomechanical models[END_REF][START_REF] Miga | Computational modeling for enhancing soft tissue image guided surgery: An application in neurosurgery[END_REF][START_REF] Morin | Brain-shift compensation using intraoperative ultrasound and constraint-based biomechanical simulation[END_REF][START_REF] Garlapati | More accurate neuronavigation data provided by biomechanical modeling instead of rigid registration[END_REF][START_REF] Luo | An integrated multi-physics finite element modeling framework for deep brain stimulation: Preliminary study on impact of brain shift on neuronal pathways[END_REF][START_REF] Mohammadi | Estimation of intraoperative brain shift by combination of stereovision and doppler ultrasound: phantom and animal model study[END_REF] Recently, Morin et al. [START_REF] Morin | Brain-shift compensation using intraoperative ultrasound and constraint-based biomechanical simulation[END_REF] measured brain shift at the brain surface and sub-surface vessels using intraoperative doppler-based ultrasound and then used physics-based models to propagate the deformation to regions of the brain where arteries are not present. In Sun et al. [START_REF] Sun | Near real-time computer assisted surgery for brain shift correction using biomechanical models[END_REF] pre-computed atlases of the brain are used to simulate brain shift following a sparse set if image-points extracted from the cortical brain surface using an optically tracked portable laser range scanner. In Luo et al. [START_REF] Luo | A comprehensive model-assisted brain shift correction approach in image-guided neurosurgery: a case study in brain swelling and subsequent sag after craniotomy[END_REF] an optically tracked stylus is used to identify cortical surface vessel features; these features are integrated in a model-based workflow to estimate brain shift correction after craniotomy and dural opening. Stereovision has been used as a means to capture the shape of the exposed brain and infer the deformation caused by brain shift. The method proposed by Mohammadi et al. [START_REF] Mohammadi | Estimation of intraoperative brain shift by combination of stereovision and doppler ultrasound: phantom and animal model study[END_REF] used a projection-based stereovision process to map brain surface with a pre-operative finite element model. The projection of a pre-defined pattern permits to recover the 3D shape of the brain that is coupled with ultrasound imaging to perform a non-rigid registration. Ji et al. [START_REF] Ji | Cortical surface shift estimation using stereovision and optical flow motion tracking via projection image registration[END_REF] proposed to combine optical flow and stereovision constraints to reconstruct a 3D dense brain surface at two different surgical stages leading to obtain an undeformed and deformed surface. A non-rigid registration between the underformed and deformed surface is used to determine the deformation of the exposed brain surface during surgery.

In this paper we propose a vessel-based method to register pre-operative scans onto intra-operative images captured through the surgical microscope. Our method uses cortical vessels at the surface since images of the brain surface from the craniotomy are available in real-time through the oculars of the microscope (or possibly a ceiling mounted camera) while intra-operative ultra sound and intra-operative MRI both require significant cost and time. In comparison to previous methods, we rely solely on a single image acquired from the surgical microscope, to avoid tedious calibration of the stereo camera, laser range finder or optical stylus, which makes previous approaches impractical in most hospital settings. This narrows down our problem to a 3D/2D non-rigid registration between undeformed 3D centerlines and deformed 2D centerlines that can be solved by satisfying a combination of physical and projective constraints. The surface deformation estimated by this method is then propagated to the rest of the brain using a biomechanical model, built from pre-operative MRI scans, that has proven to be fast and reliable to model the brain tissue and its inner structures. [START_REF] Mendizabal | Face-based smoothed finite element method for real-time simulation of soft tissue[END_REF][START_REF] Bilger | Biomechanical simulation of electrode migration for deep brain stimulation[END_REF] Intra-operative Image Figure 1: Overview of our pipeline: inputs of our system consist of a single intra-operative image acquired from the surgical microscope and a model of brain surface derived from the pre-operative MRI. A 3D/2D non-rigid registration method is applied to align the vessels. This alignment is propagated to the rest of the brain using a biomechanical model to provide a 3D model of brain shift.

METHODS

Method overview

Our approach updates the pre-operative neurosurgical plan (particularly the tumor position) by taking into account the intra-operative brain shift. As shown in the pipeline of figure 1, at any time t, inputs to our registration system include a single monocular image, I , acquired intra-operatively via the surgical microscope and a 3D model of the cortical vessels, V , derived from the pre-operative MRI. A 3D/2D non-rigid registration method is applied to align the vessels to the image. This registration deforms the vessels while preserving its physical consistency. This deformation estimates a shift of the whole brain (global) from a sub-part of the brain surface (local). The local deformation is converted to a global deformation using a biomechanical model that propagates the location deformation of cortical veins to deep structures including vessels and the tumor.

Data processing and problem formulation

The first stage of our pipeline is processing the input intra-operative image I and pre-operative vessels V . We chose to rely on vascular network graphs (or centerlines) to perform our non-rigid registration (see figure 2). Indeed, centerlines represent an effective shape abstraction over using the complete vascular network and can be manipulated more easily.

For this preliminary study, extracting centerlines from I is done manually, by interactively selecting a set of points representing the starting and ending points of vessel segments. More advanced methods exist, either supervised or unsupervised [START_REF] Fraz | Blood vessel segmentation methodologies in retinal images -a survey[END_REF][START_REF] Ding | Automatic segmentation of cortical vessels in pre-and post-tumor resection laser range scan images[END_REF] and could be easily plugged in our pipeline. We denote U = {u j 2 R 2 }, the set of 2D points corresponding to the intra-operative centerlines. Extracting the centerlines from V is done by first segementing the MRI scans and building a triangulated surface mesh of the vessels. This mesh is then iteratively thinned using mean curvature skeletonization [START_REF] Tagliasacchi | Mean curvature skeletons[END_REF] to obtain the final centerlines that we denote V = {v i 2 R 3 }.

Our goal is to find the transformation function F so that U = F (P,R,t,d u) (V) where P is the camera matrix that transforms camera coordinates to world coordinates, R and t are respectively the rotation and translation matrices representing rigid transformation components and d u is the non-rigid transformation component.

Modelling the vessels and its surrounding tissues

Let S be a 3D triangulated surface mesh of the brain generated from pre-operative MRI scans that includes the parenchyma, internal structures such as vessels or tumors, and constraints from surrounding anatomical information such as the skull. [START_REF] Bilger | Biomechanical simulation of electrode migration for deep brain stimulation[END_REF] The mesh S allows us to build a physical model incorporating tissue properties and biomechanical behavior (see Figure 3). This physical model is characterized by a geometry S and a stiffness matrix K that describe physical properties such as tissue elasticity, damping or viscosity. In order to account for tissue heterogeneity, the stiffness matrix of the whole brain is a mechanical composition of paranchyma and vessel stiffness properties. This mechanical coupling permits the propagation of vessel deformation to the paranchyma and the tumor. In practice, the global stiffness matrix is built so that each element of the parenchyma model that intersects a vessel centerline has a higher stiffness.

The deformation is specified by its stress-strain relationship. The brain deformation is computed using a non-linear geometric finite element method, with a linear constitutive law, [START_REF] Nealen | Physically based deformable models in computer graphics[END_REF] where the finite element model is meshed with linear hexahedrons. This allows for rotation in the model, while relying on a linear expression of the stress-strain relationship.

The equation relating the external forces f to the nodal displacements x can be written as f = K(x)d x.

Energy-based Non-rigid Registration

As most of the registration algorithms, our non-registration has an intialization phase. This consists of a rigid alignment, done manually, that permits to initialize the rotation matrix R and translation vector t. With R and t set, a correspondences vector C = {c i 2 N} can be built. This vector is built so that if a source point v i corresponds to a target point u j then c i = j for each point of the source set. Having the biomechanical model on one hand and the set of correspondences C on the other hand, we can update the pre-operative 3D mesh S by registering the pre-operative centerlines V with the intra-operative centerlines U that minimizes the physical energy of the biomechanical model. This leads to the following energy minimization expression:

min d u Physical consistency z }| { 1 2 kd u > Kd uk + Image fitting z }| { Â i2n C 1 2 kkv i Pu c i k 2 ! ( 1
)
where k is the stiffness coefficient that ties the source and target centerlines to compute the bending energy. Note the subscript c i that denotes the correspondence indices between the two point sets. The image fitting term can be considered as sightlines coming from the camera position to the 2D centerlines that enforces the physical model to fit the image.

RESULTS

Simulated Data

We tested our method on synthetic data of a complete human brain. The vessel centerlines were extracted from the vessels and linearly down-sampled to permit a point-to-point vessel matching. The number of centerlines nodes after down-sampling is 102 nodes. The biomechanical brain model is derived from the triangular mesh using Delaunay volume triangulation. In our tests, both hemispheres are meshed with approximately 1000 tetrahedrons. The stiffness matrix is built with a Young's modulus E set to 3000 Pa and Poisson's ratio to 0.45. We used the SOFA framework to build the biomechanical model. We quantitatively evaluated our method by measuring the registration error on tumors. We considered 3 tumors at different locations close to the surface (see figure 4-a). We simulated the brain shift under two different scenarios: the first one mimicked the brain sliding towards the back of the skull under gravity as illustrated in figure 4-b and the second simulates a protrusion deformation that can occur due to brain swelling after the craniotomy as illustrated in figure 4-c. From the simulated data we extracted the 3D vessel centerlines to perform the matching where we added Gaussian noise with a standard deviation of 5 mm and a 5 clustering decimation on a subset of points composing the centerlines. We calculated the error as the Euclidean distance between the center of mass of the simulated tumors and the ones measured using our method. The results reported in figure 5 show the registration error for each tumor. Depending on the location of the tumors, we measured a distance error ranging from 0.63 mm to 2 mm with a vessel correspondence of 50% which corresponds to a 81% and 68% brain-shift correction respectively (The brain-shift correction is measured as the difference between the initial error and the corrected error divided by the initial error).

In addition to tumor locations, we measured the registration error on the brain surface using Hausdorff distance. As shown in Figure 6, the maximum measured Hausdorff distance was 3.2 mm with a vessel correspondence of 50%. We can also observe that gravity-induced deformation generates less errors than deformations caused by brain swelling at the site of the craniotomy. We furthermore downgraded the matching quality by decreasing the number of vessel correspondences, from 90% to 10% to demonstrate the capability of the model to interpolate deformation where no image information is available. As shown in figures 5 and 6 the registration error on the tumors and the brain surface decreases monotonically as the number of We tested our method on a subset of centerlines nodes to get closer to a craniotomy case where only a small part of the brain is visible. This subset is composed of 8 nodes regularly distributed over the centerlines. We plotted in Figure 7 the actual registration error between the estimated tumors' positions and the ground truth positions for both type of deformation. The errors are more important compared to the global registration but are still acceptable with a minimal distance of 1.08 mm and a maximal distance of 2.61 mm. Tumor 2 located near the visible surface vessel subset exhibits the lowest distance errors while the tumor 3 located deeper w.r.t the selected surface shows the highest distance errors.

Real Data

We tested our method on real data using images acquired from a Carl Zeiss surgical microscope. The scope is equipped with two cameras with a video frame rate of approximately 30 frames per second. We used only the left image. The pre-operative mesh is first aligned manually on the image to obtain the rigid transform, then, the non-rigid refinement is performed, which will drive the whole brain mesh. The Figure 8 shows the non-registration process and the resulting mesh-to-image overlay.

CONCLUSION

We propose a method to update pre-operative neurosurgical planning by taking into account brain deformation induced by brain shift. Our method follows a 3D/2D non-rigid process between pre-operative and intra-operative cortical vessels centerlines using a single image instead of a stereo pair. Our method shows promising results in estimating brain tumor positions subject to two common types of brain shift, a gravity-induced deformation and a protrusion deformation. In addition, our results suggest that cortical vessels can be considered as strong features to estimate brain shift deformation.

This approach can be used for neurosurgical navigation when vessels visible on the surface can be captured using a surgical microscope.

Future work will consist of extending the experiments on real data with surgical conditions and include an automated algorithm for vessels' centerlines extraction from microscopic images.

Pre

Figure 2 :

 2 Figure 2: Input data processing: (a) interactive points selection, (b) centerlines between starting and ending points, (c) preoperative vessel with region of interest, (d) zoom on the region on interest, (e) centerline extraction using mean curvature skeletonization.

Figure 3 :

 3 Figure 3: Constructing the biomechanical model: (a) a 3D surface model S derived from the preoperative MRI scan and (b) a 3D hexahedral volume model generated using the geometrical properties and the stiffness matrix

26

 26

Figure 4 :

 4 Figure 4: Synthetic data experiments: (a) tumor positions inside the brain, tumor 1 is in purple, tumor 2 is in yellow and tumor 3 is in green. (b) Simulated force applied to mimic brain sliding towards the back of the skull. (c) Simulated force applied to mimic protrusion deformation that occurs during craniotomy.

Figure 5 :

 5 Figure 5: Quantitative evaluation of registration error on tumors.

Figure 6 :

 6 Figure 6: Color maps corresponding to the registration errors for the simulated data experiments: (a) and (b): brain surface registration errors for gravity-induced deformation with 10% matching and 90% matching respectively, (c) and (d) brain surface registration errors for protrusion deformation with 10% matching and 90% matching respectively.

Figure 7 :

 7 Figure 7: Registration errors on a sub part of the brain for both types of deformations.

Figure 8 :

 8 Figure 8: Experiments using real-world data: (a) inital rigid registration, (b) non-rigid registration, (c) alternate point of view showing the 2D constraints and (d) deformation propagation onto the volume model

ACKNOWLEDGEMENTS

The authors were supported by the following funding bodies and grants: NIH: R01 EB027134-01, NIH: R01 NS049251 and BWH Radiology Department Research Pilot Grant Award.


Jérémie Chalopin

Andreas Bärtschi
email: baertschi@inf.ethz.ch

Shantanu Das

Yann Disser

Barbara Geissmann

Daniel Graf

Arnaud Labourel

Matúš Mihalák

Collaborative delivery with energy-constrained mobile robots

Keywords: delivery, mobile agents, limited battery, resource augmentation, budget

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

We consider a team of mobile robots which are assigned a task that they need to perform collaboratively. Even simple tasks such as collecting an item and delivering it to a target location can become challenging when it involves the cooperation of several agents. The difficulty of collaboration can be due to several limitations of the agents, such as limited communication, restricted vision or the lack of persistent memory, and this has been the subject of extensive research (see [START_REF] Flocchini | Distributed Computing by Oblivious Mobile Robots[END_REF] for a recent survey). When considering agents that move physically (such as mobile robots or automated vehicles), a major limitation of the agents are their energy resources, which restricts the travel distance of the agent. This is particularly true for small battery operated robots or drones, for which the energy limitation is the real bottleneck. We consider a set of mobile agents where each agent i has a budget B i on the distance it can move, as in [START_REF] Anaya | Convergecast and broadcast by power-aware mobile agents[END_REF][START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF]. We model their environment as an undirected edge-weighted graph G, with each agent starting on some vertex of G and traveling along edges of G, until it runs out of energy and stops forever. In this model, the agents are obliged to collaborate as no single agent can usually perform the required task on its own. Our goal is to design centralized algorithms for the agents for such a type of collaboration.

The problem we consider is that of moving some physical item (henceforth called package) from a given source location to a target location in the graph G using a subset of the agents. Although the problem sounds simple, finding a valid schedule for the agents to deliver the package is computationally hard, even if we are given full information on the graph and the location of the agents. Given a graph G with designated source and target vertices, and k agents with given starting locations and energy budgets, the decision problem of whether the agents can collectively deliver a single package from the source to the target node in G is called BudgetedDelivery. Chalopin et al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF][START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF] showed that Non-Returning BudgetedDelivery is weakly NP-hard on paths and strongly NP-hard on general graphs.

Unlike previous papers, we also consider a version of the problem where each agent needs to return to its starting location after completing its task. This is a natural assumption, e.g. for robots that need to return to their docking station for maintenance or recharging. We call this variant Returning BudgetedDelivery. Surprisingly, this variant of the problem is easier to solve when the graph is a tree (unlike the original version of the problem), but we show it to be strongly NP-hard even for planar graphs. We present a polynomial time algorithm for solving Returning BudgetedDelivery on trees.

For arbitrary graphs, we are interested in resource-augmented algorithms. Since finding a feasible schedule for BudgetedDelivery is computationally hard when the agents have just enough energy to make delivery possible, we consider augmenting the energy of each robot by a constant factor γ, to enable a polynomial-time solution to the problem. Given an instance of Budgeted-Delivery and some γ > 1, we have a γ-resource-augmented algorithm, if the algorithm, running in polynomial time, either (correctly) answers that there is no feasible schedule, or finds a feasible schedule for the modified instance with augmented budgets Bi = γ • B i for each agent i.

Our Model. We consider an undirected edge-weighted graph G = (V, E) with n = |V | vertices and m = |E| edges. The weight (think length) w(e) of an edge e ∈ E defines the energy required to cross the edge in either direction in the following sense: We have k mobile agents which are initially placed on arbitrary nodes p 1 , . . . , p k of G, called starting positions. Each agent i has an initially assigned energy budget B i ∈ R ≥0 and can move along the edges of the graph, for a total distance of at most B i (if an agent travels only on a part of an edge, its traveled distance is downscaled proportionally to the part traveled). The agents are required to move a single package from a given source node s to a target node t. An agent can pick up the package from its current location, carry it to another location (a vertex or a point inside an edge), and drop it there. Agents have global knowledge of the graph and are controlled by a central entity.

Given a graph G with vertices s = t ∈ V (G) and the starting nodes and budgets for the k agents, we define BudgetedDelivery as the decision problem of whether the agents can collectively deliver the package without exceeding their individual budgets. In Returning BudgetedDelivery each agent needs to return to its respective starting position before using up its energy budget; in the Non-Returning version we do not place such a restriction on the agents and an agent may terminate at any location in the graph.

A solution to BudgetedDelivery is given in the form of a schedule which prescribes for each agent whether it moves and if so, the two locations in which it has to pick up and drop off the package. A schedule is feasible if the package can be delivered from s to t.

Related Work. Delivery problems in the graph have been usually studied for a single agent moving in the graph. For example, the well known Traveling salesman problem (TSP) or the Chinese postman problem (CPP) require an agent to deliver packets to multiple destinations located in the nodes of the graph or the edges of the graph. The optimization problem of minimizing the total distance traveled is known to be NP-hard [START_REF] Applegate | The Traveling Salesman Problem: A Computational Study[END_REF] for TSP, but can be solved in polynomial time for the CPP [START_REF] Edmonds | Matching, euler tours and the chinese postman[END_REF]. When the graph is not known in advance, the problem of exploring a graph by a single agent has been studied with the objective of minimizing the number of edges traversed (see e.g. [START_REF] Panaite | Exploring unknown undirected graphs[END_REF][START_REF] Albers | Exploring unknown environments[END_REF]). Exploration by a team of two agents that can communicate at a distance has been studied by Bender and Slonim [START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF] for digraphs without node identifiers. The model of energy-constrained robot was introduced by Betke et al. [START_REF] Betke | Piecemeal learning of an unknown environment[END_REF] for single agent exploration of grid graphs. Later Awerbuch et al. [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] studied the same problem for general graphs. In both these papers, the agent could return to its starting node to refuel and between two visits to the starting node, the agent could traverse at most B edges. Duncan et al. [START_REF] Duncan | Optimal constrained graph exploration[END_REF] studied a similar model where the agent is tied with a rope of length B to the starting location and they optimized the exploration time, giving an O(m) time algorithm.

For energy-constrained agents without the option of refueling, multiple agents may be needed to explore even graphs of restricted diameter. Given a graph G and k agents starting from the same location, each having an energy con-straint of B, deciding whether G can be explored by the agents is NP-hard, even if the graph G is a tree [START_REF] Fraigniaud | Collective tree exploration[END_REF]. Dynia et al. studied the online version of the problem [START_REF] Dynia | Power-aware collective tree exploration[END_REF][START_REF] Dynia | Why robots need maps[END_REF]. They presented algorithms for exploration of trees by k agents when the energy of each agent is augmented by a constant factor over the minimum energy B required per agent in the offline solution. Das et al. [START_REF] Das | Collaborative exploration by energy-constrained mobile robots[END_REF] presented online algorithms that optimize the number of agents used for tree exploration when each agent has a fixed energy bound B. On the other hand, Dereniowski et al. [START_REF] Dereniowski | Fast collaborative graph exploration[END_REF] gave an optimal time algorithm for exploring general graphs using a large number of agents. Ortolf et al. [START_REF] Ortolf | Online multi-robot exploration of grid graphs with rectangular obstacles[END_REF] showed bounds on the competitive ratio of online exploration of grid graphs with obstacles, using k agents.

When multiple agents start from arbitrary locations in a graph, optimizing the total energy consumption of the agents is computationally hard for several formation problems which require the agents to place themselves in desired configurations (e.g. connected or independent configurations) in a graph. Demaine et al. [START_REF] Demaine | Minimizing movement[END_REF] studied such optimization problems for multiple identical agents and provided approximation algorithms and inapproximability results. Similar problems have been studied for agents moving in the visibility graphs of simple polygons; optimizing either the total energy consumed or the maximum energy consumed per agent can be hard to approximate even in this setting, as shown by Bilo et al. [START_REF] Bilò | Polygon-constrained motion planning problems, in: 9th International Symposium on Algorithms and Experiments for Sensor Systems[END_REF]. For the case where the graph is a continuous line, Czyzowicz et al. [START_REF] Czyzowicz | On minimizing the maximum sensor movement for barrier coverage of a line segment[END_REF] studied the barrier coverage problem, where sensors, represented by individual intervals, have to be moved so that they collectively cover a given interval. They showed that the maximum movement can be minimized efficiently. Dobrev et al. [START_REF] Dobrev | Complexity of barrier coverage with relocatable sensors in the plane[END_REF] later studied the more general problem for mobile sensors in a plane with several intervals to cover.

A recent paper studies energy-efficient delivery of multiple packages by heterogeneous agents, which have different rates of energy consumption (but no constraints on the amount of energy they can use) [START_REF] Bärtschi | Energy-efficient Delivery by Heterogeneous Mobile Agents[END_REF][START_REF] Bärtschi | Energy-efficient Delivery by Heterogeneous Mobile Agents[END_REF]. This setting also allows for the design of truthful mechansims [START_REF] Bärtschi | Truthful Mechanisms for Delivery with Mobile Agents[END_REF], in a game-theoretic model, where the rate of energy consumption is information private to each agent. Anaya et al. [START_REF] Anaya | Convergecast and broadcast by power-aware mobile agents[END_REF] studied centralized and distributed algorithms for the information exchange by energy-constrained agents, in particular the problem of transferring information from one agent to all others (Broadcast) and from all agents to one agent (Convergecast). For both problems, they provided hardness results for trees and approximation algorithms for arbitrary graphs. The budgeted delivery problem was studied by Chalopin et al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF] who presented hardness results for general graphs as well as resource-augmented algorithms. For the simpler case of lines, [START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF] proved that the problem is weakly NP-hard and presented a quasi-pseudo-polynomial time algorithm. Czyzowicz et al. [START_REF] Czyzowicz | Communication problems for mobile agents exchanging energy[END_REF] recently showed that the problems of budgeted delivery, broadcast and convergecast remain NPhard for general graphs even if the agents are allowed to exchange energy when they meet.

Our Contribution. This is the first paper to study the Returning version of BudgetedDelivery. We first show that this problem can be solved in O(n + k log k) time for lines and trees (Section 2). This is in sharp contrast to the Non-Returning version which was shown to be weakly NP-hard [START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF] even on lines. In Section 4, we prove that Returning BudgetedDelivery is NP-hard even for planar graphs. For arbitrary graphs with arbitrary values of agent budgets, we present a 2-resource-augmented algorithm and we prove that this is the best possible, as there exists no (2 -)-resource-augmented algorithm unless P = NP (Section 5). We show that this bound can be broken when the agents have the same energy budget and we present a (2 -2/k)-resource-augmented algorithm for this case.

For the Non-Returning version of the BudgetedDelivery, we close the gaps left open by previous research [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF][START_REF] Chalopin | Data delivery by energyconstrained mobile agents on a line[END_REF]. In particular we prove that this variant of the problem is also strongly NP-hard on planar graphs, while it was known to be strongly NP-hard for general graphs and weakly NP-hard on trees.

We also show tightness of the 3-resource-augmented algorithm for the problem, presented in [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF]. Finally, in Section 6, we investigate the source of hardness for BudgetedDelivery and show that the problem becomes easy when the order in which the agents pick up the package is known in advance.

Returning BudgetedDelivery on the Tree

We study the Returning BudgetedDelivery on a tree and show that it can be solved in polynomial time. We immediately observe that this problem is reducible to the Returning BudgetedDelivery on a path: There is a unique s-t path on a tree and we can move each agent from her starting position to the nearest node on this s-t path while subtracting from her budget twice the distance traveled. The path problem now has an equivalent geometric representation on the line: the source node s, the target node t, and the starting positions of the agents p i are coordinates of the real line. We assume s < t, i.e., the package needs to be delivered from left to right.

Without loss of generality, we consider schedules in which every agent i that moves uses all its budget B i . Because every agent needs to return to its starting position, an agent i can carry the package on any interval of size B i /2 that contains the starting position p i . For every agent i, let We now show that if a cover exists, greedy finds one. Observe first that a cover can be given by a subset of the agents {i 1 , . . . , i t }, t ≤ k, and by their ordering (i 1 , i 2 , . . .), according to the right endpoints of their intervals I ij , since we can reconstruct a covering by always placing the respective interval I ij at the rightmost possible position.

l i = p i -B i /
Suppose, for contradiction, that greedy fails. Let (i * 1 , i * 2 , . . .) be a minimal cover of [s, t] that agrees with the greedy schedule (i 1 , i 2 , . . .) in the maximum number of first agents i 1 , . . . , i j . Hence, j + 1 is the first position such that i * j+1 = i j+1 . The left endpoints of I * j+1 and I j+1 correspond to s r+1 in our algorithm. If agent i j+1 does not appear in the solution (i * 1 , i * 2 , . . .), adding i j+1 to that solution and deleting (if the solution is not a minimal cover) some of the subsequent ones results in a minimal cover that agrees on the first j + 1 agents, a contradiction.

If agent i j+1 appears in the solution (i * 1 , i * 2 , . . .), say, as agent i * j+δ , for some δ ≥ 2, then we modify this cover by swapping i * j+1 with i * j+δ . We claim that the new solution still covers [s, t]. To see this, let us first show that δ = 2. Recall that both the agent i j+1 = i * j+δ and the agent i * j+1 can extend the covering beyond s r+1 . By the greedy choice, it follows that r ij+1 = r i * j+δ ≤ r i * j+1 . Since every agent i covers with its interval I i half of its region [l i , r i ], it follows that in the solution (i * 1 , i * 2 , . . .) agents i * j+1 and i * j+δ together cover the region [s r+1 , r i * j+δ ] (both agents can place an interval at s r+1 , and both agents' intervals have length at least half of the length of the region [s r+1 , r i * j+δ ]). By the minimality of the solution

(i * 1 , i * 2 , . . .), it follows that i * j+δ = i * j+2 .
Obviously, the two agents do not cover more than this region (because agent i * j+δ 's righmost endpoint of its interval is r i * j+δ ). Now, since δ = 2, and because of the fact that agents i * j+1 and i * j+δ can place their intervals within the region [s r+1 , r i * j+δ ], it follows that exchanging the order of the two agents produces a solution where the region [s r+1 , r i * j+δ ] will be still covered (and perhaps even more), and the agents i * j+3 , i * j+4 , . . . can place the intervals in the very same way. See Figure 1 for illustration of the situation.

s r+1 s * r+2 s * r+3 s r+1 s r+2 s r+3 p i * j+δ p i * j+1 p i * j+δ p i * j+1 r i * j+δ l i * j+δ l i * j+1 r i * j+1 l i * j+δ l i * j+1 r i * j+1 r i * j+δ swapping i * j+1 and i * j+δ

Resource Augmentation Algorithms

We now look at general graphs G = (V, E). As we will see in the next section, BudgetedDelivery is NP-hard, hence we augment the budget of each agent by a factor γ > 1 to allow for polynomial-time solutions. For non-returning agents, a min 3, 1 + max Bi Bj -resource-augmented algorithm was given by Chalopin et. al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF]. We first provide a 2-resource-augmented algorithm for Returning BudgetedDelivery. This is tight as there is no polynomial-time (2ε)-resource-augmented algorithm, unless P = NP (Section 5). If, however, the budgets of the agents are similar, we can go below the 2-barrier: In this case, we present a 1 + k-2 k max Bi Bj -resource-augmented algorithm. Throughout this section, we assume that there is no feasible schedule with a single agent, which we can easily verify.

Preliminaries. We denote by d(u, v) the distance of two points u, v ∈ G. Assume an agent i with budget B i starts in u and moves first to v. Which locations in the graph (vertices and positions on the edges) are still reachable by i so that he has sufficient energy left to move back to u? We define the ellipsoid

E(u, v, B i ) = {p ∈ G | d(u, v) + d(v, p) + d(p, u) ≤ B i } and the ball B(u, Bi 2 ) = E(u, u, B i ). It is easy to see that E(u, v, B i ) can be (i) computed
in polynomial time by running Dijkstra's shortest path algorithm from both u and v and (ii) represented in linear space: We store all vertices p ∈ V with p ∈ E(u, v, B i ), and for each edge (p, q) ∈ E with p ∈ E(u, v, B i ), q / ∈ E(u, v, B i ) we store the furthest point of (p, q) still reachable by i.

Theorem 2 (2-resource-augmentation).

There is a polynomial-time 2-resourceaugmented algorithm for Returning BudgetedDelivery.

Proof. Denote by p i the starting position of agent i. We consider the balls

B i := B(p i , Bi
2 ) around all agents, as well as the balls B(s, 0) and B(t, 0) of radius 0 around s and t. We compute the intersection graph G I of the balls, which can be done in polynomial time. If there is a feasible schedule, then there must be a path from B(s, 0) to B(t, 0) in G I (for example the path given by the balls around the agents in the feasible schedule).

If there is no path from B(s, 0) to B(t, 0), then the algorithm outputs that there is no feasible schedule with non-augmented budgets. Otherwise we can get a 2-resource-augmentation as follows: Pick a shortest path from B(s, 0) to B(t, 0) in G I and denote by ≤ k the number of agents on this path, labeled without loss of generality 1, 2, . . . , . For each edge on the shortest path, we specify a handover point h i ∈ B i ∩ B i+1 in G (where we set h 0 = s and h = t). Then each agent i, i = 1, . . . , walks from its starting position p i to the handover point h i-1 to pick up the package, goes on to the handover point h i to drop the package there, and returns home to p i . Since

h i-1 , h i ∈ B(p i , Bi
2 ), the budget needed by agent i to do so is at most Bi

= d(p i , h i-1 ) + d(h i-1 , h i ) + d(h i , p i ) ≤ Bi 2 + 2 • Bi 2 + Bi 2 = 2 • B i . Theorem 3. There is a polynomial-time 1 + k-2
k max Bj Bi -resource-augmented algorithm for Returning BudgetedDelivery.

Proof. We first "guess" the first agent a and the last agent b of the feasible schedule (by trying all k 2 pairs). In contrast to Theorem 2, we can in this way get a 2-resource-augmented solution in which a and b only need their original budgets. Intuitively, we can evenly redistribute the remaining part of Ba and Bb among all k agents, such that for each agent i we have Bi

≤ B i + k-2 k max B j . Without
h 0 = s, h i ∈ B i ∩ B i+1
, and h = t. If the agents handover the package at the locations h i , we get a 2-resource-augmentation where the agents 1 and use only their original budget. Instead we let them help their neighbours 2 and -1 by -2 B 2 and -2 B -1 , respectively. Those agents further propagate the surplus towards the agent(s) in the middle, see Figure 2 (right). Specifically, we let the agents move as follows:

Agent 1 goes to h 0 to pick up the package and then goes on to h 1 . Then he moves towards p 2 along the shortest path from h 1 to p 2 by a -2 -fraction of d(h 1 , p 2 ), drops off the package and returns home. Since d(h 1 , p 2 ) ≤ B2

2 , the budget needed to do so is at most

d(p 1 , h 0 ) + d(h 0 , h 1 ) + 2 -2 d(h 1 , p 2 ) + d(h 1 , p 1 ) ≤ B 1 + -2 B 2 . Agents i = 2, .
. . , 2 get help from their preceding agent and thus can help the following agent: Agent i walks from its starting position p i by a 2(i-1) -fraction towards h i-1 to pick up the package and then returns home. Then i goes on to the point h i and from there on by a -2ifraction towards p i+1 to drop off the package. Finally, agent i returns home to p i . Since h i-1 , h i ∈ B i and h i ∈ B i+1 , the budget needed by agent i to do so is at most

2 2(i-1) d(p i , h i-1 ) + 2d(p i , h i ) + 2 -2i d(h i , p i+1 ) ≤ 2(i-1) B i + B i + -2i B i+1 ≤ B i + -2 max {B i , B i+1 }. Agents i = +2
2 , . . . , help in the same way their preceding agent, hence they need a budget of at most

B i + -2 max {B i-1 , B i }. If is odd there is an additional middle agent i = +1 2 who needs a budget of at most 2 -1 d(p i , h i-1 ) + 2 -1 d(p i , h i+1 ) ≤ 1 + -2 B i . Hence we achieve a resource augmentation of 1 + -2 max Bj Bi ≤ 1 + k-2 k max Bj Bi .

Hardness for Planar Graphs

In this section, we show that BudgetedDelivery in a planar graph is strongly NP-hard, both for the Returning version and the Non-Returning version. Both proofs are based on the same reduction from Planar3SAT.

Planar 3SAT. Let F be a conjunctive normal form 3CNF with a set of variables V = {v 1 , . . . , v x } and a set of clauses C = {c 1 , . . . , c y }. Each clause is a disjunction of at most three literals

(v i ) ∨ (v j ) ∨ (v k ), where (v i ) ∈ {v i , v i }. We can represent F by a graph H(F ) = (C ∪ V, A 1 ∪ A 2 )
which we build as follows: We start with a bipartite graph with the node set N consisting of all clauses and all variables and an edge set A 1 which contains an edge between each clause c and variable v if and only if v or v is con-

tained in c, A 1 = {{c i , v j } | v j ∈ c i or v j ∈ c i }.
To this graph we add a cycle A 2 consisting of edges between all pairs of consecutive variables,

A 2 = {{v j , v j+1 } | 1 ≤ j < x} ∪ {v x , v 1 } .
We call F planar if there is a plane embedding of H(F ) which at each variable node has all paths representing positive literals on one side of the cycle A 2 and all paths representing negative literals on the other side of A 2 . The decision problem Planar3SAT of finding whether a given planar 3CNF F is satisfiable or not is NP-complete, a result due to Lichtenstein [START_REF] Lichtenstein | Planar formulae and their uses[END_REF]. We assume without loss of generality that every clause contains at most one literal per variable. For an example of such an embedding, see Figure 3

(left).

Building the Delivery Graph. We first describe how to turn a plane embedding of a planar 3CNF graph H(F ) into a delivery graph G(F ), see Figure 3. Only later we will define edge weights, the agents' starting positions and their energy budgets. We will focus on Returning BudgetedDelivery; the only difference for non-returning agents lies in their budgets, we provide adapted values for non-returning agents in footnotes.

v 1 ∨ v 2 v 2 ∨ v 3 ∨ v 4 v 1 ∨ v 2 ∨ v 4 v 2 ∨ v 3 ∨ v 4 v 1 v 2 v 3 v 4
We transform the graph in four sequential steps: First we dissolve the edge {v x , v 1 } and replace it by an edge {v x , v x+1 }. Secondly, denote by deg H(F ),A1 (v) the total number of positive literal edges and negative literal edges adjacent to v. Then we can "disconnect" and "reconnect" each variable node v i (1 ≤ i ≤ n) from all of its adjacent clause nodes as follows: We delete all edges {{v i , c}} ⊆ A 1 and split {v i , v i+1 } into two paths p i,true and p i,false , on which we place a total of deg H(F ),A1 (v) internal literal nodes l i,c : If v i is contained in a clause cand thus we previously deleted {v i , c} -we place l i,c on p i,false and "reconnect" the variable by adding an edge between l i,c and the clause node c. Else if v i is contained in c we proceed similarly (putting the node l i,c on p i,true instead). As a third step, depending on the number of literals of each clause c, we may modify its node: If c contains only a single literal, we delete the c node (but we keep its literal node l i,c ). If c contains two literals (v i ), (v j ), we rename the node to c i,j . If c is a disjunction of three literals (v i ), (v j ), (v k ), we split it into two nodes c i,j (connected to l i,c , l j,c ) and c j,k (connected to l j,c , l k,c ). Finally, we place the package on the first variable node s := v 1 and set its destination to t := v x+1 .

We remark that all four steps can be implemented such that the resulting delivery graph G(F ) is still planar, as illustrated in Figure 3 (in each path tuple (p i,true , p i,false ) the order of the internal nodes follows the original circular order of adjacent edges of v i , and for each clause c = (v i ) ∨ (v j ) ∨ (v k ) the nodes c i,j and c j,k are placed close to each other).

Reduction Idea. We show that the package can't be delivered via any of the clause nodes. Thus the package has to be routed in each path pair (p i,true , p i,false ) through exactly one of the two paths. If the package is routed via the path p i,true , we interpret this as setting v i = true and hence we can read from the package trajectory a satisfiable assignment for F .

Agent Placement and Budgets. We will use Greek letters ζ, δ for weights that depend on each other or on the input. We place three kinds of agents on G:

1. Variable agents: x agents which are assigned to the variable nodes v 1 , . . . , v x . These agents will have to decide whether the package is delivered via p i,true or via p i,false , thus setting the corresponding variable to true or to false. We give all of them a budget of 2ζ.1 2. Clause agents: One agent per created clause node, e.g. a clause c containing three literals gets two agents, one in each of the two clause nodes. We think of these agents as follows: If in c = (v i ) ∨ (v j ) ∨ (v k ) the literal (v j ) is false, then clause c needs to send one of its agents down to the corresponding path node l j,c to help transporting the package over the F will be satisfiable, if and only if no clause needs to spend more agents than are actually assigned to it respectively its node(s) in G(F ). We give all clause agents a budget of 2 • (1 + ζ).2 3. Separating agents: These will be placed in-between the agents defined above, to ensure that the variable and clause agents actually need to solve the task intended for them (they should not be able to deviate and help out somewhere else -not even their own kind). The separating agents will be placed in pairs inside δ-tubes, which we define below. Edge Weights. We define edge weights on our graph G(F ) as follows: All edges between clause nodes and internal path nodes get weight 1 (in particular this means that if a clause agent walks to the path, it has a remaining range of ζ). Each path consists of alternating pieces of length ζ and of δ-tubes. We choose δ := 4ζ 3 > ζ. This means that neither variable nor clause agents can cross a δ-tube (because their budget is not sufficiently large). Furthermore the distance any separating agent can move outside of its residential tube is at most

s t Returning: B 1 =B 2 =δ NonReturning: B 1 =B 2 =2δ/3 δ 3 δ 2 v 1 v 2 v 3 v 4 ζ ζ ζ 1 1 1 1 1 1 1 1 1 1 ζ ζ ζ ζ ζ ζ ζ ζ ζ ζ δ 6 δ 6 δ 3 δ 2
δ 3 = 4ζ 9 < ζ 2 .
In particular separating agents are not able to collectively transport the package over a ζ-segment, since from both sides they are not able to reach the middle of the segment to handover the package. At last, ζ := 1 8 .

Equivalence of planar 3SAT and planar BudgetedDelivery. In the following we show that solving BudgetedDelivery on G(F ) is at least as hard as solving the underlying planar 3SAT instance. We first establish three key properties (Propositions 1-3):

Proposition 1. If a planar 3CNF F is satisfiable, then in the corresponding delivery graph G(F ), the agents can collectively deliver the package from s to t and return to their respective starting positions.

Proof. Assume that there is a satisfiable assignment for F . Then the agents' actions are straightforward: Each variable agent placed on v i moves according to the variable assignment to v i by a ζ-distance into either the true-path p i,true or the false-path p i,false . For the package to be delivered to the next variable agent, it needs to be handed across δ-tubes and ζ-segments. The former can always be done by the respective separating agents residing inside the δ-tube. It remains to be shown that the latter can be done by clause agents. To this end, consider a clause c which consists of |c| literals.

If |c| = 1 respectively c = (v j ) for some j, then there is no clause node in G(F ) at all (see the top right clause in Figure 4). No agent can reach the ζ-segment adjacent to l j,c , but this does not cause a problem, since by our assumption the literal (v j ) is satisfied and thus the variable agent at v j chose to deliver the package via the opposite path p j, (vj ) . If |c| = 2, then there is one clause agent on a single clause node c i,j which is connected to the internal path nodes l i,c and l j,c (see the top left clause in Figure 4). Both have adjacent ζ-segments which correspond to the literals (v i ), (v j ). By assumption, at least one literal -without loss of generality (v j ) -is satisfied, and since the variable agent choosing the assignment for v j thus takes the "opposite" path p j, (vj ) , the ζ-segment corresponding to (v j )

does not need to be crossed while delivering the package. If the other literal is not satisfied, then the clause agent is needed at the corresponding ζ-segment, otherwise it can stay at its place of origin.

If |c| = 3, we have three literals/ζ-segments and we have two clause nodes with one agent each (see the top center clause in Figure 4). One is connected to the first and the second ζ-segment, the other to the second and third. Collectively the two agents can reach every possible pair of segments out of the three ζ-segments. At least one literal (v j ) is satisfied. To each of the remaining ζ-segments we can therefore send one agent. Moving to the path needs 1 unit of energy (and so does returning to the clause node). Hence the agent can cover a remaining distance of ζ, which is sufficient to transport the package to the next δ-tube. Proposition 2. It is not possible to deliver a package from s to t via any clause node of the delivery graph G(F ).

Proof. For the sake of contradiction assume that the package is transported via a clause node c i,j which connects to the internal path nodes l i,c and l j,c . Except for the clause agent stationed at c i,j , no other agent can move further than ζ = 1 into each of the two edges {l i,c , c i,j } and {l j,c , c i,j }. Hence the clause agent stationed at c i,j needs to cover in each edge a distance of 2(1-ζ) (to go back and forth), hence for both edges it needs an energy of at least 2

• 2(1 -ζ) = 4 • 7 8 = 7 2 .
However, the agent has a budget of only

2(1 + ζ) = 2 • 9 8 < 7 2
, yielding a contradiction to the package being transported over the clause node. 3Proposition 3. To deliver the package over a ζ-segment adjacent to a variable node v i , we need the variable agent with starting position v i . To deliver the package over a ζ-segment adjacent to a literal node l j,c , we need a clause agent with starting position c i,j or c j,k .

Proof. Recall that δ = 4ζ 3 . Separating agents inside δ-tubes can neither singlehandedly nor collectively (starting from both sides) transport the package over a ζ-segment, since they can move outside of their residential tube by at most

δ 3 < ζ 2 .
Furthermore variable agents and clause agents can move on a trueor false-path inside an interval of size at most ζ < δ, hence they can't cross a δ-tube.

Thus to transport the package over a ζ-segment adjacent to a variable node v j , we need the variable agent placed on v j . On the other hand, transporting the package over a ζ-segment adjacent to the internal path node l j,c needs a clause agent of clause c. If c has two clause nodes c i,j , c j,k , either of the two clause agents will do.

Lemma 1 (Returning BudgetedDelivery).

A planar 3CNF F is satisfiable if and only if it is possible to deliver a package from s to t in the corresponding delivery graph G(F ), such that all agents are still able to return to their starting points in the end.

Proof. "⇒" This direction has been shown in Proposition 1. "⇐" Assume that the package can be delivered from s to t. From Proposition 2 it follows that the package has to be transported through the trueand false-paths. Without loss of generality, the package must move monotonously through the paths p i,true or p i,false . By Proposition 3 we know that for each ζ-segment that the package is delivered over, we need either the corresponding variable agent or the corresponding clause agent. It remains to show that we have enough clause agents for the task:

Each clause with |c| literals "owns" only |c| -1 clause agents and thus must have at least one satisfied literal (otherwise the |c| -1 clause agents would not be sufficient to help in all corresponding ζ-segments). Hence we can read a satisfiable variable assignment for the Planar3SAT instance directly from the choice of the variable agents (which each pick the adjacent trueor the adjacent false-path).

It is easy to see that the same arguments work for Non-Returning Budgeted-Delivery as well, hence we immediately get the same statement for the Non-Returning version.

Corollary 1 (Non-Returning BudgetedDelivery). A planar 3CNF F is satisfiable if and only if it is possible to deliver a package in the corresponding delivery graph.

Recall that a delivery graph G(F ) created from a planar 3CNF F is planar. Furthermore the size of G(F ), as well as the number of agents we use, is polynomial in the number of clauses and variables. The agents' budgets and the edge weights are polynomial in ζ, δ and thus constant. Thus Lemma 1 shows NP-hardness of BudgetedDelivery on planar graphs. Finally, note that hardness also holds for a uniform budget B: One can simply add an edge of length (B -B i )/2 to the starting location of each agent i and relocate i to the end of this edge. 4Theorem 5 (Hardness of BudgetedDelivery). Both versions of Budgeted-Delivery are strongly NP-hard on planar graphs, even for uniform budgets.

Hardness of Resource Augmentation

Main Ideas. We show that for all ε > 0, there is no polynomial-time (2ε)resource-augmented algorithm for Returning BudgetedDelivery, unless P = NP. The same holds for (3ε)-resource-augmentation for the Non-Returning version. Intuitively, an algorithm which finds out how to deliver the package with resource-augmented agents will at the same time solve 3SAT. We start by taking the reduction from Planar3SAT from Section 4. However, in addition to the previous delivery graph construction G(F ), we need to replace the δ-tubes and ζ-segments in order to take care of three potential pitfalls. We illustrate the modification into the new graph G (F ) in Figure 6: 1. In a resource-augmented setting, δ-tubes are no longer able to separate the clause and variable agents: These agents might be able to cross the δ-tube, or the separating agents residing inside the δ-tube can help out in the ζ-segments (there is no value for δ to prevent both). We will tackle this issue below by replacing δ-tubes by a chain of logarithmically many tubes with exponentially increasing and decreasing δ-values.

In the reduction for the original decision version of BudgetedDelivery,

a clause c with three literals gave rise to two clause nodes c i,j , c j,k that were adjacent to the same path node l j,c . Hence the agent on c i,j , now with resource-augmented budget, could pick up the package at l j,c and bring it close to the second resource-augmented agent stationed at c j,k .

δ-tubes 2δ-tubes This agent then might transport the package via its own clause node to the distant literal node l k,c . To avoid this, we replace every ζ-segment adjacent to such a "doubly" reachable path node l j,c by two small parallel arcs. Both arcs contain exactly one ζ-segment, reachable from only one clause node (the package can then go over either arc), as well as a chain of tubes to provide the necessary separation. 3. A single clause agent stationed at c i,j might retrieve the package from the first literal node l i,c , walk back to its origin and then on to the second literal l j,c , thus transporting the package over a clause node. This can always be done by 2-resource-augmented agents; however for (2ε)resource-augmentation we can prevent this by carefully tuning the weights of the ζ-segments, e.g. such that (2ε)

2 log L δ • δ -tubes δ-tubes 6× 6× 6× 6×
• (1 + ζ) 2. 5
We now give a more formal description of the ideas mentioned above. Recall that a δ-tube had length δ and contained two agents with budget at most δ each. If these agents are now γ-resource-augmented, γ < 3, they can move strictly less than 3δ to the right or to the left of the δ-tube. In the following we want to uncouple the length of the line segment from the range the agents have left to move on the outside of the line segment.

L-δ-Chains. We call a line segment an L-δ-chain if it satisfies the following three properties: (i) Its length is at least L (a constant). (ii) No γ-resourceaugmented agent (1 ≤ γ < 3) contained in the chain has enough energy to leave the line segment by 3δ or more. (iii) The agents contained in the chain can collectively transport a package through the line segment from left to right (already with their original budget). We can create L-δ-chains for both BudgetedDelivery versions simply by using the respective δ-tubes as a black box: We start our line segment by adding a block of six δ-tubes next to each other, followed by a block of six 2δ-tubes, a block of six 4δ-tubes and so on until we get a block of length at least 6 •

2 log L/δ • δ > L.
The same way we continue to add blocks of six tubes with lengths decreasing by powers of 2, see Figure 5. Obviously properties (i) and (iii) are satisfied. To see (ii), note that any agent contained in the first or last block of δ-tubes cannot leave its tube (and thus the L-δ-chain) by 3δ or more. On the other hand, none of the inner blocks' agents is able to even cross the preceding or the following block of six tubes, since their total length is larger than its budget.

1 1 1 ζ ζ ζ 1 1 1 ζ ζ ⇒ ζ ζ ζ ζ 1 ζ 1 1 1 ζ ζ l j,c l i j,c l k j,c
Arc Replacement of ζ-Segments. Next we decouple any pair of clause agents (stationed at nodes c i,j , c j,k ) that can directly go to the same literal node l j,c (so as not to allow them to transport the package via clause node with their augmented budgets, depicted in red in Figure 6 (left)). We replace the adjacent ζ-segment by two small arcs which represent alternative ways over which the package can be transported. Each arc consists of one L-δ-chain and of one ζ-segment, see Figure 6.

The inner arc begins with the ζ-segment -whose beginning l i j,c can be reached through an edge of length 1 by the first clause agent (stationed at c i,j ) -and ends with the L-δ-chain. The outer arc first has the L-δ-chain and then the ζ-segment. The node in between these two parts, denoted by l k j,c , is connected via an edge of length 1 to the second clause agent's starting position c j,k .

We conclude the replacement with three remarks: Firstly, it is easy to see that the described operation respects the planarity of the graph. Secondly, we are able to give values for L and δ in the next paragraph such that a single clause agent is still both necessary and (together with agents inside the newly created adjacent L-δ-chain) sufficient to transport a package over one of the parallel arcs from left to right. Finally, the clause agent starting at c i,j is no longer able to meet the clause agent starting at c j,k .

Budgets and Edge Weights. Recall that our agents have the following budgets: separating agents have a budget according to their position in the L-δ-chain, variable agents a budget of 2ζ and clause agents a budget of 2(1 + ζ). 6 Now these budgets are γ-resource-augmented, with γ < 3. We would like to prevent clause and variable agents from crossing L-δ-chains or even meeting inside of them, hence we set L := 9, which shall exceed the augmented budget of every agent by a factor of more than 2. Furthermore we don't want separating agents to help out too much outside of their residential chain, hence we set δ := ζ 9 .

A resource-augmented separating agent can thus walk only as far as 3δ = ζ 3 to the outside of the chain. In particular, separating agents cannot transport the package over a ζ-segment. At the same time, if the agents were able to deliver the package in G(F ), then they can do so in G (F ): Proposition 4. If a planar 3CNF F is satisfiable, then in the corresponding delivery graph G (F ), the agents can collectively deliver the package from s to t and return to their respective starting positions.

Proof. In Proposition 1 we have seen how the package can be transported in the original delivery graph G(F ). In the modified delivery graph G (F ), variable agents and clause agents do exactly the same as their counterparts in G(F ), and separating agents help wherever needed.

Next we choose ζ such that an augmented clause agent stationed at a clause node c i,j is not able to transport the package from l i,c to l j,c , not even in collaboration with the separating agents that can reach the two literal nodes. We set ζ := ε 6-ε . The edges {c i,j , l i,c } , {c i,j , l j,c } have length 1. In each edge, separating agents can help by at most 3δ = ζ 3 , leaving at least a distance of 1 -ζ 3 for the clause agent to cover. First note that for 0 < ε < 1, we have

ζ = ε 6-ε < ε 5 < 2ε 3 and (6 -ε) > 3(2 -ε). Hence a γ-resource-augmented clause agent has a budget of only γ • 2(1 + ζ) = 2(2 -ε)(1 + ζ) = 2(2 -ε + (2-ε)ε 6-ε ) < 2(2 -2ε 3 ) < 2(2 -ζ) < 4 • (1 -ζ 3 )
, and thus cannot transport the package via its clause node and return home in the end. 7 We get:

Proposition 5. It is not possible for (2ε)-resource-augmented agents to deliver the package from s to t via any clause node of the delivery graph G (F ). 8 Finally, we need to show that -as in Proposition 3 -a transport over a ζ-segment needs the corresponding variable or clause agent. Additionally, any feasible schedule with augmented budgets should correspond to a feasible schedule with original budgets. Proposition 6. Assume that there is a schedule in which γ-resource-augmented agents (γ < 3) collectively deliver the package from s to t in the delivery graph G (F ). Then in each ζ-segment that the package is delivered over, the schedule uses the corresponding variable agent or the corresponding clause agent. Furthermore the schedule can be transformed into a feasible schedule with the original budgets.

Proof. By Proposition 5 we know that the package cannot be transported over any of the clause nodes. Recall that γ-resource-augmented separating agents 7 For non-returning agents we use (for ε < 2) the inequalities:

ζ = ε 6-ε < ε 4 < ε 2 and (6 -ε) > 2(3 -ε). Hence a non-returning γ-resource-augmented clause agent has a budget of γ(1 + ζ) = (3 -ε)(1 + ζ) = 3 -ε + (3-ε)ε 6-ε < 3 -ε 2 < 3 -ζ = 3 • (1 -ζ 3 )
, and thus cannot transport the package via its clause node. 8 For the Non-Returning setting the proposition holds for (3-ε)-resource-augmented agents.

inside δ-tubes can neither single-handedly nor collectively (starting from both sides) transport the package over a ζ-segment, since they can move outside of their residential L-δ-chain by at most 3δ = ζ 3 . Furthermore, clause agents and variable agents are not able to meet each other anywhere in the graph, since they are pairwise separated by at least one L-δ-chain and do not have enough energy (even with the resource-augmented budgets) to reach the middle point of one of these chains.

In conclusion, we know that the package needs to be transported along the trueand false-paths and without loss of generality we assume that this happens in a strictly monotone movement. Now in each ζ-segment the package is transported across in the schedule with (2ε)-resource-augmented budget, a variable agent or a clause agent is necessary. Since these agents cannot meet each other, such an agent must pick up the package from a separating agent of the preceding L-δ-chain and hand it over to a separating agent of the following L-δ-chain. Even with a non-augmented budget, said agent would be able to pick up and hand over the package at the end and the start of these chains. Additionally, separating agents are able to transport the package from left to right across their L-δ-chain without a resource augmentation of their budgets. Together this yields a solution for delivery on G (F ) without any resourceaugmented budgets.

Lemma 2 (Resource-augmented Returning BudgetedDelivery). A planar 3CNF

F is satisfiable if and only if it is possible to deliver a package with (2ε)resource-augmented agents from s to t in the corresponding delivery graph G (F ), such that the agents are still able to reach their starting point in the end.

Proof. "⇒" This direction has been shown in Proposition 4.

"⇐" Assume that the package can be delivered from s to t. From Proposition 5 it follows that the package has to be transported through the trueand false-paths. By Proposition 6 we know that the schedule thus can be transformed into a schedule of agents with non-augmented budgets, where in each ζ-segment that the package is delivered over, the corresponding variable agent or the corresponding clause agent is used.

We show that there is a bijective mapping into a feasible schedule in the original graph G(F ), which by Lemma 1 gives us a satisfiable assignment for F . Consider the movement of the individual agents: First of all, we let every variable agent in G(F ) do the same work as its counterpart in G (F ) and vice versa. Now consider the separating agents of any δ-tube in G(F ) which corresponds to a L-δ-chain in G (G). We let these agents collectively transport the package from left to right over their δ-tube in G(F ) if and only if the agents in the corresponding chain in G (F ) transport the package over their L-δ-chain. Finally, we let corresponding clause agents in both graphs go to the same ζ-segment (both to their first segment, both to their second segment, or both to neither). Hence agents in G(F ) can just "copy" the movements of their respective counterparts in G (F ).

It is easy to see that the same arguments work for Non-Returning Budgeted-Delivery as well: In the proof, we simply replace the use of Lemma 1 by referring to Corollary 1 and replace the estimations in the proof of Proposition 5 with the corresponding estimations for non-returning (3-ε)-resource-augmented agents, given in Footnote 7.

Corollary 2 (Resource-augmented Non-Returning BudgetedDelivery). A planar 3CNF F is satisfiable if and only if it is possible to deliver a package with (3-ε)-resource-augmented agents from s to t in the corresponding delivery graph G (F ).

Compare the new delivery graph G (F ) with the original graph G(F ). The only topological changes we introduced with our replacements were the parallel arcs replacing the ζ-segments reachable by two clause nodes. We have already seen that this change respected the planarity of the delivery graph. Relevant changes to the edge weights and agent numbers, on the other hand, were added by replacing δ-tubes with L-δ-chains: Each chain consists of blocks of six δtubes of exponentially increasing size, hence we need a logarithmic number of tubes per chain, namely O log L δ many. We have fixed the values of L and

δ to L = 9 and δ = ζ 9 . With ζ -1 = 9 ε -1 ∈ Θ(ε -1 ) we get O log L δ = O(log(ζ -1 )) = O(log(ε -1
)) many agents per chain. The number of chains is clearly polynomially bounded by the number of variables and clauses and the edge weights depend on ε only as well. Hence we conclude: Theorem 6 (Inexistence of a better resource augmentation for BudgetedDelivery). There is no polynomial-time (2ε)-resource-augmented algorithm for Returning BudgetedDelivery and no (3ε)-resource-augmented algorithm for Non-Returning BudgetedDelivery, unless P = NP.

Discussion

We gave a polynomial time algorithm for the returning variant of the problem on trees, as well as a best-possible resource-augmented algorithm for general graphs. On the other hand, we have shown that BudgetedDelivery (both the returning and non-returning version) is NP-hard, even on planar graphs, or even if we allow "small" resource augmentation. Our hardness bounds on the required resource augmentation are tight and complement the previously known algorithm [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF] for the non-returning case.

Our results show that the returning version of BudgetedDelivery becomes hard when transitioning from trees to planar graphs. Naturally, it is interesting to investigate, from the graph topology point of view, when exactly the transition from easy to hard happens. At the same time, it is not only the topology that makes the problem hard. In the following we have a light look at various aspects that make the problem easy or hard. Intermediate graph classes. We have seen that the Returning BudgetedDelivery is solvable in polynomial time on trees. Here, we extend this positive result to graphs, which correspond to the union of internally vertex-disjoint s-tpaths. Observe that a special case of such a graph is a ring (also called a cycle), which is one of the simplest connected planar graphs that is not a tree. Theorem 7. There is an O(n + k log k)-time algorithm for Returning Bud-getedDelivery on graphs consisting of internally vertex-disjoint s-t-paths.

Proof. Denote by P 1 , . . . , P l the internally vertex-disjoint s-t-paths of the input graph G. Observe that if there is a solution to the given instance, then the packet travels from s to t along exactly one of the l paths. Let us call such a path a delivery path. Hence, we can try each of the l paths, and check whether the agents can deliver the packet along the path. This problem is quite similar to BudgetedDelivery on the line, with the exception that now the agents that are not on the path (along which the delivery happens) can enter the path from two vertices -from s and from t. Observe that when searching for a solution, we can assume that there is always at most one agent that is not on the delivery path and that enters the path via s. If there were two or more such agents, then we could simply keep, among all such agents, only the agent that reaches the farthest vertex from s along the path. By similar arguments, we can assume that at most one agent enters the delivery path via t. We can thus enumerate all possible agents that can help to deliver the package along the delivery path. In detail, this can be done as follows.

As in the case of trees, we can find the distances from all agents' starting positions to s and t in time O(n) using breadth-first search from both s and t. Hence, for each agent we know whether it can reach s and whether it can reach t, and we also know how much budget the agent has left, once it reaches, respectively, s and t. For any path P i , we denote by k i the number of agents with starting position p j on P i and keep track of the two agents a s,i,1 , a s,i,2 with the two highest remaining budgets after moving to s, i.e. we take a s,i,1 := arg max j {B jd(s, p j ) | p j ∈ P i and d(s, p j ) ≤ B j } and similarly a s,i,2 := arg max j {B jd(s, p j ) | p j ∈ P i and d(s, p j ) ≤ B j and j = a s,i,1 }. In the same way, we store the two agents a t,i,1 , a t,i,2 with the highest remaining budget after moving to t. Note that the two latter are not necessarily disjoint from the former, and these agents may not exist at all (if this is the case, we simply discard them from the following discussion). Finally, among all agents a s,i,1 , a s,i,2 , i = 1, . . . , l we keep the set of the four agents with the highest remaining budget after they reach s, which we denote by A s . We do the same at t to get A t , the set of agents with the highest remaining budget at t.

Assume that we are interested in whether the package can be delivered from s to t along the path P i : Applying the result for trees and lines (Theorem 1), it is clear how to solve the decision problem for P i -by only using agents with starting position on P i -in time O(k i log k i ). However, the package might get advanced from s towards t on P i by some external agent j originating from another path (i.e. an agent with p j / ∈ P i ); the package might also be picked up by such an external agent and taken to t. Without loss of generality, this will not yet marked vertex. If so, we mark this vertex (and the number of marked vertices stays at most n). Next we check whether a i can bring the package into an edge e = {u, v} for which (without loss of generality) u is marked and v is not. Check whether the point inside the edge which is furthest from u -and still can be reached by a i -has larger distance to u than a previously marked point. If so, delete the old point (if any) and mark the new point and store its distance from u. The number of marked edges stays at most m.

If at some point we mark the vertex t, we are done. Since each agent i has at most n + m pick-up locations to consider, we can compute all new marks by computing the ellipsoid E(p i , l, B i ) for every old mark l, which we can do by running Dijkstra's shortest path algorithm once from p i and once from each old mark. Hence we require time O((n + m) • (n log n + m)) per agent.

Corollary 3. For a constant number of agents k, BudgetedDelivery is solvable in time O(poly(n, m)) by brute forcing the order of the agents.

Future work.

An interesting open problem is to understand collaborative delivery of multiple packages at once. For example, the complexity of the problem on paths remains open. In this setting, it may be reasonable to constrain the number of agents, the number of packages, or the ability of transporting multiple packages at once, in order to allow for efficient algorithms. Also, in general graphs, the problem may not become easy if the order in which agents move is fixed.

Figure 1 :

 1 Figure 1: Changing the order of agents i * j+1 and i * j+δ in the schedule.

  loss of generality, we assume that agent a walks from its starting position on a shortest path to s to pick up the package, and that agent b walks home directly after dropping the package at t. Hence consider the ellipsoids B a := E(p a , s, B a ) and B b := E(p b , t, B b ) as well as the balls B i := B(p i , Bi2 ) around the starting positions of all other agents and compute their intersection graph G I .We denote by i = 1, . . . , the agents on a shortest path from B a to B b in G I (if any), where a = 1, b = ≤ k and specify the following points:

s = h 0 t = h 7 Figure 2 :

 72 Figure 2: (left) Feasible schedule.(right) Schedule with 1 + 5 7 maxB j B i-resourceaugmentation.

Figure 3 :

 3 Figure 3: (left) A plane embedding of a 3CNF F which is satisfied by (v 1 , v 2 , v 3 , v 4 ) = (true, false, false, true). (right) Its transformation to the corresponding delivery graph.

Figure 4 :

 4 Figure 4: (left) Two examples of δ-tubes for both versions of BudgetedDelivery. (right) Agent placement and edge weights on G(F ); agents are depicted by squares

Remark 4 .

 4 Strictly speaking, a reduction without variable agents works as well. In terms of clarity, we like to think of variable agents as the ones setting the variables to true or false. δ-Tubes. We call a line segment a δ-tube if it satisfies the following four properties: (i) It has a length of δ. (ii) It contains exactly two agents which both have budget at most δ. (iii) Neither agent has enough energy to leave the line segment on the left or on the right by more than a distance of δ 3 . (iv) The agents can collectively transport a package through the line segment from left to right. δ-tubes exist for both BudgetedDelivery versions, examples are given in Figure 4 (left). The reader may think of these examples, whenever we talk about δ-tubes.

Figure 5 :

 5 Figure 5: L-δ-chains consist of blocks of 6 tubes of exponentially increasing and decreasing size.

Figure 6 :

 6 Figure 6: (top-to-bottom) We replace δ-tubes in G(F ) by L-δ-chains in G (F ). (left-to-right) We replace each ζ-segment connected to two clause agents by two parallel arcs.

  2 denote the leftmost point where she can pick up a package, and let r i = p i + B i /2 be the rightmost point to where she can deliver the package. The Returning BudgetedDelivery on a line now becomes the following covering problem: Can we choose, for every i, an interval I i of size B i /2 that lies completely within the region [l i , r i ] such that the segment [s, t] is covered by the chosen intervals, i.e., such that [s, t] ⊆ i I i ?The following greedy algorithm solves the covering problem. The algorithm works iteratively in rounds r = 1, 2, . . .. We initially set s 1 = s. We stop the algorithm whenever s r ≥ t, and return true. In round r, we pick i * having the smallest r i * among all not yet used agents i with l i ≤ s r < r i , and set s r+1 = min{r i * , s r + B i * /2} and I i * = (s r+1 -B i * /2, s r+1 ), and continue with the next round r + 1. If we cannot choose i * , we stop the algorithm and return . Whenever it decides upon I i , it will set s r to the respective endpoint of I i , and never ever consider i again or change the placement of I i within the boundaries [l i , r i ]. Thus, whenever s r ≥ t, the intervals I i form a cover of [s, t].

	Theorem 1. There is an O(n + k log k)-time algorithm for Returning Bud-getedDelivery on a tree.
	Proof. The reduction from a tree to a path takes O(n) time using breadth-first search from s and the algorithm greedy can be implemented in time O(k log k) using a priority queue. For the correctness, we now show that greedy returns a
	solution to the covering problem if and only if there exists one.
	Greedy can be seen as advancing the cover of [s, t] from left to right by
	adding intervals I
	false.

i

In the Non-Returning version we want agents to have the same "range", hence we set their budget to ζ.

In the Non-Returning version we assign a budget of (1 + ζ) to clause agents.

Non-returning agents need to cover only one of the edges twice (to go back and forth), hence they need an energy of at least 3(1 -ζ) =[START_REF] Czyzowicz | On minimizing the maximum sensor movement for barrier coverage of a line segment[END_REF] 8 versus a budget of 1 + ζ = 9 8 , yielding a contradiction as well.

We relocate a non-returning agent by adding an edge of length (B -B i ).

Non-returning clause agents can do this if they are 3-resource-augmented; and we can prevent it for (3 -ε)-resource-augmentation by setting ζ such that (3 -ε) • (1 + ζ)3 (in fact the value of ζ will be the same as for Returning BudgetedDelivery, but we will use different bounds in the proof).

In the Non-Returning version, variable agents have a budget of ζ and clause agents a budget of 1 + ζ.

$ This work was partially supported by the ANR project ANCOR (anr-14-CE36-0002-01), and by the SNF (project 200021L_156620).

be done -if at all -by the external agent a s,j,1 , j = i which has the highest remaining budget at s, or if this agent is also the agent which has the highest remaining budget at t, by the external agent a s,j,2 , j = i with the second highest remaining budget (and the same observation holds for t).

Clearly, these candidates are from the sets A s and A t , and testing all pairwise combinations yields a running time of

Hence we can simply go over all paths

and check whether the package can be delivered along P i . This positive result raises the question of whether BudgetedDelivery is polynomial-time solvable for other subclasses of planar graphs such as seriesparallel graphs or outerplanar graphs. So far, this remains an intriguing open problem.

Fixed agent order. Chalopin et al. [START_REF] Chalopin | Data delivery by energy-constrained mobile agents[END_REF] gave a polynomial algorithm for the Non-Returning version under the assumptions that (i) the order in which the agents move is fixed and (ii) the package can only be handed over at vertices. Using a dynamic program, we are able to drop assumption (ii), allowing handovers within edges. Our result holds for both versions of BudgetedDelivery.

if the agents are restricted to a fixed order in which they move.

Proof. If there is a feasible schedule, we can compute it in a breadth-first searchlike fashion where we proceed agent by agent and update reachable regions of the graph on-the-fly: Each agent can either not help in the schedule or it can transport the package from a pickup location to a drop-off location. We show that we can restrict drop-offs to meaningful places such that for each agent the set of all possible pickup locations is bounded by n + m. This limitation to only one of the potentially infinitely many handover points inside each edge allows us to use dynamic programming and to proceed by induction:

Denote the agents in the schedule order by a 1 , . . . , a . The first agent a 1 can pick up the package at s only, hence there is only one possible pick-up location.

If a 1 wants to drop off the package at a vertex, there are at most n choices of where to do so. We mark all the vertices which a 1 can reach from s while still being able to return home. Now assume a 1 wants to drop off the package inside an edge e = {u, v}. This means that e can be reached by a 1 , hence without loss of generality the vertex u is marked. If v is marked as well, then a 1 should not drop the package inside e, since the package has to be picked up later, which could just as well be done at either u or v. Otherwise a 1 should bring the package as far as possible into the edge (since if a later agent a i wants to pick up the package, it can pick it up at u or come in via v). We mark this point inside the edge and store its distance from u. We now restrict ourselves to these at most n + m described drop-off locations. An agent a i , i > 1 can pick up the package at s or at any previous drop-off location. By induction there are at most n + m many such locations. Now we first check whether a i can pick up the package somewhere and deliver it to any