Consider a team of mobile robots that must service a set of spatially distributed tasks (inspection points, pick-ups, or manipulation events). A task allocation mechanism decides which robot executes which task (and in which order) so as to optimize some global objective such as total completion time, traveled distance, or energy expenditure.

Let the robot set be \( R = \{1,\dots,n\} \) and the task set be \( T = \{1,\dots,m\} \). A typical global objective is to minimize the team cost:

\[ J(x) = \sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij}, \]

where \( c_{ij} \) encodes the cost for robot \( i \) to execute task \( j \) (e.g., planned path length in configuration space) and \( x_{ij} \in \{0,1\} \) indicates whether robot \( i \) is assigned to task \( j \).

In centralized schemes, a global planner knows all \( c_{ij} \) and solves a combinatorial optimization problem (e.g., assignment or vehicle routing). In contrast, in distributed market-based methods, robots act as self-interested agents:

• each robot computes \( c_{ij} \) locally for nearby tasks,
• tasks are viewed as “goods” with prices,
• robots compute bids based on their private valuations,
• prices adjust until supply and demand balance, yielding an allocation.

The core idea is that prices encode global coupling constraints (e.g., “only one robot may win a task”) so that purely local optimization at each robot can still approximate or attain globally optimal coordination.

flowchart TD
  T["Task set T and robot set R"] --> C["Each robot: estimate local cost to tasks"]
  C --> B["Robots compute bids from utility - price"]
  B --> X["Exchange bids and current prices over network"]
  X --> W["Determine winning robot for each task"]
  W --> U["Update assignments and task prices"]
  U --> D{"Unassigned or contested \ntasks remain?"}
  D -->|yes| C
  D -->|no| E["Robots execute their allocated tasks in parallel"]
        

We first study the single-robot-per-task, single-task-per-robot case with \( n = m \). The decision variables are \( x_{ij} \in \{0,1\} \), where \( x_{ij} = 1 \) means robot \( i \) executes task \( j \). The linear assignment problem is

\[ \begin{aligned} \min_{x_{ij}} \quad & \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j=1}^n x_{ij} = 1, \quad i = 1,\dots,n, \\ & \sum_{i=1}^n x_{ij} = 1, \quad j = 1,\dots,n, \\ & x_{ij} \in \{0,1\}. \end{aligned} \]

The constraints enforce that every robot is assigned one task and every task is served by exactly one robot. The cost \( c_{ij} \) is typically computed from motion-planning or kinematic models, e.g.

\[ c_{ij} = \ell\bigl(\gamma_{ij}\bigr), \]

where \( \gamma_{ij} \) is a collision-free path in configuration space from robot \( i \)'s current configuration to the configuration required by task \( j \), and \( \ell(\cdot) \) is its path length or dynamic cost functional.

2.1 LP relaxation and total unimodularity

If we relax the integrality constraint to allow \( 0 \le x_{ij} \le 1 \), we obtain a linear program (LP). The constraint matrix for the assignment problem is totally unimodular, so every vertex of the feasible polytope has integer coordinates. Therefore:

Theorem (Birkhoff–von Neumann). The set of doubly-stochastic matrices

\[ \mathcal{B}_n = \left\{ X \in \mathbb{R}^{n \times n} \;\middle|\; X \mathbf{1} = \mathbf{1},\; X^\top \mathbf{1} = \mathbf{1},\; X_{ij} \ge 0 \right\} \]

is the convex hull of permutation matrices. In particular, there exists an optimal solution of the relaxed LP that is a permutation matrix, hence integral.

This result explains why centralized algorithms such as the Hungarian method can solve the assignment problem in polynomial time. Distributed auction algorithms construct such solutions iteratively by adjusting prices rather than solving the LP directly.

2.2 Capacity-constrained robots

For robots capable of executing up to \( q_i \) tasks each, we obtain a more general multi-assignment formulation:

\[ \begin{aligned} \min_{x_{ij}} \quad & \sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{i=1}^n x_{ij} \le 1, \quad j = 1,\dots,m, \\ & \sum_{j=1}^m x_{ij} \le q_i, \quad i = 1,\dots,n, \\ & x_{ij} \in \{0,1\}. \end{aligned} \]

Market-based methods extend naturally by interpreting each robot’s capacity as a cardinality constraint on the bundle of tasks that it may win.

To connect auctions with optimization, we switch to a maximization viewpoint with nonnegative valuations \( v_{ij} \). Let

\[ v_{ij} = -c_{ij}, \]

