pith. sign in

arxiv: 2606.17388 · v1 · pith:OW5J7X2Knew · submitted 2026-06-16 · 💻 cs.RO · cs.CG· cs.SY· eess.SY

Agent Utilities over Generalized Voronoi Regions and their Gradients

Andre N. Costa , Petter \"Ogren , Carlos H. C. Ribeiro This is my paper

Pith reviewed 2026-06-27 01:29 UTC · model grok-4.3

classification 💻 cs.RO cs.CGcs.SYeess.SY
keywords Cost-Induced Voronoi regionsutility gradientsReynolds Transport Theoremmulti-agent systemsLQR costssoccer simulation
0
0 comments X

The pith

Agent utilities over cost-induced Voronoi regions have gradients that the Reynolds Transport Theorem computes an order of magnitude faster than finite differences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper generalizes ordinary Voronoi partitions to Cost-Induced Voronoi regions whose boundaries are level sets of a cost function, such as the optimal cost of an LQR problem; in this setting the agent's full state can include velocity while the partitioned space remains position only. Utility for each agent is defined as the integral of an arbitrary density over its own region, so that the value directly measures quantities like the probability an agent receives a pass in a soccer scenario. The central result is that the gradient of this integral with respect to agent state is obtained by applying the Reynolds Transport Theorem to the moving boundaries, producing a formula whose numerical evaluation matches the accuracy of finite-difference approximations yet runs roughly ten times faster.

Core claim

Agent utilities defined as integrals of a utility density over Cost-Induced Voronoi regions admit gradients that can be computed using the Reynolds Transport Theorem, achieving similar accuracy to finite-difference methods while reducing computation time by about an order of magnitude.

What carries the argument

Cost-Induced Voronoi (CIV) regions whose boundaries equate costs evaluated at different agent states, together with the Reynolds Transport Theorem applied to the time-varying boundaries of these regions.

If this is right

  • The probability of beneficial events such as pass reception can be increased by moving each agent along the computed utility gradient.
  • The same gradient formula applies to any utility density integrated over CIV regions generated by arbitrary cost functions.
  • Real-time multi-agent optimization becomes practical once the per-step gradient cost drops by an order of magnitude.
  • The method remains valid when the agent's state vector is larger than the space being partitioned, as occurs with LQR costs that include velocity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same boundary-transport approach may extend to other smooth cost functions arising from optimal control beyond the LQR case examined.
  • Gradient-based coordination could be applied to teams whose members obey different dynamics, provided each cost remains well-defined.
  • Empirical scaling tests on state spaces larger than the two-dimensional soccer example would be needed to confirm continued runtime gains.

Load-bearing premise

The Reynolds Transport Theorem can be applied directly to the time-varying boundaries of Cost-Induced Voronoi regions defined by an arbitrary cost function without additional regularity conditions on the cost or the utility density.

What would settle it

A numerical test in which the Reynolds-Transport-Theorem gradient differs by more than a small tolerance from a high-resolution finite-difference reference gradient on a low-dimensional CIV example whose boundary motion is known analytically.

Figures

Figures reproduced from arXiv: 2606.17388 by Andre N. Costa, Carlos H. C. Ribeiro, Petter \"Ogren.

