Skip to content

Instantly share code, notes, and snippets.

@Kinjalrk2k

Kinjalrk2k/MSB_optimization.c

Last active September 15, 2018 05:57
Show Gist options
  • Save Kinjalrk2k/5cffaa555c9196ad8b5dc5f301f82004 to your computer and use it in GitHub Desktop.
Save Kinjalrk2k/5cffaa555c9196ad8b5dc5f301f82004 to your computer and use it in GitHub Desktop.
Download ZIP
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
Raw
Maze-Solving-Bot.c
/*
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");
}
Raw
MSB_optimization.c
/***********************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");
}
}
@Kinjalrk2k
Copy link
Author

Kinjalrk2k commented Sep 8, 2018 •
edited
Loading

@Somsubhra1 and @YanDs03
Check this out...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment