Having a robot be aware of it's position in a maze

Discussion specific to NXT-G, NXC, NBC, RobotC, Lejos, and more.
skelly89
Posts: 10
Joined: 13 Oct 2010, 21:41

Having a robot be aware of it's position in a maze

Post by skelly89 »

Hello,
I am currently building a robot that can solve a maze. So far my robot can successfully navigate the maze, but I am having issues with letting the robot know where it is currently positioned in the maze, and being able to check if the position it wants to move to has already been explored (this eliminates the robot from doing things like going down a dead end it has already explored). However I'm getting a myriad of compiler errors and I'm assuming my syntax is horribly wrong or I'm approaching the problem the wrong way.

Here is the relevant code:

Code: Select all

enum Direction {
     North = 0,
     West = 1,
     South = 2,
     East = 3
     };

int MyPosX = 0, MyPosY = 0; //starting position at (0,0)

//Finds which direction is to the left and right of current direction
#define LeftOf(Dir) (Direction)( (Dir+1)/4)
#define RightOf(Dir) (Dir == North ? East : (Direction)(Dir-1))

//converts directions into their relative position in the Map array
#define RelPosX(Dir) (Dir == West ? -1 : (Dir == East ? 1 : 0))
#define RelPosY(Dir) (Dir == North? 1 : (Dir == South ? -1 : 0))

//decrease the value of array position by 1 to indicate one less new path
#define DecreaseOne(Var) { Var -= 1; Var = ((Var) < 1 ? 1 : (Var); }

//Definition of Map array values"
//     0 - haven't visited this position
//     1 - been here, no unvisited paths are available
//     2, 3 - there are more ways to go from here
int Map[5][4];
bool Paths[3]; //checks which direction is available - (0=left, 1=front, 2=right)

void chooseDirections()
{
 Direction myDir = North;
 
 if(Paths[0])
 {
    //have we visited this position to our right?
    if(Map[MyPosX+RelPosX(RightOf(MyDir))][MyPosY+RelPosY(RightOf(MyDir))] == 0)
    {
         //No, we have not. Visit that space now.
         //Movement code goes here
    }
    else //Yes, we have already visited that path
    {
         DecreaseOne(Map[MyPosX][MyPosY]);
         DecreaseOne(Map[MyPosX+RelPosX(RightOf(MyDir))][MyPosY+RelPosY(RightOf(MyDir))]);
    }
 }
 else if(Paths[1])
 {
      //same code goes here to check if forward path is unvisited
 }
 else if(Paths[2])
 {
      //same code goes here to check if left path is unvisited
 }
 else
 {
     //code goes here to turn the robot around - we have reached a dead end
 }
}

task main()
{
   chooseDirection();
}
Obviously a lot of the irrelevant code (such as movement or checking which paths even exist) is missing - if anybody wants me to post the entire source I am more than happy to.

