A Control- Theoretic Framework for Voronoi-like Space Partitioning in Multi-Agent Drone Systems with Second-Order Costs

We present a framework for space partitioning, where the Regions of Influence (ROIs) of the agents are defined based on proximity metrics derived from the cost of optimal control problems. Efficient space partitioning in multi-agent systems, particularly in Unmanned Aerial Vehicle (UAV) operations, is critical for coverage, load balancing, and task allocation. However, traditional methods, such as the standard Voronoi Diagrams (VDs) based solely on distances, often fail to account for the dynamic behavior and capabilities of UAV s. We generalize the VD concept by replacing distance-based metrics with transition costs obtained from optimal control formulations. This allows the resulting partitions to incorporate UAV dynamics, including initial states and control effort, in defining regions where one agent is more suitable than another for a given task. We show that for a broad class of problems with second-order optimal costs, the boundaries between ROIs are given by either hyperplanes or quadratic surfaces. This includes, as special cases, classical VDs based on distance, minimum-time problems for single integrators, the fixed-final-state (FFS) optimal transfer problem, and Linear Quadratic Regulators (LQR). Overall, the proposed framework bridges geometric and control-theoretic space partitioning, enabling dynamic and context-aware task allocation in multi-agent systems.