Title: Implementation of Genetic Algorithms for Path Planning in Grid$-$Based Robot Navigation

Description: This project involves designing and implementing a genetic algorithm to solve the path

planning problem for a robot in a grid map environment. The robot must navigate from a start

position $($S$)$ to a goal position $($G$)$ while avoiding obstacles. Assume that the environment of the

robot is represented by a grid map in which the initial and goal states $($current location and the

destination$)$ are clearly localized on the map. Some cells of the map contain obstacles the robot

cannot traverse them to reach the goal. The robot can move horizontally, vertically or diagonally

from a cell to another neighbor free cell $($the maximum number of reachable neighbor cells with one

transition is $8).$

The following figure illustrates the environment of the robot:Project Objectives:

To understand and apply genetic algorithms in solving path planning problems.

To analyze algorithm performance under varying conditions.

To foster collaboration and teamwork in a technical project setting.

Project Phases:

Problem Formulation: Define initial state, goal state, and successor function for the path

planning problem.

Algorithm Design: Develop a genetic algorithm for path planning. This includes defining

the chromosome structure, fitness function, selection, crossover, and mutation methods.

Implementation: Write Python code for the genetic algorithm in a Jupyter Notebook.

Ensure the code can handle different grid sizes and obstacle densities.

Testing and Analysis:

Test your program on randomly generated test problems on grids of size $100$ and

varying the percentage of obstacles from $10$ to $90$ by steps of $10.$

For each type of problem $($the number of obstacles is fixed$)$ generate $20$ random

problem tests. The total number of runs of your code is $180.$

Analyze and comment your results. Provide for each type of problem the average

time, the worst case, the best case. Draw a figure summarizing all results. Interpret

your results.

Documentation and Presentation: Create a comprehensive Jupyter Notebook with code,

comments, and in$-$line analysis.

Submission Requirements:

Source Code and Documentation: A well$-$commented Jupyter Notebook containing

the implementation and inline analysis.

Technical Report: A comprehensive report detailing the approach, implementation,

results, and analysis of the algorithm performance $($It can be merged with Jupyter

Notebook$)$Project Evaluation Rubric

Problem Formulation $(15\%)$

Clearly defines initial and goal states.

Succinctly explains the successor function and problem constraints.

Accuracy in setting up the path planning challenge.

Algorithm Design $(20\%)$

Creativity and correctness in designing the genetic algorithm.

Appropriateness of the chromosome structure, fitness function, selection, crossover,

and mutation strategies.

Theoretical justification for chosen methods.

Code Implementation $(25\%)$

Code functionality and correctness.

Efficiency and optimization of the algorithm.

Readability and organization of the code.

Adequate comments and documentation within the code.

Testing and Analysis $(20\%)$

Thoroughness in testing $($covering different obstacle densities$).$

Correctness of the execution for all test cases.

Depth and clarity in the analysis of results $($average time, worst$-$case, best$-$case

scenarios$).$

Quality and relevance of visualizations.

Jupyter Notebook Presentation $(10\%)$

Cohesiveness and clarity of the narrative.

Quality of in$-$line comments and analysis.

Visual appeal and readability of the notebook.

Technical Report $(10\%)$

Comprehensiveness in documenting the approach, implementation, and analysis.

Organization and clarity of writing.

Proper citation of sources and adherence to report format.

$($Extra $10\%)$

explore ways to integrate A$*$ search into the GA framework and compare with the

original GA$.$