Collaborative Problem-Solving in an Optimization Game
This addresses the challenge of human-AI collaboration in complex problem-solving for users in optimization domains, though it is incremental as it builds on existing dialogue and LLM methods.
The paper tackles the problem of enabling dialogue agents to collaboratively solve NP-hard optimization tasks, specifically a two-player Traveling Salesman problem, by introducing a novel game and an agent combining LLM prompting with symbolic mechanisms, achieving optimal solutions in 45% of games in self-play and showing successful collaboration with humans and generalization to new graphs.
Dialogue agents that support human users in solving complex tasks have received much attention recently. Many such tasks are NP-hard optimization problems that require careful collaborative exploration of the solution space. We introduce a novel dialogue game in which the agents collaboratively solve a two-player Traveling Salesman problem, along with an agent that combines LLM prompting with symbolic mechanisms for state tracking and grounding. Our best agent solves 45% of games optimally in self-play. It also demonstrates an ability to collaborate successfully with human users and generalize to unfamiliar graphs.