  Efficient planning in continuous state and action spaces is fundamentally
hard, even when the transition model is deterministic and known. One way to
alleviate this challenge is to perform bilevel planning with abstractions,
where a high-level search for abstract plans is used to guide planning in the
original transition space. Previous work has shown that when state abstractions
in the form of symbolic predicates are hand-designed, operators and samplers
for bilevel planning can be learned from demonstrations. In this work, we
propose an algorithm for learning predicates from demonstrations, eliminating
the need for manually specified state abstractions. Our key idea is to learn
predicates by optimizing a surrogate objective that is tractable but faithful
to our real efficient-planning objective. We use this surrogate objective in a
hill-climbing search over predicate sets drawn from a grammar. Experimentally,
we show across four robotic planning environments that our learned abstractions
are able to quickly solve held-out tasks, outperforming six baselines. Code:
https://tinyurl.com/predicators-release
