  The goal of programmatic Learning from Demonstration (LfD) is to learn a
policy in a programming language that can be used to control a robot's behavior
from a set of user demonstrations. This paper presents a new programmatic LfD
algorithm that targets long-horizon robot tasks which require synthesizing
programs with complex control flow structures, including nested loops with
multiple conditionals. Our proposed method first learns a program sketch that
captures the target program's control flow and then completes this sketch using
an LLM-guided search procedure that incorporates a novel technique for proving
unrealizability of programming-by-demonstration problems. We have implemented
our approach in a new tool called PROLEX and present the results of a
comprehensive experimental evaluation on 120 benchmarks involving complex tasks
and environments. We show that, given a 120 second time limit, PROLEX can find
a program consistent with the demonstrations in 80% of the cases. Furthermore,
for 81% of the tasks for which a solution is returned, PROLEX is able to find
the ground truth program with just one demonstration. In comparison, CVC5, a
syntax guided synthesis tool, is only able to solve 25% of the cases even when
given the ground truth program sketch, and an LLM-based approach, GPT-Synth, is
unable to solve any of the tasks due to the environment complexity.
