Optimal Interactive Learning on the Job via Facility Location Planning
Shivam Vats*, Michelle Zhao*, Patrick Callaghan, Mingxi Jia, Maxim Likhachev, Oliver Kroemer, George KonidarisRSS, 2025
project site / paper / bibtex

We propose COIL (Cost-Optimal Interactive Learning), a multi-task interaction planner that minimizes human effort across a sequence of tasks by strategically selecting among three query types (skill, preference, and help). When user preferences are known, we formulate COIL as an uncapacitated facility location (UFL) problem, which enables bounded-suboptimal planning in polynomial time using off-the-shelf approximation algorithms. We extend our formulation to handle uncertainty in user preferences by incorporating one-step belief space planning, which uses these approximation algorithms as subroutines to maintain polynomial-time performance.











