  We present a new approach for modeling avoidance constraints in 2D
environments, in which waypoints are assigned to obstacle-free polyhedral
regions. Constraints of this form are often formulated as mixed-integer
programming (MIP) problems employing big-M techniques -- however, these are
generally not the strongest formulations possible with respect to the MIP's
convex relaxation (so called ideal formulations), potentially resulting in
larger computational burden. We instead model obstacle avoidance as
combinatorial disjunctive constraints and leverage the independent branching
scheme to construct small, ideal formulations. As our approach requires a
biclique cover for an associated graph, we exploit the structure of this class
of graphs to develop a fast subroutine for obtaining biclique covers in
polynomial time. We also contribute an open-source Julia library named
ClutteredEnvPathOpt to facilitate computational experiments of MIP formulations
for obstacle avoidance. Experiments have shown our formulation is more compact
and remains competitive on a number of instances compared with standard big-M
techniques, for which solvers possess highly optimized procedures.