and here is the compiler errors I am receiving:
Image
(I apologize for the screenshot, I couldn't figure out how to copy/paste the compiler errors)

Much of this code is based heavily from Building Robots with Lego Mindstorms NXT by Dave Astolfo, Mario Ferrari and Giulio Ferrari, although the language they use is RobotC, not NXC. This book is fantastic and I can't recommend it enough.

I'm assuming I'm doing something wrong with my Directions enumerator or the #define macros I'm using. I've never really used either of these in any fashion before - am I just doing a bonehead error? As far as I can tell the logic behind looking at the correct array element is correct and what's going wrong is how I'm attempting to do it, as evidenced by the huge amount of compiler errors. Any help is greatly appreciated.
hassenplug
Posts: 346
Joined: 27 Sep 2010, 03:05
Contact:

Re: Having a robot be aware of it's position in a maze

Post by hassenplug »

You're right, NXC does not support enums, so the enum Direction is a problem.

I think changing:
enum Direction {
North = 0,
West = 1,
South = 2,
East = 3
};

to:
North = 0;
West = 1;
South = 2;
East = 3;

and
Direction myDir = North;
to
int myDir = North;

should go a long way towards solving your problem.

Steve
---> Link to lots of MINDSTORMS stuff under my picture --->
afanofosc
Site Admin
Posts: 1256
Joined: 26 Sep 2010, 19:36
Location: Nashville, TN
Contact:

Re: Having a robot be aware of it's position in a maze

Post by afanofosc »

There were a number of typo bugs in your code. Here's a version that compiles with the latest version of the compiler. NXC does not support casting expressions so the (Direction) bits in your macros had to go. Recent versions of NXC do support enums but without enforcing type safety so no casting is required. You named your function chooseDirections but referred to it in task main without the "s" at the end so I renamed it. You had unmatched parenthesis in your DecreaseOne macro so I added the missing close paren before the semicolon near the end of the macro. You declared a variable as myDir and then referred to it in a number of places as MyDir.

hth,

John Hansen

Code: Select all

enum Direction {
     North = 0,
     West = 1,
     South = 2,
     East = 3
     };

int MyPosX = 0, MyPosY = 0; //starting position at (0,0)

//Finds which direction is to the left and right of current direction
#define LeftOf(Dir) ((Dir+1)/4)
#define RightOf(Dir) (Dir == North ? East : (Dir-1))

//converts directions into their relative position in the Map array
#define RelPosX(Dir) (Dir == West ? -1 : (Dir == East ? 1 : 0))
#define RelPosY(Dir) (Dir == North? 1 : (Dir == South ? -1 : 0))

//decrease the value of array position by 1 to indicate one less new path
#define DecreaseOne(Var) { Var -= 1; Var = ((Var) < 1 ? 1 : (Var)); }

//Definition of Map array values"
//     0 - haven't visited this position
//     1 - been here, no unvisited paths are available
//     2, 3 - there are more ways to go from here
int Map[5][4];
bool Paths[3]; //checks which direction is available - (0=left, 1=front, 2=right)

void chooseDirection()
{
Direction myDir = North;

if(Paths[0])
{
    //have we visited this position to our right?
    if(Map[MyPosX+RelPosX(RightOf(myDir))][MyPosY+RelPosY(RightOf(myDir))] == 0)
    {
         //No, we have not. Visit that space now.
         //Movement code goes here
    }
    else //Yes, we have already visited that path
    {
         DecreaseOne(Map[MyPosX][MyPosY]);
         DecreaseOne(Map[MyPosX+RelPosX(RightOf(myDir))][MyPosY+RelPosY(RightOf(myDir))]);
    }
}
else if(Paths[1])
{
      //same code goes here to check if forward path is unvisited
}
else if(Paths[2])
{
      //same code goes here to check if left path is unvisited
}
else
{
     //code goes here to turn the robot around - we have reached a dead end
}
}

task main()
{
   chooseDirection();
}
Multi-platform LEGO MINDSTORMS programming
http://bricxcc.sourceforge.net/
skelly89
Posts: 10
Joined: 13 Oct 2010, 21:41

Re: Having a robot be aware of it's position in a maze

Post by skelly89 »

Thank you very much for the help john. I was a bit preemptive in writing this post, I was not on my home computer at the time and had to retype the code from memory on my laptop. I should have taken a bit more time to clean it up before I posted which would have taken care of the typos and such. You were correct I was needlessly typecasting the macro which was causing the errors I was experiencing. Thank you again for pointing me in the right direction, it is much appreciated.
skelly89
Posts: 10
Joined: 13 Oct 2010, 21:41

Re: Having a robot be aware of it's position in a maze

Post by skelly89 »

Hello,
I'm having a lot of fun (and it's a fantastic learning experience) working on this project, but now I'm running into another issue that I believe stems from me not fully understanding the characteristics of now NXC works. My code works fine until my robot reaches a dead end and then all hell breaks loose. My robot can correctly identify which direction (north, south, east, west) is to the left and right of it at it's current point, and from that information can determine which junction node it will visit next. This works without issue until my robot reaches a dead end. When I have it reach a dead end, I turn the robot around, change it's direction to the opposite direction it started it, and then send it forward. However, when I do this and it reaches the next node again, it thinks it is at a 'dead end' again and changes it's direction to the opposite instead of to it's left or right (I hope that made sense). For example, if the robot was heading south towards (5,2), after it reaches (5,2) and determines it is in fact a dead end, it turns around 180 degrees and changes it's direction to North. After it reaches (5,3) and determines that it can turn left which would send it East, it instead changes it's direction to South again but still follows the East line, so when it in fact reaches (4,3) it believes it reaches (5,2) again. I'm at a total loss as to why it is continuously executing that bit of code when it should ignore it unless in special cases.

