Distributed Submodular Minimization And Motion Planning Over Discrete State Space

Hassan Jaleel, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 desig
Original languageEnglish (US)
Pages (from-to)1-1
Number of pages1
JournalIEEE Transactions on Control of Network Systems
StatePublished - Aug 8 2019


Dive into the research topics of 'Distributed Submodular Minimization And Motion Planning Over Discrete State Space'. Together they form a unique fingerprint.

Cite this