Create a Java project which implements the uninformed breadth_first_search algorithm found on page 82 of AIMA (Artificial Intelligence: A Modern Approach 3rd edition by Russell and Norvig), and uses it to solve the Missionaries and Cannibals problem as a first example of a Problem class.

Your project should include the following classes:

Agent -- which includes a breadth_first_search method (page 82 of AIM) and a child_node method (page 79 of AIM),

Problem -- discussed on pages 66 through 68 of AIMA Node -- discussed on pages 78 and 79 of AIMA Sequence -- mentioned on pages 66 and 67 of AIMA QueueFIFO -- discussed on pages 79 and 80 of AIMA

ValidityChecker -- used to make certain that the input is valid

Action -- simple class with a one parameter constructor and a toString method Percept -- simple class with a one parameter constructor and a toString method State -- simple class with a one parameter constructor and a toString method

Each of the first six classes mentioned above (Agent, Problem, Node, Sequence, QueueFIFO, and ValidityChecker) should have a "main" method used for testing the class.

When you implement algorithms from AIMA, use variable names, method names, and code structure that are as close as possible to the names and structures in AIMA.

The first Problem we will solve with this AI technique is the Missionaries and Cannibals Problem.

In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries).

https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

Our encoding scheme is:

Input "M&C#331000#000133" indicates a Missionaries and Cannibals Problem with 331000 as a start state and 000133 as a goal state.

"331000" indicates a State with 3 missionaries and 3 cannibals on the left bank of the river, a boat on the left bank, and 0 missionaries and 0 cannibals on the right bank.

"120121" indicates a State with 1 missionary and 2 cannibals on the left bank of the river, a boat on the right bank, and 2 missionaries and 1 cannibal on the right bank.

"row#10" indicates an Action where 1 missionary and 0 cannibals will move across the river and also the boat will move to the other bank.

If s is a State initialized with "331000" and a is an Action initialized with "row#10", then result(s,a) would return a State initialized with "230110".

Example runs of a completed project will be demonstrated and discussed in class.

============

Note: Using the generalized agent approach developed in AIMA it will be possible to add a single new Problem subclass to the program and solve other problems from different domains. For example, our agent will be able to solve the routeFinding problem by adding a new Problem subclass.