Skip to main content

AI Planning Tree Search Algorithm for Missionary And Cannibal Problem in Java

I have been doing AI Planning course and I decided to implement the first basic problem in Java. To implement this, i tried to create the algorithm with right level of abstractions so that it can be applied to any problem in future.

Some take aways in my package structure is that, I have maintained all the generic reusable code in definitions package and problem specific code in monkcannibal package.

To solve the problem, I have implemented State which had successor method, IProblem which defined the problem to solve and IStrategy which defined the strategy to take for state transition. Here I have used two strategies for tree travesal, breadth first search aka, BFS and Depth First Search, aka DFS.

The code is available on github at: https://github.com/biplav/aiplanning

The main file is : com.biplav.aiplanning.problems.monkcanibbal.MissionaryCannibalPlan.java


And the output is:

1:L->3m1cfalseboat R->0m2ctrueboat
2:L->3m2ctrueboat R->0m1cfalseboat
3:L->3m0cfalseboat R->0m3ctrueboat
4:L->3m1ctrueboat R->0m2cfalseboat
5:L->1m1cfalseboat R->2m2ctrueboat
6:L->2m2ctrueboat R->1m1cfalseboat
7:L->0m2cfalseboat R->3m1ctrueboat
8:L->0m3ctrueboat R->3m0cfalseboat
9:L->0m1cfalseboat R->3m2ctrueboat
10:L->1m1ctrueboat R->2m2cfalseboat
11:L->0m0cfalseboat R->3m3ctrueboat
Time consumed is 3
1:L->2m2cfalseboat R->1m1ctrueboat
2:L->3m2ctrueboat R->0m1cfalseboat
3:L->3m0cfalseboat R->0m3ctrueboat
4:L->3m1ctrueboat R->0m2cfalseboat
5:L->1m1cfalseboat R->2m2ctrueboat
6:L->2m2ctrueboat R->1m1cfalseboat
7:L->0m2cfalseboat R->3m1ctrueboat
8:L->0m3ctrueboat R->3m0cfalseboat
9:L->0m1cfalseboat R->3m2ctrueboat
10:L->0m2ctrueboat R->3m1cfalseboat
11:L->0m0cfalseboat R->3m3ctrueboat

Time consumed is 1

Popular posts from this blog

Why India Hasn’t Built Its GPT Moment (Yet)

India has the world’s third-largest startup ecosystem, a thriving developer base, and a mobile-first population larger than the US and Europe combined. Yet, no GPT-4. No DeepMind. No Amazon-style platform. Why? Innovation Isn’t Accidental—It’s Engineered The Zerodha Daily Brief recently asked why India hasn’t built a global product company like Apple. The key argument: India isn’t building for the world. It’s solving for local constraints, scale, and affordability—but global scale requires deep IP, design, and tech differentiation. It’s not just about software, it’s about systems thinking. More importantly, it answers the question: Why do countries innovate? The answer isn’t just genius or ambition—it’s incentives and ecosystems. The U.S. Defense Department, for example, accounted for nearly 70% of federal R&D funding during the Cold War. China has pumped billions into semiconductors and AI with long-term national alignment. These aren’t short-term bets—they are strategic, delibe...
Read more

From Stubborn to Smart: How I Learned to Use AI as a PM

Listen to the article in podcast format on PM-AI Diaries channel on Spotify! Ever since I published "The Death of the Stubborn PM" back in February, my inbox has been buzzing with one big question: “Okay, I get that AI is the future for product managers—but how do I actually use it?” It’s a fair ask. In that piece, I argued that PMs who resist AI are doomed to fade away, like dinosaurs refusing to evolve. As I wrote, “The stubborn PM who clings to old ways will die out, replaced by those who harness AI’s power while leaning into what makes us human.” Now, people want the playbook. So, let’s walk through it with a story—my own journey of figuring this out, backed by some sharp insights from MIT Sloan’s "When Humans and AI Work Best Together—and When Each Is Better Alone" . The Wake-Up Call Picture me a few months back: a PM buried in work, juggling a dozen tasks, and feeling like there weren’t enough hours in the day. Writing user stories, sketching ideas, track...
Read more

8 Product Management lessons from the movie 'Gold'

The movie 'Gold' starring Akshay Kumar, is an inspirational story of how passion, determination and persistence can help one achieve the Impossible. The character of Tapan Das, who was the Team Manager of Indian Hockey Team, is a fine example of an ideal Product Manager . Listing few of the core responsibilities/skillset of an ideal PM with examples from the movie (Spoiler Alert! ): Vision: The foremost responsibility of a PM is to set the vision for the team. During 1936 Olympics in Berlin, Tapan clearly set the vision for Gold medal as free India as a Goal and Vision. Hustle: As a PM, you need to hustle to get things done. Tapan, hustled to meet Mr Wadia to get things done over and over again through out the movie. Stakeholder Management: Aligning different stakeholders to your vision and progress is critical. Tapan did a brilliant job of doing that with Mr Wadia, Imtiaz, Samrat and other members of the team. Be it a royal blood like Raj Pratap Singh or a ...
Read more