Abstract
While most AI planners focus on moving physical objects, this research introduces the Social Flexible Problem Solver (SFPS), a system that achieves goals by strategically altering the mental states of other agents. By modeling "beliefs about beliefs," the system generates complex social strategies ranging from simple cooperation to sophisticated double-bluffs and intentional deceit. Evaluation across various symbolic fable scenarios demonstrates that SFPS can reliably produce plausible social plans by simulating the internal reasoning of other agents.
Introduction
Traditional AI planning typically treats the world as a collection of physical states and the agent as a solitary actor. However, human intelligence is deeply social; we achieve our goals by asking for help, negotiating, or sometimes misleading others. The challenge is that "social planning" requires a Theory of Mind—the ability to represent and reason about what someone else knows, believes, or wants. To do this effectively, an AI must handle nested beliefs (e.g., what Agent A thinks Agent B believes), social operators (actions like "bluffing" that change mental states), and agency (recognizing that other agents have their own goals and will not simply act as extensions of the primary agent's will).
Methods: The SFPS Architecture
The authors extend a pre-existing architecture called FPS (Flexible Problem Solver) into SFPS. The core technical contributions include:
- Representational Extensions: A formal notation for nested mental states, such as
belief(lion, belief(sheep, not(sick(lion)))). This allows the system to represent complex social dynamics, such as a lion who thinks a sheep thinks the lion is healthy. - Embedded Inference: The system runs deductive inference inside the simulated mind of another agent. If the AI knows a rule (e.g., "if you are hungry, you should eat"), it can infer that another agent will likely follow that same logic.
- Social Operators: Defined with "main effects" (intended mental change) and "side effects" (e.g., a listener's new belief about the speaker's honesty).
- Heuristic Search: SFPS uses backward chaining and iterative sampling. Crucially, when planning for other agents, it biases the search toward actions that satisfy those agents' own goals, preventing the AI from assuming others will act against their own interests.
Evaluation and Scenarios
The system was evaluated using eight symbolic "fable" scenarios inspired by Aesop’s Fables. These vignettes involve interactions between characters like a Crow, a Sheep, a Deer, and a Cheetah.
The scenarios were categorized by social complexity:
- Basic Social Interaction: Simple cooperation (e.g., a Crow helping a Deer find food).
- Capitalizing on Misbeliefs: Taking advantage of an agent's existing ignorance.
- Deceiving Other Agents: Actively creating a false belief in another agent.
- Encouraging False Beliefs: Sophisticated "double bluffs" where an agent manipulates what another agent thinks they know.
Results
The authors ran SFPS 50 times on each of the eight scenarios (400 runs total). The system generated "plausible" social plans in 97% of runs. Plans averaged 3.2 operators but were dense with social logic. For instance, in the "Cunning Crow" scenario, the AI successfully generated a double-bluff to initiate a trade the sheep originally would not accept.
Lesion studies revealed that disabling "embedded inference" caused the success rate to plummet to 48%, proving that simply having a model of someone's beliefs is insufficient without the ability to reason with those beliefs. Furthermore, without incorporating other agents' actions, the system could only solve 1 out of the 8 problems, highlighting that social planning is fundamentally about leveraging the agency of others.
Discussion and Conclusion
The core insight of this work is that social planning is driven by embedded reasoning. To trick someone, an agent must simulate their internal logical process to see if a lie will lead to the desired conclusion. By treating communication as a state change—similar to a "move" command in robotics—SFPS effectively navigates social environments.
Despite its success, the model assumes deterministic outcomes where social actions always work. Future work aims to incorporate uncertainty and abductive reasoning, where the agent must infer what someone believes based on their actions, moving toward more realistic and robust social intelligence.
Summary updated