Here is the algorithm:

Code: Select all

task SolveMaze()
{
     while(!foundExit)
     {
          findEdges();

          Map[MyPosX][MyPosY] = (right+up+left);
          nextMove = -1;

          if(right == 1)
          {
               //have we visited this position to our right?
               if(Map[MyPosX+RelPosX(RightOf(myDir))][MyPosY+RelPosY(RightOf(myDir))] == 0)
               {
                    //No, we have not. Visit that space now.
                    nextMove = 0;
               }
               else //Yes, we have already visited that path
               {
                    DecreaseOne(Map[MyPosX][MyPosY]);
                    DecreaseOne(Map[MyPosX+RelPosX(RightOf(myDir))][MyPosY+RelPosY(RightOf(myDir))]);
               }
          }
          else if(up == 1)
          {
               //have we visited this position in front of us?
               if(Map[MyPosX+RelPosX(myDir)][MyPosY+RelPosY(myDir)] == 0)
               {
                    //No, we have not. Visit that space now.
                    nextMove = 1;
               }
               else //Yes, we have already visited that path
               {
                    DecreaseOne(Map[MyPosX][MyPosY]);
                    DecreaseOne(Map[MyPosX+RelPosX(myDir)][MyPosY+RelPosY(myDir)]);
               }
          }
          else if(left == 1)
          {
               //have we visited this position to our left?
               if(Map[MyPosX+RelPosX(LeftOf(myDir))][MyPosY+RelPosY(LeftOf(myDir))] == 0)
               {
                    //No, we have not. Visit that space now.
                    nextMove = 2;
               }
               else //Yes, we have already visited that path
               {
                    DecreaseOne(Map[MyPosX][MyPosY]);
                    DecreaseOne(Map[MyPosX+RelPosX(LeftOf(myDir))][MyPosY+RelPosY(LeftOf(myDir))]);
               }
          }
          up = 0; left = 0; right = 0;

          switch(nextMove)
          {
               case 0: //go right
                    myDir=RightOf(myDir);
                    rotateRight();
                    break;
               case 2: //go left
                    myDir=LeftOf(myDir);
                    rotateLeft();
                    break;
          }

          if(nextMove != -1)
          {
               moveForward();
               MyPath[pathCounter++] = nextMove;
               MyPosX += RelPosX(myDir);
               MyPosY += RelPosY(myDir);
               continue;
          }
          //If we got here, either we are in a dead end or an intersection
          //where we have visited all possible directions. We now need to backtrack
          else
          {
               rotate180();
               myDir = RightOf(myDir);
               myDir = RightOf(myDir); // doing this twice turns the robot direction around
               moveForward();
               MyPosX += RelPosX(myDir);
               MyPosY += RelPosY(myDir);
               continue;
          }
     }
}
the subroutine moveForward() moves the robot along the line until it reaches the next junction node, and the subroutine findEdges() looks around the junction node and checks if the robot is able to move up, left, and right from it's current position.

from my understanding of loop logic the only time the line "rotate180();" and beyond should only be executed when nextMove == -1 (which means we did not find any other direction to probe). Why does it keep executing it every single time after the first time? After doing some tests, it seems like after the robot turns around, the other if logic statements inside the while(!foundExit) loop do not execute, so the nextMove value never changes, even though findEdges() correctly found that there is a path to take. This is not the problem in any other instance though.