so that maximizing team valuation is equivalent to minimizing total cost. The primal problem is

\[ \begin{aligned} \max_{x_{ij}} \quad & \sum_{i=1}^n \sum_{j=1}^n v_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j=1}^n x_{ij} = 1,\quad i = 1,\dots,n, \\ & \sum_{i=1}^n x_{ij} = 1,\quad j = 1,\dots,n, \\ & x_{ij} \ge 0. \end{aligned} \]

The dual variables associated with these constraints are interpreted as prices or potentials. Introduce dual variables \( \alpha_i \) for robot constraints and \( \beta_j \) for task constraints. The dual problem is

\[ \begin{aligned} \min_{\alpha,\beta} \quad & \sum_{i=1}^n \alpha_i + \sum_{j=1}^n \beta_j \\ \text{s.t.} \quad & \alpha_i + \beta_j \ge v_{ij}, \quad \forall i,j. \end{aligned} \]

Intuitively, \( \alpha_i \) is the “utility level” of robot \( i \), and \( \beta_j \) is the “price” for task \( j \). For any feasible allocation \( x \) and prices \( (\alpha,\beta) \) we have

\[ \sum_{i,j} v_{ij} x_{ij} \le \sum_{i,j} (\alpha_i + \beta_j) x_{ij} = \sum_i \alpha_i + \sum_j \beta_j, \]

giving the usual primal–dual inequality (team valuation is upper bounded by the total dual price).

Complementary slackness for optimal solutions states that if \( x_{ij} > 0 \), then

\[ \alpha_i + \beta_j = v_{ij}. \]

Market-based algorithms approximate these conditions by iteratively adjusting the task prices \( \beta_j \) (or equivalently \( p_j = \beta_j \)) until robots are nearly indifferent between their assigned task and all alternatives.

The classical auction algorithm for assignment is a primal–dual method driven by bids on tasks. Each robot maintains its own valuation vector \( v_{ij} \) and a local copy of the price vector \( p_j \). At any iteration, each robot \( i \) chooses its most preferred task relative to prices:

\[ j_1(i) = \arg\max_{j} \bigl( v_{ij} - p_j \bigr), \quad j_2(i) = \arg\max_{j \ne j_1(i)} \bigl( v_{ij} - p_j \bigr), \]

where \( j_1(i) \) is the best task and \( j_2(i) \) is the second best at current prices. The robot then computes a bid:

\[ b_i = p_{j_1(i)} + \bigl( v_{i j_1(i)} - v_{i j_2(i)} \bigr) + \varepsilon, \]

for some small \( \varepsilon > 0 \). The price and assignment for task \( j_1(i) \) are updated to reflect the highest received bid:

\[ p_{j_1(i)} \leftarrow b_i, \quad x_{i j_1(i)} \leftarrow 1,\quad x_{k j_1(i)} \leftarrow 0 \text{ for } k \ne i. \]

Robots that lose tasks become unassigned again and bid in subsequent iterations. Prices thus increase on over-demanded tasks until only one robot can profitably win each task.

4.1 Distributed realization

In a centralized auction, a single auctioneer collects all bids and broadcasts the updated prices. In a distributed auction:

• each robot maintains and broadcasts its local view of the winning robot and price for each task,
• neighboring robots exchange these views over a communication graph,
• conflicts (two robots claiming the same task) are resolved using deterministic tie-breaking (e.g. highest bid or lowest robot index).

Under mild connectivity assumptions (e.g. the communication graph is repeatedly jointly strongly connected), distributed auction algorithms converge to the same assignment as their centralized counterpart.

flowchart TD
  A["Robot i local state: prices p_j, winners w_j"] --> S["Select best task j1 maximizing v_ij - p_j"]
  S --> B["Compute bid for j1 \nusing gap to second-best"]
  B --> M["Broadcast bid and candidate winner \nfor task j1 to neighbors"]
  M --> R["Receive neighbors' bids and \nresolve conflicts (keep highest bid)"]
  R --> U["Update local prices p_j \nand winners w_j"]
  U --> C{"Robot i still unassigned \nand tasks available?"}
  C -->|yes| S
  C -->|no| Q["Stop: local assignment converged"]
        

Many robotic missions require each robot to execute a sequence of tasks. Let a task bundle for robot \( i \) be a finite subset \( S \subseteq T \). The value of assigning bundle \( S \) to robot \( i \) is \( f_i(S) \), which may encode routing cost, battery limits, and dynamic feasibility. Typically:

