Last active
September 15, 2018 05:57
-
-
Save Kinjalrk2k/5cffaa555c9196ad8b5dc5f301f82004 to your computer and use it in GitHub Desktop.
The Maze Solving Bot algorithms/approach (both Dry run and Actual Run), which in turn to be applied into an Arduino Sketch for the TechnoRion Techfest '18 at IIT Bombay
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Teammates: Kinjal Raykarmakar, Pourab Roy, Sayan and Somsubhra Das | |
Author: Kinjal Raykarmakar | |
Test Cases by: Pourab Roy | |
Filename: main.c | |
Description: The Maze Solving Bot algorithms/approach (both Dry run and Actual Run), | |
which in turn to be applied into an Arduino Sketch for the | |
TechnoRion Techfest '18 at IIT Bombay | |
Gist Link: https://gist.github.com/Kinjalrk2k/5cffaa555c9196ad8b5dc5f301f82004 | |
List of Test Cases tested and verified on: | |
LULLLUSULLUSLL (14) -> https://www.hackster.io/mjrobot/maze-solver-robot-using-artificial-intelligence-4318cf | |
RRLLULULULLSLLRLLLURLRLLLULUSRRLLR (34) -> Pourab Roy | |
SLULLLLULRSULSLLUSSRLRRLLRRLLUL (31) -> IITBombay's Official Meshmerize Instructions PDF | |
*/ | |
#include <stdio.h> | |
#include <stdbool.h> | |
#include <string.h> | |
// enumeration to handle types of intersections | |
enum intersection | |
{ | |
DE, // dead end | |
EOM, // end of maze | |
S_R, // straight or right | |
S_L, // straight or left | |
CR, // cross | |
T, // T-intersection | |
RO, // right only | |
LO, // Left Only | |
CL // line clear | |
}; | |
// enumeration to handle types of moves | |
enum move | |
{ | |
R, // turn right | |
L, // turn lest | |
S, // go straight | |
U, // U-turn | |
ExI, // extra inch | |
ST // stop | |
}; | |
// enumeration to handle types of runs | |
enum state | |
{ | |
DR, // dry run | |
AR // actual run | |
}; | |
char light_sensor[6]; // array to handle of the IR light sensors | |
/***********************TEST CASES***************************/ | |
char ac_path[100]="LULLLUSULLUSLL"; | |
int ac_path_len=14; | |
/***********************************************************/ | |
char opt_path[100]; // save the moves of optimised path | |
int opt_path_len; // optimised path lenght | |
/* Did You Know? opt_path_len<=ac_path_len */ | |
// function to detect the IR sensors and save them to the light_sensor array | |
void detect_sensors(char* light_sensor) | |
{ | |
/*****PROCEED WITH CAUTION: ARDUINO CODE AHEAD*****/ | |
/* | |
light_sensor[0] = digitalRead(lineFollowSensor0); | |
light_sensor[1] = digitalRead(lineFollowSensor1); | |
light_sensor[2] = digitalRead(lineFollowSensor2); | |
light_sensor[3] = digitalRead(lineFollowSensor3); | |
light_sensor[4] = digitalRead(lineFollowSensor4); | |
*/ | |
} | |
// function to move the bot around | |
void move_bot(enum move m) | |
{ | |
/*****PROCEED WITH CAUTION: ARDUINO CODE AHEAD*****/ | |
switch(m) | |
{ | |
case R: | |
// motor driver: turn 90 degrees right | |
break; | |
case L: | |
// motor driver: turn 90 degrees left | |
break; | |
case S: | |
// motor driver: full speed straight | |
break; | |
case U: | |
// motor driver: turn 180 degrees | |
break; | |
case ExI: | |
// motor driver: move a bit forward in the same direction | |
break; | |
case ST: | |
// motor driver: halt | |
break; | |
} | |
} | |
// funtion that make the bot follow the line in case of offset | |
void follow_line(char* light_sensor) | |
{ | |
/*****PROCEED WITH CAUTION: ARDUINO CODE AHEAD*****/ | |
while(light_sensor!="00100") | |
{ | |
if(light_sensor=="00001") | |
{ | |
// move way right | |
} | |
else if(light_sensor=="00011") | |
{ | |
// move way right | |
} | |
else if(light_sensor=="00010") | |
{ | |
// move moderate right | |
} | |
else if(light_sensor=="00110") | |
{ | |
// move bit right | |
} | |
else if(light_sensor=="01100") | |
{ | |
// move bit left | |
} | |
else if(light_sensor=="01000") | |
{ | |
// move moderate left | |
} | |
else if(light_sensor=="11000") | |
{ | |
// move way left | |
} | |
else if(light_sensor=="10000") | |
{ | |
// move way left | |
} | |
} | |
} | |
// function to handle with differnt kinds of intersections | |
enum intersection intersection_handling(char* light_sensor) | |
{ | |
// loop the move stright till straight lineis maintained | |
while(light_sensor=="00100") | |
{ | |
move_bot(S); | |
detect_sensors(light_sensor); | |
} | |
if(light_sensor=="00000") // dead end | |
return DE; | |
else if(light_sensor=="00111") // right or straight | |
{ | |
move_bot(ExI); // move a bit | |
if(light_sensor=="00000") // no line | |
return RO; | |
else if(light_sensor=="00100") // straight line | |
return S_R; | |
} | |
else if(light_sensor=="11100") //left or straight | |
{ | |
move_bot(ExI); // move a bit | |
if(light_sensor=="00000") //no line | |
return LO; | |
else if(light_sensor=="00100") // straight line | |
return S_L; | |
} | |
else if(light_sensor=="11111") // cross or T or End | |
{ | |
move_bot(ExI); | |
{ | |
if(light_sensor=="00000") // no line | |
return T; | |
else if(light_sensor=="11111") // filled | |
return EOM; | |
else if(light_sensor=="00100") // straight line | |
return CR; | |
} | |
} | |
} | |
/**********FOLLOWING: LEFT HAND ALGORITHM/RULE (LHA/LHR)**********/ | |
// function that judges the moves depending upoun the intersection | |
enum move move_handling(enum intersection i) | |
{ | |
/* self-explanatory moves depending upon LHA/RHA */ | |
switch(i) | |
{ | |
case DE: | |
move_bot(U); | |
break; | |
case EOM: | |
move_bot(ST); | |
break; | |
case S_R: | |
move_bot(S); // for RHA: move_bot(R); | |
break; | |
case S_L: | |
move_bot(L); // for RHA: move_bot(S); | |
break; | |
case CR: | |
move_bot(L); // for RHA: move_bot(R); | |
break; | |
case T: | |
move_bot(L); // for RHA: move_bot(R); | |
break; | |
case RO: | |
move_bot(R); | |
break; | |
case LO: | |
move_bot(L); | |
break; | |
case CL: | |
move_bot(S); | |
break; | |
} | |
} | |
// function that checks whether the path is optimisable... meanwhile optimises it | |
bool isoptimizable() | |
{ | |
int j=0, count=0, i=0; | |
for(i=0; i+1<opt_path_len; i++, j++) | |
{ | |
// temp_path is a 3-move path used for optimization | |
char temp_path[4]; | |
if(opt_path[i]=='U') | |
{ | |
temp_path[0]=opt_path[i-1]; | |
temp_path[1]=opt_path[i]; | |
temp_path[2]=opt_path[i+1]; | |
temp_path[3]='\0'; | |
} | |
/*****************REPLACEMENT RULES AHEAD*****************/ | |
if(strcmp(temp_path,"LUR")==0) | |
{ | |
printf("LUR=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"LUS")==0) | |
{ | |
printf("LUS=R | "); | |
opt_path[j]='R'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"RUL")==0) | |
{ | |
printf("RUL=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"SUL")==0) | |
{ | |
printf("SUL=R | "); | |
opt_path[j]='R'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"SUS")==0) | |
{ | |
printf("SUS=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"LUL")==0) | |
{ | |
printf("LUL=S | "); | |
opt_path[j]='S'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else | |
{ | |
opt_path[j]=opt_path[i]; | |
continue; | |
} | |
} | |
return false; | |
} | |
// function that optimises the moves | |
void optimize() | |
{ | |
// initially, copies the actual path to the optimised path | |
for(int i=0; i<ac_path_len; i++) | |
opt_path[i]=ac_path[i]; | |
opt_path_len=ac_path_len; | |
while(isoptimizable()) // this loop iterates till the path is optimizable | |
{ | |
// printing the temporary optimised path | |
for(int i=0; i<opt_path_len; i++) | |
printf("%c ", opt_path[i]); | |
printf("\n"); | |
} | |
} | |
/*****PROCEED WITH CAUTION: ARDUINO CODE AHEAD*****/ | |
// standard Arduino function | |
void loop() | |
{ | |
enum state s; | |
//s=getstate_3wayswitch(); // discuss | |
enum move m=S; // set the initial move to straight | |
enum intersection i; | |
// switch the RUN | |
switch(s) | |
{ | |
case DR: | |
{ | |
move_bot(S); // initially move the bot straight | |
while(m!=ST) | |
{ | |
detect_sensors(light_sensor); // detect the IR sensors and update light_sensors array | |
follow_line(light_sensor); // follow the line if in offset | |
i=intersection_handling(light_sensor); // understand the intersection(if any) | |
m=move_handling(i); // move as per the intersection | |
} | |
break; | |
} | |
case AR: | |
{ | |
// still figuring... | |
break; | |
} | |
} | |
} | |
// standard C main function without any command line arguments | |
int main() | |
{ | |
// print Dry Run Path | |
printf("Dry Run Path: "); | |
for(int i=0; i<ac_path_len; i++) | |
printf("%c ", ac_path[i]); | |
printf("\n\n"); | |
// Optimise the path | |
optimize(); | |
// print the Optimised Run Path | |
printf("\nOptimised Path: "); | |
for(int i=0; i<opt_path_len; i++) | |
{ | |
printf("%c ", opt_path[i]); | |
} | |
printf("\n"); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/***********************TEST CASES***************************/ | |
char ac_path[100]="LULLLUSULLUSLL"; | |
int ac_path_len=14; | |
/***********************************************************/ | |
char opt_path[100]; // save the moves of optimised path | |
int opt_path_len; // optimised path lenght | |
/* Did You Know? opt_path_len<=ac_path_len */ | |
// function that checks whether the path is optimisable... meanwhile optimises it | |
bool isoptimizable() | |
{ | |
int j=0, count=0, i=0; | |
for(i=0; i+1<opt_path_len; i++, j++) | |
{ | |
// temp_path is a 3-move path used for optimization | |
char temp_path[4]; | |
if(opt_path[i]=='U') | |
{ | |
temp_path[0]=opt_path[i-1]; | |
temp_path[1]=opt_path[i]; | |
temp_path[2]=opt_path[i+1]; | |
temp_path[3]='\0'; | |
} | |
/*****************REPLACEMENT RULES AHEAD*****************/ | |
if(strcmp(temp_path,"LUR")==0) | |
{ | |
printf("LUR=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"LUS")==0) | |
{ | |
printf("LUS=R | "); | |
opt_path[j]='R'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"RUL")==0) | |
{ | |
printf("RUL=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"SUL")==0) | |
{ | |
printf("SUL=R | "); | |
opt_path[j]='R'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"SUS")==0) | |
{ | |
printf("SUS=U | "); | |
opt_path[j]='U'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else if(strcmp(temp_path,"LUL")==0) | |
{ | |
printf("LUL=S | "); | |
opt_path[j]='S'; // optimised move | |
// one optimisation at a time, copying the rest of the moves | |
for(int l=j+1, m=i+3; m<opt_path_len; l++, m++) | |
opt_path[l]=opt_path[m]; | |
opt_path_len-=2; | |
return true; // optimizable | |
} | |
else | |
{ | |
opt_path[j]=opt_path[i]; | |
continue; | |
} | |
} | |
return false; | |
} | |
// function that optimises the moves | |
void optimize() | |
{ | |
// initially, copies the actual path to the optimised path | |
for(int i=0; i<ac_path_len; i++) | |
opt_path[i]=ac_path[i]; | |
opt_path_len=ac_path_len; | |
while(isoptimizable()) // this loop iterates till the path is optimizable | |
{ | |
// printing the temporary optimised path | |
for(int i=0; i<opt_path_len; i++) | |
printf("%c ", opt_path[i]); | |
printf("\n"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@Somsubhra1 and @YanDs03
Check this out...