Mobility Matters
Home›Mobile agents on graphs›Exploration›Delivery by energy-constrained agents

Delivery by energy-constrained agents

Agents with energy budgets, placed in a weighted graph, must carry a message from a source node to a target node, handing it over when they meet: when can a planner find a schedule quickly, and by how much must the budgets grow?

Problem statement and measurescollapse
stbudget left: a 6, b 6, c 6budget left: a 5, b 6, c 6budget left: a 4, b 6, c 6budget left: a 3, b 6, c 6budget left: a 2, b 6, c 6budget left: a 1, b 6, c 6budget left: a 0, b 6, c 6budget left: a 0, b 5, c 6budget left: a 0, b 4, c 6budget left: a 0, b 3, c 6budget left: a 0, b 2, c 6budget left: a 0, b 1, c 6budget left: a 0, b 1, c 5budget left: a 0, b 1, c 4aabbccStart: equal budgets B = 6; the message (square) lies at sa, the leftmost agent, walks back to the message and picks it upa has used its budget: it drops the messageb walks back to the message and carries it to the rightb reaches c's node: c takes over with its whole budgetFinal: c brings the message to t; a schedule exists
Delivery on a path with equal budgets, by the greedy schedule of Anaya et al. 2016: the edges have weight 1, every agent has budget \(B = 6\), and the message must go from \(s\) to \(t\). The agents are used from left to right. Each one walks to the message, picks it up and carries it to the right until its budget is used up, unless it reaches the start node of the next agent first, which then takes over with its whole budget. If any schedule exists, this one does (Lemma 1), so the planner decides the task in linear time. One frame per edge crossed; the numbers at the bottom are the budgets left.

\(k\) agents start at nodes of a connected undirected graph \(G\) with \(n\) nodes and \(m\) edges; every edge \(e\) has a positive weight \(\mathrm{wt}(e)\), its length. Agent \(i\) has a budget \(B_i\): it can travel a total distance of at most \(B_i\), also along parts of edges. A message lies at a source node \(v_s\) and must reach a target node \(v_t\). An agent can pick the message up where it is, carry it, and drop it anywhere (at a node or inside an edge), where another agent can pick it up; agents need not return to their start nodes. A planner that knows \(G\), the start nodes and the budgets computes a schedule: which agents move, and where each one picks up and drops the message. The task is to decide whether a schedule exists and to find one. Time is the running time of the planner. The budget factor \(\gamma\) is that of a planner that runs in polynomial time and either correctly reports that no schedule exists or finds one in which every agent may travel \(\gamma B_i\) (resource augmentation); with equal budgets \(B_i = B\), it is the ratio between the budget the planner uses and the smallest budget that admits a schedule.

Measures: Time, running time of the planner; Budget factor, factor by which a polynomial-time planner enlarges the budgets (resource augmentation), or its approximation ratio for the smallest equal budget.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture couriers spread over a town, each able to walk only a limited total distance, who must carry a letter from one place to another, handing it over when two of them meet. The town is a graph: places are nodes, roads are edges, and each edge has a weight, its length. The couriers are agents, and agent \(i\) has a budget \(B_i\), the total distance it may travel. The letter is the message. It lies at the source node \(v_s\) and must reach the target node \(v_t\). An agent can pick the message up where it stands, carry it, and drop it anywhere, even partway along an edge, where another agent can pick it up. Agents need not go back to where they started. A planner, a program that knows the graph, the start nodes and the budgets, must decide whether a schedule exists and find one. A schedule says which agents move and where each one picks up and drops the message. We measure the planner's running time. For a fast planner that is allowed to enlarge the budgets, we also measure the budget factor: how much it must enlarge them. In the standard version the graph is arbitrary and every agent has its own budget.

1AlgorithmOn a path with equal budgets, push the message as far as possible Paths, equal budgets → Anaya et al. 2016

Let the graph be a path, its nodes in a row, with \(v_s\) to the left of \(v_t\), and let all budgets be equal.

  1. Take the agents in the order of their start nodes, from left to right.
  2. The current agent walks to the message, picks it up and carries it to the right until its budget is used up, then drops it.
  3. If it reaches the start node of the next agent on the way, it hands the message over there instead. The next agent still has its whole budget, so it can carry the message at least as far.
  4. A schedule exists exactly when the message reaches \(v_t\).
Why it works and what it costs. Each agent is used once, so once the agents are sorted the planner needs \(O(k)\) steps for \(k\) agents Anaya et al. 2016. The greedy schedule is enough because of an exchange argument (Lemma 1): if some schedule exists, then one exists in which the agents carry the message in order of position, each pushing it as far as possible. Equal budgets matter. When budgets differ, the planner must choose which agents to use, and delivery is NP-hard already on a path Chalopin et al. 2014. That hardness is weak: it needs budgets that are large numbers.

