  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 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 coordination problems in discrete state space
based on submodular function minimization. We establish through a challenging
setup of capture the flag game that submodular functions over lattices can be
used to design artificial potential fields over discrete state space in which
the agents are attracted towards their goals and are repulsed from obstacles
and from each other for collision avoidance.
