What is the Water Jug Problem in AI? Easy to Understand

Introduction

Love puzzles? Most of us liked them during our childhoods. If you still have that passion for puzzles even when you are older now, the water jug problem is worth checking out. The water jug problem is a classic model puzzle in the field of AI (a market that will reach $407 billion by 2027) that highlights artificial reasoning. While it is pretty well-known, you may have never heard of this problem. Don’t worry! In this article, we will try to explain the water jug problem in AI and how it helps us in our everyday lives. 

Also Read: What is Pandera in Python? Check Examples and How to Use It

History

The water jug problem isn’t just a math riddle; it has made its mark in history and even in pop culture. What seems like a simple problem has actually influenced more than just algorithms and AI. This problem has its roots in the water pouring puzzles from the old days. Elizabeth B. Cowley mentions in his piece ‘Discussions: Note on a Linear Diophantine Equation’ that this puzzle “goes back to medieval times” and points out that it appears in Bachet’s math book from the 17th century.

What is the Water Jug Problem As Regards Artificial Intelligence?

In both artificial intelligence as well as maths, the water jug problem refers to a classic puzzle that aids in gauging a particular water quantity. For this purpose, two water jugs containing different water levels are taken. But what is the problem here? Well, none of the water jugs have any water volume markings. The aim is to figure out a series of steps—like filling, emptying, or pouring between the jugs. By doing these things, we get the exact measurement we want. 

The water jug problem might look easy at first. But it dives into the intricacies of problem-solving in AI. Essentially, this puzzle displays how AI algorithms can explore a bunch of different water level combos in the jugs to reach a solution.

Also Read: What are Small Language Models and how do they work?

How Does the Water Jug Problem Work?

The water jug problem is a complex problem where individuals have to gauge the water amount by utilizing nothing but two jugs of different capacities. Here’s how the problem works: 

• Problem-Solving: The water jug problem is efficient in showing the capabilities of artificial intelligence to go through a number of viable states in order to find a solution.
• State Space Search: You start with both jugs empty and the goal is to fill one jug with the exact amount of water you need.
• Mathematical Outlook: To figure out if you can really solve it, check if the amount you want is a multiple of the greatest common divisor (GCD) of the jug sizes.
• Solution: The solution process involves filling the smaller jug and pouring it into the larger one until you hit your target. If the larger jug fills up, just empty it and keep trying.
• DFS/BFS: A DFS or a BFS approach works well here. While the former offers backtracking facilities that let you try different paths and backtrack when necessary, the latter doesn’t offer anything like that.

Source: vtupulse. 

Also Read: What is Scribble Diffusion? How Does It Turn Doodles and Sketches to AI Images?

Step-By-Step Process of Solving the Water Jug Problem in AI?

Search algorithms in AI are super important for tackling problems like the water jug problem. Basically, such algorithms check out every possible setup, or state, of water levels in the jugs. Each action—like filling, emptying, or pouring—makes the system move from one state to another. By gathering all these states, it is possible to create the state space. For those who don’t know, it is the state space that helps AI find the solution.

Take the following example, for instance. Suppose you’ve got two jugs. The first has a capacity of 10 liters. The second jug has a 7-liter capacity. Your mission is to measure out exactly 6 liters of water:

State Representation and Initial Condition: The problem can be expressed as a pair (x, y). So…x is the volume of water in the first jug, and y shows how much water is in the second one. We begin at the state (0, 0).

Goal Predicate: Our objective is to get to the state (6, y), where y has to be between 0 and 7.

Operators: Let’s set up some operators to move between different states:

