  Motivated by exploration of communication-constrained underground
environments using robot teams, we study the problem of planning for
intermittent connectivity in multi-agent systems. We propose a novel concept of
information-consistency to handle situations where the plan is not initially
known by all agents, and suggest an integer linear program for synthesizing
information-consistent plans that also achieve auxiliary goals. Furthermore,
inspired by network flow problems we propose a novel way to pose connectivity
constraints that scales much better than previous methods. In the second part
of the paper we apply these results in an exploration setting, and propose a
clustering method that separates a large exploration problem into smaller
problems that can be solved independently. We demonstrate how the resulting
exploration algorithm is able to coordinate a team of ten agents to explore a
large environment.
