Abstract
The Water-jug problem is a staple in artificial intelligence and recreational mathematics. While classical methods like Depth-First Search (DFS) and Breadth-First Search (BFS) are commonly used, they are often memory and time-intensive. This paper presents a cognitive approach using the Problem Space Computational Model (PSCM) within the Soar architecture. By implementing human-like heuristics through production rules, we achieved significant efficiency gains, reducing the average solution steps by up to 72% compared to baseline cognitive models.
Introduction
The Water Jug problem involves measuring a specific volume of water using two jugs with different capacities and no intermediate markings. In a typical scenario (e.g., using 5-liter and 3-liter jugs to measure 1 liter), the state space can become surprisingly complex for a computer to navigate blindly.
Classical search algorithms explore this space without "intuition," often revisiting states or making counter-productive moves. Humans, conversely, use heuristics to prune the search space. This study aims to bridge this gap by encoding such heuristics into a cognitive agent using the Soar architecture, moving away from brute-force search toward a more intelligent, rule-based approach.
Methodology: The Soar Architecture and PSCM
The researchers employed the Soar cognitive architecture, which models human problem-solving through the Problem Space Computational Model (PSCM). The agent operates in a continuous cycle of input, state elaboration, operator proposal, decision-making, and action.
Three distinct models were tested to evaluate the impact of cognitive heuristics:
- Baseline Model: A standard agent with 15 basic production rules for filling, emptying, and pouring. It lacks any specific strategy for choosing between valid moves.
- Proposed Method I (Preference Rules): Two additional rules (P16, P17) were added to establish a hierarchy of actions. For instance, the agent is taught to prefer pouring or filling over emptying, mimicking the human logic of not undoing recent progress.
- Proposed Method II (Problem Space Restriction): This method uses a "reject" operator (P18) to aggressively prune the search tree. It blocks transitions that are known to be inefficient for specific goal states, such as pouring water back into a jug that was just emptied.
Results and Discussion
The performance of each method was evaluated over 20 experimental runs. The metric for success was the number of steps required to reach the goal state (1 liter in the 3-liter jug).
The results were striking. The Baseline model averaged 194.75 steps, with high variance due to Soar's random selection among valid operators. Method I (Preferences) reduced this average to 156.35 steps, a 19.7% improvement. However, Method II (Space Restriction) was the most effective, averaging only 53.9 steps—a 72.32% increase in efficiency. In several optimal runs, Method II reached the solution in as few as 5 to 9 steps.
These findings demonstrate that while "preferring" good moves is beneficial, explicitly "rejecting" bad moves is significantly more powerful in narrowing the search space and reducing the impact of random decision-making within the cognitive architecture.
Conclusion and Future Work
By integrating human-like heuristics into the Soar architecture, this research shows that cognitive models can solve logic problems far more efficiently than blind search algorithms. The primary limitation remains the inherent randomness in operator selection when multiple rules match.
Future work will focus on incorporating Soar's chunking mechanism and reinforcement learning. These features would allow the agent to "remember" successful paths from previous runs, eventually enabling it to solve the problem optimally every single time without the high variance observed in these initial experiments.
Summary updated