Figure 1
Figure 1. Figure 1: LQR-Cost-Induced Voronoi regions (LQR-CIV), and their gradients, [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of CIV boundary shifts v T b nˆi as a function of x˙ i, in Equation (14) for two special cases, described in Remark 3. (a) If all other agents have constant costs, while one has radially increasing, the boundary ∂D is circular, following the agent x. (b) For classical Voronoi boundaries, ∂D moves uniformly (translates) when the agent moves towards the other agent (blue arrow and lines), but pi… view at source ↗
read the original abstract

In this paper, we generalize the concept of Voronoi regions, define agent utility as the integral of a utility density over the corresponding Voronoi region, derive gradients of the utility, and illustrate the approach in a two-team example from soccer. The generalization of Voronoi regions is in the form of so-called Cost-Induced Voronoi (CIV) regions, where the agent state space may differ from the space being partitioned. One example of such regions is when the cost is given by the optimal solution of an LQR control problem. Then the agent states include position as well as velocity, while the partitioned space only includes positions. The agent utility is defined by integrating some utility density over the CIV region of the agent. This utility density might be the probability density of some beneficial event, such as receiving a pass in soccer. The utility is then the overall probability of receiving a pass and the gradient represents a way to improve that probability. We show how this utility gradient can be computed using the Reynolds Transport Theorem from fluid mechanics, and that this approach achieves similar accuracy while reducing computation time by about an order of magnitude compared to a baseline finite-difference approximation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript generalizes Voronoi regions to Cost-Induced Voronoi (CIV) regions, where partitioning is induced by a cost function (such as LQR optimal cost) that may act on a state space different from the partitioned space. Agent utility is defined as the integral of a density ho over an agent's CIV region; the central technical contribution is a derivation of the utility gradient with respect to agent state via the Reynolds Transport Theorem, with an empirical claim that this yields accuracy comparable to finite differences while reducing computation time by roughly an order of magnitude, illustrated on a two-team soccer example.

Significance. If the central derivation is valid, the work supplies an efficient, differentiable utility model for multi-agent planning and optimization problems in robotics and games, where utilities are defined over regions whose boundaries move with agent states. The explicit importation of the Reynolds Transport Theorem and the reported timing comparison constitute concrete strengths that could be useful for real-time gradient-based methods.

major comments (2)
  1. [Gradient derivation section] Gradient derivation section (application of Reynolds Transport Theorem): the formula for d/ds ∫_CIV_i(s) ho(x) dx is obtained by invoking the Reynolds Transport Theorem on the moving boundary ∂CIV_i without stating or verifying the required regularity (C^1 dependence of the cost c(s,x) on both arguments and Lipschitz continuity of the induced boundary velocity); this assumption is load-bearing for both the correctness of the gradient and the claimed speedup over finite differences, yet is not addressed for the LQR case or the asserted generality to arbitrary costs.
  2. [Empirical validation paragraph] Empirical validation paragraph: the reported order-of-magnitude speedup and accuracy equivalence are presented without error bars, number of trials, or explicit handling of boundary cases (e.g., when level sets become non-smooth), making it impossible to assess whether the RTT formula remains stable under the conditions actually encountered in the soccer example.
minor comments (2)
  1. [Introduction] Notation for the cost function c_i(s,x) and the utility density ho should be introduced with explicit domain and codomain dimensions in the first use, to clarify the distinction between agent state space and partitioned space.
  2. [Abstract] The abstract states the speedup result but does not mention the regularity conditions that the derivation implicitly relies upon; adding a single qualifying clause would improve clarity without lengthening the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Gradient derivation section] Gradient derivation section (application of Reynolds Transport Theorem): the formula for d/ds ∫_CIV_i(s) ρ(x) dx is obtained by invoking the Reynolds Transport Theorem on the moving boundary ∂CIV_i without stating or verifying the required regularity (C^1 dependence of the cost c(s,x) on both arguments and Lipschitz continuity of the induced boundary velocity); this assumption is load-bearing for both the correctness of the gradient and the claimed speedup over finite differences, yet is not addressed for the LQR case or the asserted generality to arbitrary costs.

    Authors: We agree that the regularity conditions for applying the Reynolds Transport Theorem must be stated explicitly. In the revision we will add a paragraph in the gradient derivation section specifying that the cost c(s, x) must be C^1 in both arguments and that the induced boundary velocity must be Lipschitz continuous. For the LQR case the optimal cost is quadratic (hence C^∞) wherever the Riccati solution exists, and the resulting level sets yield Lipschitz boundaries away from isolated singularities; we will note this explicitly. The same conditions will be stated for the claimed generality to other costs. revision: yes

  2. Referee: [Empirical validation paragraph] Empirical validation paragraph: the reported order-of-magnitude speedup and accuracy equivalence are presented without error bars, number of trials, or explicit handling of boundary cases (e.g., when level sets become non-smooth), making it impossible to assess whether the RTT formula remains stable under the conditions actually encountered in the soccer example.

    Authors: We acknowledge the absence of statistical detail and boundary-case discussion. The revised manuscript will report the number of trials, include mean and standard-deviation error bars for both timing and accuracy metrics, and add a short subsection examining stability when level sets become non-smooth. We will also include additional runs focused on the soccer example to confirm that the RTT gradient remains well-behaved under the observed conditions. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation applies external RTT theorem to defined integrals

full rationale

The paper defines CIV regions via a cost function and agent utility as the integral of density ρ over the region. The gradient derivation invokes the Reynolds Transport Theorem (an external fluid-mechanics result) to obtain the surface integral over the moving boundary; this step does not reduce to any fitted parameter, self-defined quantity, or self-citation chain within the paper. No equations equate a claimed prediction back to its own inputs by construction, and the reported speedup is an empirical comparison against finite differences rather than a tautological renaming. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The approach rests on the applicability of the Reynolds Transport Theorem to moving CIV boundaries and on the existence of well-defined partitions induced by the chosen cost function; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Reynolds Transport Theorem applies without modification to the boundaries of Cost-Induced Voronoi regions.
    Invoked to obtain the utility gradient from the integral definition.