Why it matters. It is the building block on which Anaya et al. 2016 base convergecast and broadcast, and the easy case against which the hard ones are measured.

2AlgorithmTriple the budgets: a chain of reaches Arbitrary graphs → Chalopin et al. 2013

Call the reach of agent \(i\) the set of all points within distance \(B_i\) of its start node.

  1. Every hand-over point lies in the reach of both agents involved, \(v_s\) in the reach of the first agent and \(v_t\) in the reach of the last. So if no chain of agents, each reach meeting the next one, joins \(v_s\) to \(v_t\), no schedule exists, and the planner says so.
  2. Otherwise the planner takes such a chain and picks a meeting point in each pair of consecutive reaches.
  3. Each agent of the chain walks to the previous meeting point (or to \(v_s\)), picks up the message, walks back to its start node, and then walks to the next meeting point (or to \(v_t\)).
Why it works and what it costs. Each of the three walks stays inside the agent's reach, so agent \(i\) travels at most \(3B_i\). Finding a chain is a search in a graph whose nodes are the agents, so it takes polynomial time. Whenever the original budgets allow a schedule, the planner succeeds with budgets three times larger Chalopin et al. 2013. Unless P = NP, no polynomial-time planner can make do with any smaller factor Bärtschi et al. 2020. When all budgets are equal, doubling them is enough.

Why it matters. It locates the difficulty: deciding whether agents can reach each other is easy, and only the exact use of every budget is hard.

3Lower boundHard choice: who carries which stretch Arbitrary graphs → Chalopin et al. 2013

Start from a puzzle known to be hard, 3-partition: split \(3z\) given numbers into \(z\) groups of three with the same sum. Build a graph from it.

  1. A path from \(v_s\) to \(v_t\) is made of \(z\) stretches whose length is that sum, separated by single edges. On each separating edge sits an extra agent with budget 1, which can carry the message across it.
  2. For each number \(a\) there is one agent. It spends a fixed amount to reach any node of the path, and its budget then lets it carry the message at most \(a\) edges further.
  3. The path is so long that every agent must spend its whole budget on it. So the agents that carry the message across each stretch have numbers adding up to its length, and a schedule exists exactly when the numbers can be split.
Why it holds. A fast planner for delivery would therefore solve 3-partition, which is impossible unless P = NP Chalopin et al. 2013. The numbers in 3-partition can be kept small, so delivery stays hard when every edge has weight 1 (it is strongly NP-hard). Equal budgets do not help either: each agent first walks a private path whose length makes up the difference. The hard part is choosing the order of the agents. Once the order is fixed, a planner finds a schedule in polynomial time Bärtschi et al. 2020.

Why it matters. It is the reason this problem is studied through budget factors and special graphs rather than exact fast planners.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Budget factor
Arbitrary graphs standard
Deciding whether a schedule exists is strongly NP-hard; tripling the budgets makes it polynomial, and no smaller factor does unless P = NP.
unknown \(\text{poly}(n, m)\) vs \(\text{NP-hard}\) combinatorial hardness
tight \(\min\{3,\ 1+\max_{i,j} B_i/B_j\}\) vs \(3\) combinatorial hardness
Paths
On a path, delivery with different budgets is weakly NP-complete; a quasi-pseudo-polynomial algorithm decides it.
polynomial gap \(O\big(\mathrm{dist}(v_s,v_t)^2\, k^{1+4\log \mathrm{dist}(v_s,v_t)}\big)\) vs \(\text{weakly NP-hard}\) combinatorial hardness
unknown — vs —
Paths, equal budgets
With equal budgets, a greedy schedule in which each agent pushes the message as far as it can decides delivery on a path in linear time.
tight \(O(k)\) vs —
tight — vs —
Arbitrary graphs, equal budgets
With equal budgets, deciding whether a schedule exists stays strongly NP-hard; the smallest budget that admits a schedule can be approximated within a factor 2, and no lower bound on the factor is known.
unknown — vs \(\text{NP-hard}\) combinatorial hardness
unknown \(2\) vs —
Planar graphs, equal budgets
Delivery stays strongly NP-hard on planar graphs, even when all budgets are equal.
unknown — vs \(\text{NP-hard}\) combinatorial hardness
unknown — vs —

Open questions 6

Arbitrary graphs

  1. What is the complexity of delivering several messages at once, for instance on paths? Raised in Bärtschi et al. 2020.

Paths

  1. Is there a pseudo-polynomial algorithm for delivery on a path? Posed in Chalopin et al. 2014.
  2. Find good resource-augmented planners for delivery on a path. Posed in Chalopin et al. 2014.

Paths, equal budgets

  1. Is delivery with equal budgets between two nodes of a tree NP-hard or polynomial? Posed in Anaya et al. 2016 and again in Chalopin et al. 2013; Chalopin et al. 2021 states that on trees delivery is known to be weakly NP-hard, without a reference, in a paper about equal budgets.

