MINT: Minimal Information Neuro-Symbolic Tree for Objective-Driven Knowledge-Gap Reasoning and Active Elicitation

Joint planning through language-based interactions is a key area of human-AI teaming. Planning problems in the open world often involve various aspects of incomplete information and unknowns, e.g., objects involved, human goals/intents -- thus leading to knowledge gaps in joint planning. We consider the problem of discovering optimal interaction strategies for AI agents to actively elicit human inputs in object-driven planning. To this end, we propose Minimal Information Neuro-Symbolic Tree (MINT) to reason about the impact of knowledge gaps and leverage self-play with MINT to optimize the AI agent’s elicitation strategies and queries. More precisely, MINT builds a symbolic tree by making propositions of possible human-AI interactions and by consulting a neural planning policy to estimate the uncertainty in planning outcomes caused by remaining knowledge gaps. Finally, we leverage LLM to search and summarize MINT’s reasoning process and curate a set of queries to optimally elicit human inputs for best planning performance. By considering a family of extended Markov decision processes with knowledge gaps, we analyze the return guarantee for a given MINT with active human elicitation. Our evaluation on three benchmarks involving unseen/unknown objects of increasing realism shows that MINT-based planning attains near-expert returns by issuing a limited number of questions per task while achieving significantly improved rewards and success rates.

When an AI agent works with a person on a task, such as guiding a rescue drone, navigating a warehouse, or playing a game together, it often runs into things it has never seen and cannot interpret on its own: an unfamiliar object, a smoky corridor, an unclear goal. Today's AI either guesses (and sometimes fails spectacularly) or asks the person too many questions, wasting their time. We built MINT, a system that helps an AI figure out which question is worth asking. Before opening its mouth, MINT silently sketches a small decision tree of everything the unknown object could be, and uses a learned planner to estimate how each possibility would change its choice of action. It then asks the LLM to turn that tree into a single yes/no question whose answer most narrows down the uncertainty that actually matters for the decision. Across three test environments, including a simulated drone rescue scene with fire and smoke, MINT reaches near-expert performance after only one to three questions per unknown object, far outperforming both pure language-model planners and pure reinforcement-learning agents. We also prove a mathematical guarantee: the fewer possibilities remain after the questions, the closer the AI's plan is to the best plan a fully-informed agent could make. The result is AI teammates that ask better questions and bother people less, a step toward collaboration that respects human time and attention.