One of the easiest ways and an excellent place to start for novices to learn how to build a machine that can solve a problem is with a generic algorithm. Generic algorithms can be used to tackle a variety of issues, including the N-queens problem and maze path finder. To determine if the robot will move forward, backward, right, or left on its own without human intervention, we turn to coding. Coding is a means to instruct machines, or more specifically, robots, to carry out all job independently of human assistance. There is no need for humans to perform work after the code has been written and is functioning correctly.

OUR PROJECT:

The task assigned to us is to program a computer to navigate a maze in order to discover the fastest and easiest path for a robot to follow. For this, we employ a generic algorithm. As the name suggests, generic means that it is based on chromosomes, which we refer to as the building blocks of the next generation, fitness in the next generation, and many other factors. I will go over each of these factors individually.

Main Headings:

The main headings or in my case the functions I use in making this project are given.

1. Baby
2. Path_finder
3. Cross_over
4. Mutation
5. Bubble sort

Baby

Sorry for an inconvenient name this is used instead for chromosome as we already made one same type of algorithm in CP-1. When I am making this project I thought we already made chromosome so now its time for upgradation and we will make baby now hahahaha!. So far so good this function is used for generating chromosomes for a particular Grid (row,colums) some of the examples of chromosomes are given these chromosomes are from different grids.

Baby is: [1, 16, 20, 20, 18, 19, 19, 19, 17, 20]
Baby is: [1, 16, 20, 20, 18, 19, 20] etc
def baby(row: int, colum: int, pop: int):
  babies = []
  for _ in range(pop):
    sublist = []
    sublist.append(1)
  for _ in range(1, colum-1):
    sublist.append(random.randint(1, row))
    sublist.append(row)
    babies.append(sublist)
  return babies

This is nothing but a brief explanation of the chromosomes

Path_Finder:

Finding a route to the goal is the most crucial step in a maze solver’s generic algorithm. There are many in generic algorithm to find a path like row wise row first and colum first same in the case of colum wise. We must instruct the computer on how the robot should move within a particular chromosome.

As an example, consider how I implemented the code such that it finds the route of colum wise for both colum first and row first:

Colum:

In column wise of column first will always go the next column means if the value is (0,0) then it will go to (1,0) then (2,0) then (3,0)and so on until the it reaches the value of column which is next to it. The given diagram will explain it better.

Row First

In column wise of row first will always go to the next row means if the value is (0,0) then it will go to (0,1) then (0,2) and so on until it reaches the max value or the next column value is reached. The given diagram will explain it better.

In path finder we not only determine the path but also the path len() the infesible steps means that the robot crosses the wall or passes through the wall. We have to check it and determine whether the step taken by the robot is allowed or not if not then we will increase the infesible step by one.

def fitness(d: list, Mapm: dict, babies: list, k: int):
    infesi = 0
    for i in range(len(d)-1):
        row, colum = d[i]
        if row == colum == (len(d)):
            break
        if Mapm[d[i]]['E'] == 0 and d[i+1] == (row, colum+1):
            infesi += 1
        elif Mapm[d[i]]['W'] == 0 and d[i+1] == (row, colum-1):
            infesi += 1
        elif Mapm[d[i]]['N'] == 0 and d[i+1] == (row-1, colum):
            infesi += 1
        elif Mapm[d[i]]['S'] == 0 and d[i+1] == (row+1, colum):
            infesi += 1
    return infesi

After finding the turns taken by the robot in the given arena, the path and the infesible steps we have to calculate a general answer of all of this for this we use generic algorithm formula given to us in CP-1 course

We can manipulate the constants wf,wl&wt as we desire according to our conditions. In the project I uses wf =4,wl=wt=2 the reason is that to make the infesible steps to effect the result more than the turns and the length

Cross_Over:

Cross over is, in my opinion, the most crucial function in a generic algorithm. Since following a generation, the outcome will rely on the genes that were crossed across.By some unfortunate cross_over that I use is not that much good it is like a hit-and-miss approach to find the answer. Although I know how to make a cross_over good as much as that my program will never fails to find an answer. In that technique which is in my mind not in the project I will make two chromosome to fight and then do some calculation that obviously I am not discussing it here. The cross-over I utilised is the most straightforward, in which I swap out the newborns with those who are fitter after half the population.

def crossover(babies: list, pop: int, colum: int, row: int, infesible: list):
    if pop % 2 == 0:
        cross_over = int((pop/2)-1)
    else:
        cross_over = int(((pop-1)/2)-1)
    pt = random.randrange(colum)
    for i in range(0, cross_over+1, 2):
        for j in range(int(colum/2)):
            babies[cross_over+i][j] = babies[i][j]
            babies[cross_over+i+1][j] = babies[i+1][j]
        for k in range(pt, colum):
            babies[cross_over+i][k] = babies[i+1][k]
            babies[cross_over+i+1][k] = babies[i][k]
    mutation(babies, pop, row, colum, infesible)
    
    return babies

Mutation:

Just replacing some of the baby indexes with values that are within the bounds of the provided labyrinth is what is meant by mutation. The code is given below

def mutation(babies: list, pop: int, row: int, colum: int, infesible: list):
    for i in range(0, pop):
        index = random.randrange(colum)
        if infesible[i] <= 6: continue
        if index == 0 or index == colum-1: continue
        value = random.randrange(1, row)
        babies[i][index] = value
    return babies

Bubble Sort:

The fitness value is used in Bubble Sort to order the lists, with the fittest individuals rising to the top of the list. I also Sort baby the path and infesible, the turns and all the things as you can see in the given function.

def bublesort(dic: dict, babies: list, path: list, Infesible: list, Turns: list, fitness: list, D_B: list, O_B: list, pop: int):
    fitt = [];babb = [];Di_B = [];Ori_B = [];infesi = [];Path = [];turn = []
    
    soort = [(fitness[i], babies[i], Infesible[i], path[i],Turns[i], D_B[i], O_B[i]) for i in range(pop)]
    soort.sort(reverse=True)
    for fit, bab, infe, pth, tur, D_B, O_B in soort:
        fitt.append(fit)
        babb.append(bab)
        infesi.append(infe)
        Path.append(pth)
        turn.append(tur)
        Di_B.append(D_B)
        Ori_B.append(O_B)
    for i in range (pop):
        dic[tuple(babb[i])] = (infesi[i], Path[i],turn[i], Di_B[i], Ori_B[i], fitt[i])
    return fitt, babb, infesi, Di_B, Ori_B, dic

Results:

After reviewing the program’s results, I conclude that there is need for improvement because this approach with cross over unaltered is not very effective in greater grids. Sometimes it doesn’t offer the solution, such 25x25 or more.

A graph of a solvable grid with infeasibility, fitness, paths, and turns is provided so that you can observe the trend of how the answer is calculated.

The upper all the graphs are plot with the help of python library of matplotlib

ANS OF 20X20 GRID

ANS OF 20X15 GRID

GITHUB LINK OF GIST:

2021_MC_16_CEP.py (github.com)