Arbitrary graphs, equal budgets

  1. Is there a constant \(c > 1\) such that the smallest equal budget cannot be approximated within \(c\) in polynomial time unless P = NP? Chalopin et al. 2021 notes that no lower bound is known.

Planar graphs, equal budgets

  1. Is there an inapproximability bound for the smallest equal budget, already on planar graphs? No lower bound above 1 is known for any graph class Chalopin et al. 2021.

What the community started looking at

Anaya, Chalopin, Czyzowicz, Labourel, Pelc and Vaxès studied agents with equal budgets that gather information (convergecast) or spread it (broadcast) by meeting, and, as a building block, carrying information between two points of a path Anaya et al. 2016. Chalopin, Das, Mihalák, Penna and Widmayer posed delivery from a source to a target with individual budgets on arbitrary graphs, showed it strongly NP-hard even with equal budgets, gave resource-augmented planners and a 2-approximation of the smallest equal budget, and introduced delivery along a fixed path Chalopin et al. 2013; Chalopin, Jacob, Mihalák and Widmayer showed it weakly NP-hard already on a path Chalopin et al. 2014. Bärtschi et al. showed it strongly NP-hard on planar graphs, made the factor 3 tight, and introduced returning delivery Bärtschi et al. 2020. Later work fixed the path of the message Chalopin et al. 2021, let the agents exchange energy Czyzowicz et al. 2016, and minimised the total energy of agents with different consumption rates Bärtschi et al. 2017.

Related problems

Collaborative exploration: Energy-constrained agents also explore graphs together: with budgets in unknown trees Bampas et al. 2018, and with energy sharing in known graphs Czyzowicz et al. 2021c; both are listed there as further reading.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Bärtschi et al. 2017 Energy-Efficient Delivery by Heterogeneous Mobile Agents. Minimises the total energy of agents that spend energy at different rates, without budgets, for several messages: one message in \(O(|V|^3)\) time, collaboration helps by at most a factor 2, and a \(4\max_{i,j} w_i/w_j\)-approximation with unit capacities (their \(w_i\) are rates). Model and contributions read (arXiv v1).
  • Czyzowicz et al. 2016 Communication Problems for Mobile Agents Exchanging Energy. Agents that may hand over energy when they meet: delivery, convergecast and broadcast take linear time on paths and polynomial time on trees, and stay NP-complete on arbitrary graphs. Theorem statements read (arXiv v1); summarised in the notes of the general setting.
  • Czyzowicz et al. 2019b Energy-optimal broadcast and exploration in a tree using mobile agents. Broadcast without budgets: \(k\) agents at the root of an edge-weighted tree, one node holds a message that must reach every node, agents carry it on and need not return, and the total distance travelled is minimised. A greedy choice of the leaves where agents end computes the optimum in \(O(n\log n)\) time for any \(k\) (Theorem 1), and in \(O(n)\) time when \(k\) is at least the number of leaves (Theorem 2); the same applies to exploration. Read (model and theorems).
  • Czyzowicz et al. 2021b Gossiping by energy-constrained mobile agents in tree networks. Gossiping with energy exchange: every node of an edge-weighted tree holds a packet, \(k\) agents placed anywhere with individual budgets carry copies of all packets they have seen and may hand over energy when they meet; can every packet reach every node? Some optimal strategy is a convergecast to one node followed by a broadcast (Theorem 7), and an \(O(k^2n^2)\)-time algorithm finds a cheapest strategy whenever one exists (Theorem 8). Read (model and theorems).

All settings

The assumption tree (5 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Budget factor); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Graph class › Budgets.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Graph class

0any connected graph1planar graphs2paths

Chalopin, Das, Mihalák, Penna and Widmayer posed delivery on arbitrary graphs and left it open on paths with different budgets and on trees Chalopin et al. 2013. Anaya et al. carried information along a path with equal budgets and asked whether the task is hard on trees Anaya et al. 2016; Chalopin, Jacob, Mihalák and Widmayer found it hard on a path once budgets differ Chalopin et al. 2014, and Bärtschi et al. showed hardness on planar graphs Bärtschi et al. 2020.

Formal definitions
0any graph
\(G\) is any connected undirected graph with positive edge weights.
1planar
\(G\) is planar.
2path
\(G\) is a path, equivalently a segment of the line with the agents, \(v_s\) and \(v_t\) on it.

Budgets

0budgets may differ1equal budgets

Anaya et al. give all agents the same power Anaya et al. 2016; Chalopin et al. allow different budgets Chalopin et al. 2013, which alone makes delivery on a path NP-hard Chalopin et al. 2014. Chalopin, Das, Disser, Labourel and Mihalák call agents with equal budgets homogeneous Chalopin et al. 2021.

Formal definitions
0any budgets
Each agent \(i\) has its own budget \(B_i\).
1equal budgets
All agents have the same budget \(B\).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.