Mixed Integer Linear Programming for Multi Agent Task Allocation

15 concepts13 papers1 proposal

When coordinating a team of agents—whether they are delivery drones, autonomous factory cranes, or emergency response vehicles—we must solve two fundamentally interlocking problems simultaneously: allocation (deciding which agent performs which task) and scheduling (deciding when each task occurs).

As the number of agents and tasks grows, the space of possible schedules explodes combinatorially. Worse, real-world physical constraints are deeply interdependent. A delay in one robot's schedule can cause a cascade of collisions or missed deadlines across the entire fleet.

To solve this reliably, modern multi-agent systems increasingly rely on Mixed-Integer Linear Programming (MILP). By translating discrete logical choices and continuous physical constraints into a unified geometric framework, MILP allows exact mathematical solvers to find globally optimal schedules that guarantee safety, timing, and efficiency.


The Core Intuition: Coupling Logic with Continuous Physics

The power of MILP lies in its ability to bridge two different mathematical worlds: discrete decisions (integers) and continuous variables (real numbers).

In a multi-agent scenario, we can represent discrete choices using binary variables ($x \in \{0, 1\}$). For instance, we might state that $x_{ij} = 1$ if Agent $i$ is assigned to Task $j$, and $0$ otherwise. Early foundations in real-time coordination, such as the framework proposed by Natsuki Miyata et al. in their cooperative transport study, used linear programming to dynamically match individual robots to high-priority tasks in each control cycle, maximizing collective utility.

However, real-world tasks also involve continuous variables like time, distance, and energy. The true challenge is making the discrete choices control the continuous physics. If Agent $i$ does not visit Task $j$ followed by Task $k$, the travel time between those two locations should not impact the schedule.

To achieve this, researchers use a mathematical mechanism known as the Big-M method. Imagine we want to enforce a timeline where the start time of Task $k$ ($t_k$) must be greater than the completion time of Task $j$ ($t_j$) plus the travel time ($\Delta \tau_{jk}$), but only if the agent actually travels directly from $j$ to $k$ ($y_{jk} = 1$). We write the constraint as:

$$t_k \ge t_j + \Delta \tau_{jk} - M(1 - y_{jk})$$

Here, $M$ is an extraordinarily large constant.

  • If $y_{jk} = 1$, the term $M(1 - 1)$ becomes zero, strictly enforcing the physical travel timeline.
  • If $y_{jk} = 0$, the term becomes $-M$, making the inequality trivially true regardless of the values of $t_k$ and $t_j$. This effectively "turns off" the constraint.

This elegant trick allows discrete routing logic to seamlessly govern continuous timelines. For example, Zhenmin Huang et al. leveraged Big-M formulations in their cooperative decision-making framework to transform discrete driving logic and non-linear spatial constraints into a solvable linear format, ensuring collision-free, globally optimal paths for connected autonomous vehicles across arbitrary road layouts.


Translating High-Level Logic into Linear Equations

Multi-agent missions are rarely simple lists of independent tasks. They often come with complex temporal rules, such as "Task A and Task B can happen in parallel, but both must finish before Task C begins."

Recent research focuses on automatically compiling these high-level logical specifications directly into MILP constraints.

Temporal Logic and Partial Orders

To handle complex mission rules, planners use formal frameworks like Linear Temporal Logic (LTL) or Timed Partial Orders (TPOs). Xusheng Luo et al. demonstrated in their work on heterogeneous multi-robot systems that high-level temporal logic rules can be decomposed into subtasks and waypoints. By modeling these assignments similarly to a Vehicle Routing Problem (VRP), the MILP solver can efficiently distribute subtasks to diverse robots while guaranteeing that temporal rules are never violated.

Similarly, Kandai Watanabe et al. tackled time-sensitive sequences by translating Timed Partial Order specifications into a variant of the Traveling Salesman Problem in their optimal planning framework. Their model coordinates dozens of robots across hundreds of locations, minimizing the overall makespan by parallelizing tasks while strictly adhering to global timing dependencies.

[High-Level Specification: "Do A and B, then C"]
                 │
                 ▼
[Decomposition into Dependency Graphs / Posets]
                 │
                 ▼ (Big-M / Routing Transformations)
[MILP Constraints: t_C >= t_A + delta, etc.]
                 │
                 ▼
[Exact Solver Engine (CPLEX / Gurobi)] ──► [Optimal, Safe Multi-Agent Schedule]

Resource and Safety Boundaries