invented entities (1)
  • Cost-Induced Voronoi (CIV) region no independent evidence
    purpose: Generalized partition where cost may depend on agent state (e.g., velocity) while the partitioned space is positions only.
    Core new object enabling the utility definition; no independent evidence supplied beyond the definition.

pith-pipeline@v0.9.1-grok · 5748 in / 1264 out tokens · 38349 ms · 2026-06-27T01:29:14.474238+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references

  1. [1]

    A control-theoretic framework for voronoi- like space partitioning in multi-agent drone systems with second- order costs,

    A. N. Costa and P. ¨Ogren, “A control-theoretic framework for voronoi- like space partitioning in multi-agent drone systems with second- order costs,” in2025 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 2025, pp. 1049–1056

    2025

  2. [2]

    Coverage control for mobile sensing networks,

    J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,”IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243–255, Apr. 2004

    2004

  3. [3]

    Bullo, J

    F. Bullo, J. Cort ´es, and S. Mart´ınez,Distributed control of robotic net- works: a mathematical approach to motion coordination algorithms. Princeton University Press, Dec. 2009

    2009

  4. [4]

    Multi-robot coverage and exploration in non-euclidean metric spaces,

    S. Bhattacharya, R. Ghrist, and V . Kumar, “Multi-robot coverage and exploration in non-euclidean metric spaces,” inAlgorithmic Foun- dations of Robotics X: Proceedings of the 10th Workshop on the Algorithmic Foundations of Robotics. Springer Berlin Heidelberg, 2013, pp. 495–511

    2013

  5. [5]

    Least squares quantization in pcm,

    S. P. Lloyd, “Least squares quantization in pcm,”IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982

    1982

  6. [6]

    Centroidal voronoi tessellations: Applications and algorithms,

    Q. Du, V . Faber, and M. Gunzburger, “Centroidal voronoi tessellations: Applications and algorithms,”SIAM review, vol. 41, no. 4, pp. 637– 676, 1999

    1999

  7. [7]

    Mahalanobis centroidal voronoi tessella- tions,

    R. Richter and M. Alexa, “Mahalanobis centroidal voronoi tessella- tions,”Computers & Graphics, vol. 46, pp. 48–54, 2015

    2015

  8. [8]

    2d voronoi coverage control with gaussian density functions by line integration,

    N. Hayashi, K. Segawa, and S. Takai, “2d voronoi coverage control with gaussian density functions by line integration,”SICE Journal of Control, Measurement, and System Integration, vol. 10, no. 2, pp. 110–116, 2017

    2017

  9. [9]

    Generalized coverage control for time-varying density functions,

    J. Kennedy, A. Chapman, and P. M. Dower, “Generalized coverage control for time-varying density functions,” in2019 18th European Control Conference (ECC), Naples, Italy, 2019, pp. 71–76

    2019

  10. [10]

    Optimal pursuit of moving targets using dynamic voronoi diagrams,

    E. Bakolas and P. Tsiotras, “Optimal pursuit of moving targets using dynamic voronoi diagrams,” in49th IEEE Conference on Decision and Control (CDC). IEEE, 2010, pp. 7431–7436

    2010

  11. [11]

    Optimal partitioning for multi-vehicle systems using quadratic performance criteria,

    E. Bakolas, “Optimal partitioning for multi-vehicle systems using quadratic performance criteria,”Automatica, vol. 49, no. 11, pp. 3377– 3383, 2013

    2013

  12. [12]

    Partitioning algorithms for multi-agent systems based on finite- time proximity metrics,

    ——, “Partitioning algorithms for multi-agent systems based on finite- time proximity metrics,”Automatica, vol. 55, pp. 176–182, 2015

    2015

  13. [13]

    Optimizing the locations of opposing teams using adversarial voronoi regions,

    A. N. Costa and P. ¨Ogren, “Optimizing the locations of opposing teams using adversarial voronoi regions,” in2025 European Control Conference (ECC). IEEE, 2025, pp. 1047–1054

    2025

  14. [14]

    Cooperative pursuit with voronoi partitions,

    Z. Zhou, W. Zhang, J. Ding, H. Huang, D. M. Stipanovi ´c, and C. J. Tomlin, “Cooperative pursuit with voronoi partitions,”Automatica, vol. 72, pp. 64–72, Oct. 2016

    2016

  15. [15]

    Intercepting Rogue Robots: An Algorithm for Capturing Multiple Evaders With Multiple Pur- suers,

    A. Pierson, Z. Wang, and M. Schwager, “Intercepting Rogue Robots: An Algorithm for Capturing Multiple Evaders With Multiple Pur- suers,”IEEE Robotics and Automation Letters, Apr. 2017

    2017

  16. [16]

    L. G. Leal,Advanced transport phenomena: fluid mechanics and convective transport processes. Cambridge University Press, 2007, vol. 7

    2007