• monotonicity: \( f_i(S) \le f_i(S \cup \{t\}) \) for any task \( t \) (nonnegative benefit),
• diminishing returns (submodularity): for \( A \subseteq B \subseteq T \) and \( t \in T \setminus B \),

\[ f_i(A \cup \{t\}) - f_i(A) \ge f_i(B \cup \{t\}) - f_i(B). \]

Submodular bundle valuations arise when adding an extra task to a large tour has smaller marginal cost than adding it to a small tour, which is typical for path-planning costs.

In bundle auctions, robots iteratively construct bundles of tasks (e.g. by greedy insertion of the task with largest marginal gain per step) and bid on entire bundles. Consensus-based bundle algorithms alternate:

1. Bundle construction: each robot greedily builds its task bundle to respect capacity and timing constraints.
2. Conflict resolution: robots exchange their bundles and associated scores, then remove tasks they lost to neighbors with better bids.

For monotone submodular \( f_i \) and cardinality-constrained bundles, simple greedy construction yields near-optimal solutions. For example, if at most \( k \) tasks may be assigned in total, the team value \( F(S) = \sum_i f_i(S_i) \) of the global greedy solution \( S_{\text{greedy}} \) satisfies

\[ F(S_{\text{greedy}}) \ge \bigl(1 - 1/\mathrm{e}\bigr) F(S^\star), \]

where \( S^\star \) is an optimal allocation and \( \mathrm{e} \) is Euler’s number. This provides a rigorous performance guarantee for greedy bundle-based task allocation.

The key optimality concept for auction algorithms is \( \varepsilon \)-complementary slackness (\( \varepsilon \)-CS). Let \( p_j \) be the prices and let each robot be assigned to at most one task. The pair (assignment \( x \), prices \( p \)) satisfies \( \varepsilon \)-CS if:

1. For every assigned pair \( (i,j) \) with \( x_{ij} = 1 \),

   \[ v_{ij} - p_j \ge \max_{k} \bigl( v_{ik} - p_k \bigr) - \varepsilon. \]

2. Every unassigned task has nonnegative price, e.g. \( p_j \ge 0 \).

Intuitively, \( i \) prefers its assigned task \( j \) up to an \( \varepsilon \) margin compared to any alternative.

Theorem. Suppose (assignment \( x \), prices \( p \)) satisfy \( \varepsilon \)-CS. Let \( V(x) \) be the team valuation of \( x \) and \( V^\star \) the optimal valuation. Then

\[ V^\star \le V(x) + n \varepsilon. \]

Proof sketch. Let \( i \) be assigned to task \( j(i) \) under \( x \); if robot \( i \) is unassigned, set \( j(i) \) arbitrarily. From \( \varepsilon \)-CS,

\[ v_{i j(i)} - p_{j(i)} \ge v_{ik} - p_k - \varepsilon \quad \forall k. \]

Using these inequalities for robots in the optimal assignment and summing across robots, one can show that the total dual price upper bound exceeds \( V(x) \) by at most \( n \varepsilon \). Combining with strong duality yields the bound above. As \( \varepsilon \to 0 \), the auction solution converges to optimal.

Standard auction algorithms maintain \( \varepsilon \)-CS by construction. Each bid increases prices just enough to restore the inequality, so every iteration improves the dual objective while preserving primal feasibility. This monotonicity underlies finite-time convergence.

We now implement a minimal synchronous distributed auction for a one-to-one assignment in Python. For simplicity, we simulate communication in a central loop while keeping robot logic local.

import numpy as np

class Robot:
    def __init__(self, idx, values, epsilon=0.01):
        self.idx = idx
        self.values = np.array(values, dtype=float)  # v_ij
        self.epsilon = epsilon
        self.assigned_task = None

    def is_unassigned(self):
        return self.assigned_task is None

    def compute_bid(self, prices):
        # reduced utility u_j = v_ij - p_j
        reduced = self.values - prices
        # best and second-best tasks
        j1 = int(np.argmax(reduced))
        best = reduced[j1]
        # mask out j1 to get second-best
        mask = np.ones_like(reduced, dtype=bool)
        mask[j1] = False
        if np.any(mask):
            second = np.max(reduced[mask])
        else:
            second = -np.inf
        bid = prices[j1] + (best - second) + self.epsilon
        return j1, bid

