Lejos NXT Maze Solver

[andreas-lydakis]

Greetings everyone ! I'm currently working on a maze solving robot using the A* algorithm.The robot is supposed to enter an unknown maze and traverse it while mapping using 3 US sensors (front,left,right) and X,Y coordinates for each "block",with blocks being of a specific size.While I think I have the algoritmic part correct,I'm running in some practical problems.
Firstly when the robot turns (I'm using a DifferentialPilot for movement) it sometimes overshoots or undershoots the arc given.I'm guessing it's because of friction so I should be able to correct that.
Secondly and most importantly,because the wheels are not at the center of the robot ( I couldnt find a design that would support the sensor setup) when the robot turns it gets slightly out of where it should be,the center of each block and after some turns and movements it will start hitting walls and getting completely off.Any ideas on how to correct that ?
Thank you in advance for any feedback !

EDIT* for some reason i wrote mind instead of maze,sorry about that

[hassenplug]

I think you'll want to actually use the ultra-sonic distances to adjust how close the robot is to the walls. So, as it's moving, figure out how far it is to each wall, and try to adjust until both distances are equal.

It will be a bit more complex than that, but maybe that will get you started.

Steve

[HaWe]

Actually the Astar solves pathfinding of a *known* environment by passing the complete map and both start and destination coordinates. (But consider that the Astar is quite slow for pathfinding in mazes.)
Pathfinding in *unknown* mazes by passing start and destination coordinates is better by using the bug/bug2 algorithm.
If you are still in mapping-and-exploring mode of an *unknown* maze then I also recommend to follow steve's advice.
You will have to make some more specifications in your program to correct the erroneous odometry values depending on the maze's architecture for undistored maps like, e.g., rectangular or circular walls.
If the walls are completely irregular or if you don't want to implement an intelligent filtering then only odometry combined by gyro and compass navigation will help.

If you are running the Astar in the finally completely explored maze, then you will have to perfectly allign your odometry for navigating and following correctly your astar-calculated path in the maze.

[andreas-lydakis]

Thank you for your answers.To clarify some things,I am working with perfect mazes,meaning that there is only one path from one point to another.They are rectangular and comprised by the blocks of a specific size.Using these blocks as nodes the robot will create the stack as it visits them,build the tree and traverse it at the same time.In every block,the robot will check the available adjacent blocks and chose the best according to the heuristic/cost function.If that implementation does not work,of course I will try your suggestions.Thank you again !

[hassenplug]

In every block,the robot will check the available adjacent blocks and chose the best according to the heuristic/cost function.If that implementation does not work,of course I will try your suggestions.Thank you again !

Given that there is only one solution, there is no need to calculate the movement cost when searching the maze. The cost of movement is fixed.

I don't like giving answers, but here's an approach I used a couple years ago. There's still plenty of work converting from line-following to wall-detection...

http://www.teamhassenplug.org/robots/MaxT/

Steve

[HaWe]

If there's only 1 way - so what is the Astar for? The Astar is made to calculate the shortest way of many possible ones between two given points...

[andreas-lydakis]

I meant that to enter a new specific X,Y coordinates block,from a given point,it can be done in only one way.However when the robot meets a crossroad it needs to decide what is the best next move.That's what I meant by move cost.I know it's probably kinda simple but it's my first attempt so please excuse my lack of experience.I will probably attempt the bug/bug2 algorithm you suggested too.Thank you for all the feedback !

[HaWe]

it's not already clear to me how your program design actually is, but anyway, that's not important. The main thing is that you might see now more clearly :)

If you're curious how an astar works on the NXT for a given (known) environment (NXC plus enhanced firmware) you may propably wish to have a look at this (chessboard-geometry, moves only straight or diagonal): http://www.mindstormsforum.de/viewtopic ... 619#p55745

This code example was set up onto an environment of 3 virtual "rooms" with a definitely not easily an quickly calculatable path because of the size and the architecture of the map (map size=47*47, over all about 2000 nodes - and unfavorable built-in doors and walls between the rooms; each node is designed to be big enough for my robot to drive and spin and turn on it (50*50 cm²))

ps, edit:
I meanwhile replaced the old linked Astar version in that old thread with a recent one

[cpapple123]

http://www.teamhassenplug.org/robots/MaxT/

Steve

I'm quite new to the world of Mindstroms but am quickly realizing I'm in it for life. Anyhow I was watching some of your maze robots videos and see your using two light sensors and what looks to be a US, but the US looks to have lights emitting from it like a color sensor. What is going on here?

[hassenplug]

using two light sensors and what looks to be a US, but the US looks to have lights emitting from it like a color sensor. What is going on here?

Things are not always as they seem. It's a custom sensor in a US sensor case. It's 5-element line sensor.

Steve