This Project was made as a requisite for the ICOM5015 course. The following is a description of this project.

Shortest Path Search and Missionary Cannibal Problem

Objectives:

Exercise 3.9: To implement search algorithms for finding the shortest path between two points on a plane with convex polygonal obstacles. Exercise 3.11: To solve the Missionary Cannibal Problem optimally using an appropriate search algorithm.

Tasks:

Exercise 3.9: Shortest Path in a Crowded Environment

State Space and Paths:

Determine the number of states in the state space. Analyze the number of paths to the goal.

Shortest Path Structure:

Explain why the shortest path between polygon vertices consists of straight-line segments. Define a good state space and evaluate its size.

Necessary Functions:

Implement functions for the search problem, including a successor function and heuristic function.

Algorithm Application:

Apply one or more algorithms to solve problems in the domain. Comment on their performance and suitability for the task.

Exercise 3.11: Missionary Cannibal Problem

Problem Formulation:

Formulate the problem precisely and draw a diagram of the complete state space.

Algorithm Implementation:

Implement an appropriate search algorithm to solve the problem optimally. Assess the necessity of checking for repeated states.

Difficulty Analysis:

Explore why people find the puzzle challenging despite its simple state space.

Challenges:

Exercise 3.9:

Devising an efficient heuristic function considering the nature of the problem. Handling obstacles and defining state transitions accurately to ensure optimal pathfinding.

Exercise 3.11:

Balancing the exploration of the state space while ensuring an optimal solution. Dealing with potential complexities arising from the boat's capacity constraints and the numerical balance between missionaries and cannibals.

Video Presentation:

https://www.youtube.com/watch?v=NWyIN0GGA58&ab_channel=wushi