def distributed_auction(value_matrix, epsilon=0.01, max_iters=1000):
    """
    value_matrix: shape (n_robots, n_tasks), v_ij >= 0
    """
    n_robots, n_tasks = value_matrix.shape
    robots = [Robot(i, value_matrix[i], epsilon) for i in range(n_robots)]
    prices = np.zeros(n_tasks)
    winners = np.full(n_tasks, fill_value=-1, dtype=int)

    it = 0
    while it < max_iters and any(r.is_unassigned() for r in robots):
        it += 1
        # local bids
        bids_for_task = {j: [] for j in range(n_tasks)}
        for r in robots:
            if r.is_unassigned():
                j, b = r.compute_bid(prices)
                bids_for_task[j].append((b, r.idx))

        # "distributed" resolution: for each task, keep highest bid
        for j, bids in bids_for_task.items():
            if not bids:
                continue
            bids.sort(key=lambda x: x[0], reverse=True)
            best_bid, best_robot = bids[0]
            prices[j] = best_bid
            # unassign previous winner if any
            prev = winners[j]
            if prev != -1 and prev != best_robot:
                robots[prev].assigned_task = None
            winners[j] = best_robot
            robots[best_robot].assigned_task = j

    assignment = np.full(n_robots, fill_value=-1, dtype=int)
    for j, r_idx in enumerate(winners):
        if r_idx != -1:
            assignment[r_idx] = j

    return assignment, prices

if __name__ == "__main__":
    # Example: 3 robots, 3 tasks, valuations inversely related to travel cost
    value_matrix = np.array([
        [10.0,  8.0,  9.0],
        [ 9.0, 11.0,  7.0],
        [ 8.5,  9.5, 12.0],
    ])
    assignment, prices = distributed_auction(value_matrix, epsilon=0.01)
    print("Assignment (robot -> task):", assignment)
    print("Final prices:", prices)
      

In a ROS-based multi-robot system, each Robot instance would run in its own node, exchange bids and prices using topics or services, and integrate assigned_task with a local motion planner.

The following C++ snippet shows the core bidding logic for a robot. It can be embedded in a ROS node using roscpp, where bids are exchanged over topics.

#include <vector>
#include <limits>
#include <utility>

struct Bid {
    int task;
    double amount;
};

class Robot {
public:
    Robot(int id, const std::vector<double>& v, double eps)
        : id_(id), values_(v), epsilon_(eps), assignedTask_(-1) {}

    bool isUnassigned() const { return assignedTask_ < 0; }

    Bid computeBid(const std::vector<double>& prices) const {
        const double NEG_INF = -std::numeric_limits<double>::infinity();
        double best = NEG_INF, second = NEG_INF;
        int j1 = -1;
        for (int j = 0; j < (int)values_.size(); ++j) {
            double reduced = values_[j] - prices[j];
            if (reduced > best) {
                second = best;
                best = reduced;
                j1 = j;
            } else if (reduced > second) {
                second = reduced;
            }
        }
        double bidAmount = prices[j1] + (best - second) + epsilon_;
        return Bid{j1, bidAmount};
    }

    int id_;
    std::vector<double> values_;
    double epsilon_;
    int assignedTask_;
};
      

A coordinator (which could itself be distributed via consensus) would maintain a vector of current prices, collect bids from robots, and update winners and prices for each task analogously to the Python implementation.

The Java snippet below represents a single robot’s bid computation. It can be integrated into a multi-threaded simulation or a distributed middleware such as JADE for agent-based robotics.

public class Robot {
    private final int id;
    private final double[] values;
    private final double epsilon;
    private int assignedTask = -1;

    public Robot(int id, double[] values, double epsilon) {
        this.id = id;
        this.values = values;
        this.epsilon = epsilon;
    }

    public boolean isUnassigned() {
        return assignedTask < 0;
    }

    public Bid computeBid(double[] prices) {
        double best = Double.NEGATIVE_INFINITY;
        double second = Double.NEGATIVE_INFINITY;
        int j1 = -1;
        for (int j = 0; j < values.length; ++j) {
            double reduced = values[j] - prices[j];
            if (reduced > best) {
                second = best;
                best = reduced;
                j1 = j;
            } else if (reduced > second) {
                second = reduced;
            }
        }
        double amount = prices[j1] + (best - second) + epsilon;
        return new Bid(j1, amount, id);
    }

    public static class Bid {
        public final int task;
        public final double amount;
        public final int robotId;
        public Bid(int task, double amount, int robotId) {
            this.task = task;
            this.amount = amount;
            this.robotId = robotId;
        }
    }
}
      

A central or distributed controller aggregates Bid objects, selects the highest bid per task, and notifies robots of the updated winners and prices.