• The first jug of 10 liters has to be filled up: (x, y) → (10, y) if x < 10
• Fill the 7-liter jug: (x, y) → (x, 7) if y < 7
• Empty the 10-liter jug: (x, y) → (0, y) if x > 0
• The smaller 7-liter jug has to be emptied: (x, y) → (x, 0) if y > 0
• Empty the smaller jug (x, y) into the larger jug (10, y – (10 – x)) where 0 < (x + y) ≥ 10 and y > 0
• Pour from the 10-liter jug into the 7-liter jug: (x, y) → (x – (7 – y), 7) if 0 < x + y is at least 7 and x > 0
• Pour all from the 7-liter jug into the 10-liter jug: (x, y) → (x + y, 0) if 0 < x + y is 10 or less and y is non-negative
• Pour all from the 10-liter jug into the 7-liter jug: (x, y) → (0, x + y) if 0 < x + y is 7 or less and x is non-negative

Also Read: NLP vs LLM: What are the Chief Differences Between Them?

Using a graph search approach, we can find this solution:

• Start: (0, 0)
• Fill the 10-liter jug: (10, 0)
• Pour from the 10-liter jug to the 7-liter jug: (3, 7)
• Empty the 7-liter jug: (3, 0)
• Pour from the 10-liter jug to the 7-liter jug: (0, 3)
• Fill the 10-liter jug: (10, 3)
• Pour from the 10-liter jug to the 7-liter jug: (6, 7)

In the end, we reach the state (6, 7), which means we’ve successfully measured out exactly 6 liters in the 10-liter jug.

• Depth-First Search

Depth-First Search (DFS) method goes deep along one path, completely exploring it, before returning and selecting another path. It explores all possible next states, before returning in order to explore other states. Nevertheless, going deep in search of solutions with Depth-First Search may lead to missing the shorter solutions if the path explored is not correct. In relation to the water jug problem, a Depth-First Search would begin at (0,0), pour water in the 10-liter jug, take the 7-liter jug, and pour to it from the 10-liter jug and other actions going down the tree fully before coming back. This works as an advantage when the correct path is extended vertically, but other than that, it is likely to deal with lots of useless information in the course of the search without using pruning.

• Pruning Techniques

Pruning is an effective tactic when it comes to optimizing AI search algorithms. It removes unnecessary states that are not useful in achieving the aim. This, in turn, lowers the number of states that need to be examined, thereby making the search more effective. In conditions where BFS and DFS algorithms are employed, pruning provides a means of controlling the state space. Take for instance the water jug problem in which after exploring state (10,0), that state will not be visited again by the algorithm, thus saving time and resources. It is thanks to pruning that in the case of BFS and DFS, more attention is paid to the discovery of new and correct paths rather than spending time exploring the already known paths.  

Also Read: From Idea to App: What is Google Stitch AI? A New Coding Tool to Help Design Apps

• Breadth-First Search

Starting from the initial position, the Breadth-First Search (BFS) strategy examines every viable move before proceeding. It expands one level at a time, making sure to explore all options, which usually aids in finding the shortest route to the solution efficiently. In the water jug problem with a 10-liter jug and a 7-liter jug, for example, BFS considers how to fill, empty, or pour water at every level until reaching the goal (6, 7). This approach is efficient, as it helps minimize the number of steps taken towards arriving at a solution and concentrates on all possible shortest routes first.  

Below is how you can solve the water jug problem using the BFS tactic:

Definition With an Example

The use of the water jug problem is well displayed by Amazon and similar companies that utilize optimization algorithms for efficient delivery route planning. Factors considered include package sizes, vehicle capacity, traffic, and delivery time windows. This helps them minimize time and fuel consumption. It is a complex optimization challenge with multiple constraints and objectives involved. 

Source: cyberw1ng.medium 

Conclusion

The water jug problem in AI involves using two jugs of different sizes to measure water, showcasing various search algorithms and the importance of effective strategies. Different algorithms yield different results due to the idea of state space. Researchers analyze these methods to improve AI in tackling challenges in dynamic settings.

For information on AI, click on the links given below:

• What is knowledge distillation and how does it work?
• What is Dense Layer in Neural Network?
• What is AI Energy Consumption?