  We present a scalable algorithm for learning parametric constraints in high
dimensions from safe expert demonstrations. To reduce the ill-posedness of the
constraint recovery problem, our method uses hit-and-run sampling to generate
lower cost, and thus unsafe, trajectories. Both safe and unsafe trajectories
are used to obtain a representation of the unsafe set that is compatible with
the data by solving an integer program in that representation's parameter
space. Our method can either leverage a known parameterization or incrementally
grow a parameterization while remaining consistent with the data, and we
provide theoretical guarantees on the conservativeness of the recovered unsafe
set. We evaluate our method on high-dimensional constraints for
high-dimensional systems by learning constraints for 7-DOF arm, quadrotor, and
planar pushing examples, and show that our method outperforms baseline
approaches.