MATLAB is widely used for rapid prototyping of auction-based task allocation. The function below implements a basic auction for one-to-one assignment. It can be embedded in a Simulink model via a MATLAB Function block that interacts with kinematic or dynamic subsystems for each robot.

function [assignment, prices] = auctionTaskAllocation(V, epsilon, maxIters)
% V: nR x nT matrix of valuations v_ij
% epsilon: small positive scalar
% assignment: length-nR vector (robot -> task index or -1)
% prices: length-nT vector of task prices

if nargin < 2
    epsilon = 0.01;
end
if nargin < 3
    maxIters = 1000;
end

[nR, nT] = size(V);
prices = zeros(1, nT);
winners = -ones(1, nT);  % winner robot index per task
assignment = -ones(1, nR);

iter = 0;
while iter < maxIters && any(assignment == -1)
    iter = iter + 1;
    bidsPerTask = cell(1, nT);
    % local bidding
    for i = 1:nR
        if assignment(i) ~= -1
            continue;
        end
        reduced = V(i,:) - prices;
        [best, j1] = max(reduced);
        reduced(j1) = -inf;
        second = max(reduced);
        bidAmount = prices(j1) + (best - second) + epsilon;
        bidsPerTask{j1}(end+1, :) = [bidAmount, i]; %#ok<AGROW>
    end
    % resolve bids
    for j = 1:nT
        if isempty(bidsPerTask{j})
            continue;
        end
        B = bidsPerTask{j};
        [~, idx] = max(B(:,1));
        bestBid = B(idx,1);
        bestRobot = B(idx,2);
        prices(j) = bestBid;
        prevWinner = winners(j);
        if prevWinner ~= -1 && prevWinner ~= bestRobot
            assignment(prevWinner) = -1;
        end
        winners(j) = bestRobot;
        assignment(bestRobot) = j;
    end
end
      

In Simulink, each robot can be modeled as a subsystem that calls auctionTaskAllocation in discrete time, or the auction may run in a centralized supervisory block while individual robot subsystems implement low-level motion control for their current assigned task.

Mathematica can also implement the auction algorithm using symbolic or numerical values. Below we implement a simple synchronous auction for a square valuation matrix.

AuctionAllocation[valueMatrix_, eps_: 0.01, maxIters_: 1000] :=
 Module[{n, prices, winners, assignment, it, unassignedQ, bids, reduced,
   bestIdx, best, second, bidAmt, i, j},
  n = Length[valueMatrix];
  prices = ConstantArray[0.0, n];
  winners = ConstantArray[-1, n];
  assignment = ConstantArray[-1, n];
  it = 0;
  unassignedQ[] := MemberQ[assignment, -1];

  While[it < maxIters && unassignedQ[],
   it++;
   bids = Table[{}, {n}];
   (* local bids *)
   Do[
    If[assignment[[i]] == -1,
     reduced = valueMatrix[[i]] - prices;
     bestIdx = First@Ordering[reduced, -1];
     best = reduced[[bestIdx]];
     reduced[[bestIdx]] = -Infinity;
     second = Max[reduced];
     bidAmt = prices[[bestIdx]] + (best - second) + eps;
     bids[[bestIdx]] = Append[bids[[bestIdx]], {bidAmt, i}];
     ],
    {i, 1, n}
    ];
   (* resolve bids *)
   Do[
    If[bids[[j]] =!= {},
     (* sort by bid amount descending *)
     bids[[j]] = Reverse@SortBy[bids[[j]], First];
     {bidAmt, i} = bids[[j, 1]];
     prices[[j]] = bidAmt;
     If[winners[[j]] =!= -1 && winners[[j]] =!= i,
      assignment[[winners[[j]]]] = -1;
      ];
     winners[[j]] = i;
     assignment[[i]] = j;
     ],
    {j, 1, n}
    ];
   ];
  <<"Assignment:">> -> assignment, <<"Prices:">> -> prices
  ]
      

This implementation is suitable for symbolic experiments on convergence and sensitivity analysis of market-based task allocation under different valuation models \( v_{ij} \) and step sizes \( \varepsilon \).

Problem 1 (Primal–dual formulation). Consider the one-to-one assignment problem with valuations \( v_{ij} \). Derive the dual LP explicitly and interpret the dual constraints as price feasibility conditions.

Solution. The primal is

\[ \max_{x_{ij} \ge 0} \sum_{i,j} v_{ij} x_{ij} \quad \text{s.t.} \quad \sum_j x_{ij} = 1,\; \sum_i x_{ij} = 1. \]