Beyond timing, MILP models can natively enforce physical resource limitations by treating them as linear inequalities:

  • Battery and Range Limits: Ariel Rosenfeld et al. designed a binary integer linear program to coordinate traffic enforcement drones and mobile police cruiser charging stations, tracking discrete battery depletion and replenishment schedules over time.
  • Deadlock Prevention: In heavy industrial settings, physical agents can block one another. Xie Xie et al. formulated a MILP model for industrial crane scheduling that explicitly maps task sequencing alongside resource interference constraints to prevent physical track conflicts. In wide-area networks, Anna Livia Croella et al. utilized binary linear programming to manage railway disruptions, using binary variables to assign trains to safe holding locations and prevent network-wide deadlocks.
  • Operational Constraints: In human-centric schedules, constraints must account for human factors. Jonathan Chase et al. incorporated shift scheduling models, manpower availability, and mandatory agent break times into a mixed-integer program for law enforcement deployment. For home health care logistics, Cen Chen et al. developed an integer linear programming model that balances strict arrival time windows with workload fairness and continuity of care.

Scaling Up: Hierarchies and Hybrid Frameworks

Because integer programming is fundamentally NP-hard, solving massive multi-agent problems directly can become computationally intractable. To scale these systems to real-world applications, modern architectures decouple semantic reasoning from numerical optimization.

Neuro-Symbolic and LLM Integration

One of the most powerful recent developments is pairing Large Language Models (LLMs) with mathematical solvers. While LLMs excel at understanding natural language and breaking down abstract goals, they struggle with precise mathematical optimization and are prone to "hallucinating" impossible schedules.

To solve this, the LiP-LLM framework introduced by Kazuma Obata et al. splits the labor in their task planning framework. The LLM is responsible only for translating a user's high-level request into a structured task dependency graph. This graph is then handed over to a linear programming solver, which calculates the actual agent assignments based on physical proximity and capabilities. This division of labor eliminates neural hallucinations and guarantees mathematically optimal execution costs.

┌────────────────────────────────────────────────────────┐
│                  HIGH-LEVEL SEMANTICS                  │
│  User: "Inspect the warehouse and recharge drones."    │
│  LLM: Generates abstract task dependency graph.        │
└───────────────────────────┬────────────────────────────┘
                            │
                            ▼ (Graph Structure)
┌────────────────────────────────────────────────────────┐
│                MATHEMATICAL OPTIMIZATION               │
│  MILP Solver: Computes exact spatial assignments,      │
│  timelines, and battery constraints.                   │
└───────────────────────────┬────────────────────────────┘
                            │
                            ▼
               [Feasible, Hallucination-Free Plan]

Similarly, the HERON framework developed by Taehyeon Kim et al. utilizes an LLM-to-MILP pipeline for long-horizon human-robot collaboration. The LLM handles task decomposition and physics-guided time estimation, while the MILP solver dynamically generates schedules that minimize completion time and workload distribution, allowing the robotic team to remain resilient against unpredictable human behavior.

Algorithmic Decomposition

When the problem cannot be simplified via an LLM, researchers use structural decomposition to accelerate the optimization process itself:

  • Hierarchical Allocation: In their hierarchical task allocation framework, Shaojun Xu et al. first decompose high-level goals into independent sub-tasks and infer their temporal relationships. They then run a localized MILP to assign these sub-tasks to individual robots, drastically reducing the number of variables the solver must evaluate simultaneously.
  • Subtour Elimination: For spatial coverage problems, such as multi-UAV mapping, the challenge is ensuring that agents do not get stuck in isolated loops. Youkyung Hong et al. designed a MILP formulation that explicitly incorporates subtour elimination constraints, ensuring that multiple drones cover an entire area seamlessly without overlapping or repeating paths.
  • Branch and Price: For massive hypothesis spaces—such as tracking and recognizing the plans of multiple interacting agents—instantiating every possible schedule up front is impossible. To circumvent this, Bikramjit Banerjee et al. introduced a Branch and Price approach. Instead of evaluating all combinations, they formulate a pricing subproblem as an integer program. This subproblem generates only the most promising plan candidates on the fly, achieving speedups of over 100x compared to traditional pruning methods.

By treating discrete choices as mathematical switches that govern continuous timelines, MILP provides a rigorous, flexible, and highly scalable foundation for multi-agent coordination, ensuring that high-level intent always translates into safe, efficient physical action.

Key Foundational Work

Cooperative Transport by Multiple Mobile Robots Associated with Task-assignment (2000) — contributed 1 concept elements to this direction.
Branch and Price for Multi-Agent Plan Recognition (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_programming_task_allocation_5d08884b,
  title = {linear programming task allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-programming-task-allocation/rdr_5d08884b337849a3ae831a4dcc5d7ec1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_programming_task_allocation_5d08884b_v1,
  title = {linear programming task allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-programming-task-allocation/rdr_5d08884b337849a3ae831a4dcc5d7ec1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake