Efficient Symbolic Reactive Synthesis for Finite-Horizon Tasks

K. He, A. M. Wells, L. E. Kavraki, and M. Y. Vardi, “Efficient Symbolic Reactive Synthesis for Finite-Horizon Tasks,” in IEEE Intl. Conf. on Robotics and Automation, 2019.


When humans and robots perform complex tasks together, the robot must have a strategy to choose its actions based on observed human behavior. One well-studied approach for finding such strategies is reactive synthesis. Existing ap- proaches for finite-horizon tasks have used an explicit state approach, which incurs high runtime. In this work, we present a compositional approach to perform synthesis for finite- horizon tasks based on binary decision diagrams. We show that for pick-and-place tasks, the compositional approach achieves exponential speed-ups compared to previous approaches. We demonstrate the synthesized strategy on a UR5 robot.

PDF preprint: http://kavrakilab.org/publications/he2019efficient-symbolic-reactive-synthesis-for-finite-horizon-tasks.pdf