also, as I mentioned in a previous post,I am basing this code on an example from the book "Building Robots with Lego Mindstorms", and their example deals with backtracking in a different (and I'm sure better) manner, however when I try it with my robot it fails miserably. Here is the code I wrote based on the book example:

Code: Select all

          rotate180;
          myDir = RightOf(myDir);
          myDir = RightOf(myDir); // doing this twice turns the robot around
          MyPosX += RelPosX(myDir);
          MyPosY += RelPosY(myDir);
          moveForward();
          findEdges();
          while((Map[MyPosX][MyPosY] < 2) && (pathCounter-- > 0))
          {
               switch(MyPath[pathCounter])
               {
                    case 0: // go back left
                         myDir = LeftOf(myDir);
                         rotateLeft();
                         break;
                    case 2: //go back right
                         myDir = RightOf(myDir);
                         rotateRight();
                         break;
               }
               moveForward();
               findEdges();
               MyPosX += RelPosX(myDir);
               MyPosY += RelPosY(myDir);
     }
However, I'm having the same issues with this code example as well.

Any help or nudge in the right direction is much obliged. And I would like to say that I really appreciate the help I have had from this forum. This website is a fantastic resource and I really appreciate all the help and warm words people have on this board. It is nice to be part of a community that has so many knowledgeable experts that are more than willing to take the time to help people.
hassenplug
Posts: 346
Joined: 27 Sep 2010, 03:05
Contact:

Re: Having a robot be aware of it's position in a maze

Post by hassenplug »

Without totally digging into your code, it looks like it would also turn 180 if it THINKS all paths have been visited. No, wait... It's not checking ALL paths every time.

If the robot can go right (there is a path to the right) and it has already seen that path, it will NOT look at the "up" or "Left" paths. It will turn around and backtrack.

You need to make sure all paths have been checked, before you turn around.

You also may want to verify that your "//have we visited this position..." statement is correct.

Hope that helps.
Steve
---> Link to lots of MINDSTORMS stuff under my picture --->
skelly89
Posts: 10
Joined: 13 Oct 2010, 21:41

Re: Having a robot be aware of it's position in a maze

Post by skelly89 »

Well thanks to all the great help and advice I have recieved from this forum I have completed this project and couldn't be happier. The example I have here is pretty small (a 5x4 maze) but the Mindstorms memory could potentially handle something as big as 20x20. This robot has position detection, orientation direction, and whenever it hits a dead end or a place that it has visited all possible directions it backtracks until it gets to a new unexplored path. I had a huge amount of fun building this and programming it and I can't thank this forum enough for the help!

here is a link to the video : http://www.youtube.com/watch?v=XMEnopw9Pto
HaWe
Posts: 2500
Joined: 04 Nov 2014, 19:00

Re: Having a robot be aware of it's position in a maze

Post by HaWe »

but the Mindstorms memory could potentially handle something as big as 20x20.
my maze solver (working with an astar) solves 45x45 mazes - maybe even more.
skelly89
Posts: 10
Joined: 13 Oct 2010, 21:41

Re: Having a robot be aware of it's position in a maze

Post by skelly89 »

Really? I had a book that claimed 20x20 is the max but I never actually checked. Good to know! I would love to have a maze that large and watch the robot behavior but unfortunately it would take forever to contruct a maze that large.
HaWe
Posts: 2500
Joined: 04 Nov 2014, 19:00

Re: Having a robot be aware of it's position in a maze

Post by HaWe »

you can construct any labyrinth drawing lines in that 45x45 square which represent the walls in it.
If your robot doesn't know anything about it: let him explore the labyrinth just going around.
If you want him to walk an estimated path from a defined start to a defined destination: Use a bug or bug2 algorithm, move and react according to events (walls and paths detected in real-time while moving)
If the robot knows the labyrinth structure completely : use an astar and move just like with a navigation system (TomTom Navigator, for example), follow the routing instructions.

Track all your robot moves by odometry and/or compass readings, maybe you have some beacons to bear additionally.

My astar [1] only shows how the shortest path can be calculated when knowing the complete maze structure. For this purpose you'll need much more variable space (approx. 3 times as much) than just for mapping the maze. So just for a maze mapping you may increase the size to probably sqrt(45*45*3)=about 75x75.

If we had dynamic memory allocation we could use pointers and dynamic lists for the astar, which might be released when the path once will have been calculated, but unfortunately NXC hasn't got that feature. So we currently have to waste precious memory for an intermediate astar :cry:
Post Reply

Who is online

Users browsing this forum: No registered users and 10 guests