Distributed submodular minimization and motion planning over discrete state space

Hassan Jaleel, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review


We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial optimization problems. While there has been a significant interest in the distributed formulations of convex optimization problems, distributed minimization of submodular functions has received relatively little research attention. Our framework relies on an equivalent convex reformulation of a submodular minimization problem, which is efficiently computable. We then use this relaxation to exploit methods for the distributed optimization of convex functions. The proposed framework is applicable to submodular set functions as well as to a wider class of submodular functions defined over certain lattices. We also propose an approach for solving distributed motion-planning problems in discrete state space based on submodular function minimization. We establish through a challenging setup of the capture the flag game that submodular functions over lattices can be used to design artificial potential fields for multiagent systems with discrete inputs. These potential fields are designed such that their minima correspond to desired behaviors, that is, agents are attracted toward their goals and are repulsed from obstacles and from each other for collision avoidance. Finally, we demonstrate that the proposed distributed framework can be employed effectively for generating feasible trajectories in such motion coordination problems.

Original languageEnglish (US)
Article number8792203
Pages (from-to)932-943
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Issue number2
StatePublished - Jun 2020
Externally publishedYes


  • Distributed algorithms/control
  • multi-robot systems
  • optimization
  • submodular optimization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'Distributed submodular minimization and motion planning over discrete state space'. Together they form a unique fingerprint.

Cite this