I decided to add a little directional bias in the algorithm. By giving the robot an orientation, I was able to favour paths ahead of the robot when faced with choices where other directions have the same distance to the destination.
It changed the path travelled while mapping only a little - I modified my maze to include multiple pathways, and here is the result:
So at least now the robot has the ability to turn... Which s great really since it actually needs to be able to do that in the actual maze!
Going to give this project a break for a couple of days now, I have a few other things to do - like revision :3
Wednesday, 20 April 2011
Micromouse - Mapping
Yesterday I sat down and wrote the route planning / mapping algorithm for the bot. I've taken away the simulated sensors and bot, and just focused on getting the planning out of the way.
I'm essentially using a flood-fill algorithm based on the sensor data the robot has acquired.
Video of it in action:
While mapping, the maze is continuously updated based on the available routes, with the shortest path prevailing at the end.
Grey walls are the maze walls, and red walls are walls the robot has detected.
Of course, the shortest route isn't always the fastest, so the next step will be analysing the routes and deciding on the fastest... but for that, I need a robot to get some movement data on.
I'm essentially using a flood-fill algorithm based on the sensor data the robot has acquired.
Video of it in action:
While mapping, the maze is continuously updated based on the available routes, with the shortest path prevailing at the end.
Grey walls are the maze walls, and red walls are walls the robot has detected.
Of course, the shortest route isn't always the fastest, so the next step will be analysing the routes and deciding on the fastest... but for that, I need a robot to get some movement data on.
Friday, 15 April 2011
Micromouse
Since next year we'll be working on a micromouse, and it appears to be quite challenging, I decided I'd get an early start on mapping the maze. For this I've decided to create a simple simulation of the maze, a bot, and sensors.
I've used Processing for this, since it's a quick way for me to create a visual representation of the challenge. I've been working on it this week during lunch breaks, and have so far got as far as creating the maze, some simulated sensor values, and a little navigation.
As the bot explores, it marks where it has travelled on the map. According to the rules of micromouse you cannot tell the robot where you are starting, but since the first turn determines your position relative to the maze, it's simple enough to figure out.
To create the visual feedback of the mapping, I've "told" the robot its orientation, otherwise it wouldn't know which cells on my map to mark as visited. This doesn't actually affect the bots mapping, it's just so I can see the progress as it happens really.
I'm not detailing everything just yet, but I'll keep you posted (Seriously.)
I've used Processing for this, since it's a quick way for me to create a visual representation of the challenge. I've been working on it this week during lunch breaks, and have so far got as far as creating the maze, some simulated sensor values, and a little navigation.
As the bot explores, it marks where it has travelled on the map. According to the rules of micromouse you cannot tell the robot where you are starting, but since the first turn determines your position relative to the maze, it's simple enough to figure out.
To create the visual feedback of the mapping, I've "told" the robot its orientation, otherwise it wouldn't know which cells on my map to mark as visited. This doesn't actually affect the bots mapping, it's just so I can see the progress as it happens really.
I'm not detailing everything just yet, but I'll keep you posted (Seriously.)
Subscribe to:
Posts (Atom)