Associate dual variables \( \alpha_i \) and \( \beta_j \) with the robot and task constraints, respectively. The dual objective is

\[ \min_{\alpha,\beta} \sum_i \alpha_i + \sum_j \beta_j \]

and the dual constraints are obtained by bounding each primal variable’s contribution: \( \alpha_i + \beta_j \ge v_{ij} \) for all \( i,j \). These constraints state that the sum of robot utility \( \alpha_i \) and task price \( \beta_j \) must exceed the robot’s valuation for that task, otherwise robot \( i \) would strictly prefer \( j \) at the current prices.

Problem 2 (One iteration of auction). Three robots and three tasks have valuations

\[ V = \begin{bmatrix} 8 & 6 & 5 \\ 7 & 9 & 4 \\ 6 & 5 & 10 \end{bmatrix}. \]

Suppose all prices are initially zero and \( \varepsilon = 0.1 \). Perform one synchronous iteration of bidding: compute each robot’s best and second-best task, its bid, and the resulting prices and assignments.

Solution.

• Robot 1: reduced utilities are \( [8, 6, 5] \); best is task 1, second-best is task 2. Bid: \( b_1 = 0 + (8 - 6) + 0.1 = 2.1 \).
• Robot 2: reduced utilities \( [7, 9, 4] \); best task 2, second-best task 1. Bid: \( b_2 = 0 + (9 - 7) + 0.1 = 2.1 \).
• Robot 3: reduced utilities \( [6, 5, 10] \); best task 3, second-best task 1. Bid: \( b_3 = 0 + (10 - 6) + 0.1 = 4.1 \).

After collecting bids, tasks 1, 2, and 3 receive bids from robots 1, 2, and 3 respectively. Prices become \( p = [2.1, 2.1, 4.1] \), and the tentative assignment is: robot 1 → task 1, robot 2 → task 2, robot 3 → task 3.

Problem 3 (\( \varepsilon \)-CS bound). Let \( x \) and \( p \) satisfy \( \varepsilon \)-CS for an assignment of \( n \) robots. Show that the dual objective \( D = \sum_i \alpha_i + \sum_j \beta_j \) deviates from the primal valuation \( V(x) \) by at most \( n \varepsilon \).

Solution (sketch). For each assigned robot \( i \) with winner \( j(i) \), \( \varepsilon \)-CS implies

\[ v_{i j(i)} \ge \max_k \bigl( v_{ik} - p_k \bigr) + p_{j(i)} - \varepsilon. \]

Combining with dual feasibility \( \alpha_i + \beta_k \ge v_{ik} \) and summing over all robots, one obtains \( D - V(x) \le n \varepsilon \). Using strong duality \( V^\star = D^\star \le D \) proves \( V^\star \le V(x) + n \varepsilon \).

Problem 4 (Submodularity of tour cost). For a single robot, let \( S \subseteq T \) be a set of tasks and \( c(S) \) the length of the optimal tour starting and ending at the robot’s base that visits all tasks in \( S \). Define the negative cost \( f(S) = -c(S) \) as the bundle value. Argue why \( f \) is approximately submodular in practice (even if not strictly so).

Solution. Adding a new task \( t \) to a small set of tasks typically requires a larger increase in tour length than adding it to a large set, because more insertion positions are available in a larger tour and the new detour can be spread over multiple edges. Thus the marginal gain \( f(S \cup \{t\}) - f(S) \) tends to decrease with \( |S| \), matching the submodularity inequality. Although strict submodularity may fail in some instances, empirical studies demonstrate that greedy insertion heuristics yield good approximations, supporting the modeling assumption.

Problem 5 (Distributed convergence and connectivity). Consider a distributed auction where robots exchange their local views of prices and winners with neighbors over a time-varying communication graph. State a sufficient connectivity condition for convergence to the centralized auction solution.

Solution. A typical sufficient condition is that the union of communication graphs over any time window of length \( L \) is strongly connected (joint strong connectivity). This ensures that information about price and winner updates eventually propagates to every robot, so all robots’ local views agree in the limit and the distributed process emulates the centralized auction.

In this lesson we formalized multi-robot task allocation as an assignment or bundle-optimization problem, revealed its dual price structure, and developed auction-based algorithms that exploit local computations and limited communication. We introduced \( \varepsilon \)-complementary slackness as a bridge between local bidding rules and global near-optimality, and discussed bundle auctions under submodular valuations. Finally, we provided multi-language implementations suitable for embedding into motion-planning frameworks in advanced robotic systems.