Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sat, 14 Jun 2003 22:45:52 GMT
|
Viewed:
|
891 times
|
| |
|
|
Thanks for the reply, but this message was meant for Scott Davis regarding the
configuration of his particular robot.
Timothy
Hello Timothy, hello Scott, and hello to all the others
off course, i know. Those thougts i mentioned, are general questions regarding
both the robots hardware, the environment he is operating in, and the mapping
software. They were posed to Scott too.
I posted it, because i want to start the maze robot project for myself. I have
little time, so it would be great, if you could help me with that.
First of all, the robots hardware layout, his mechanical construction, is a
theme for itself, taking lots of days if not even weeks or months.
Next, the environment, he is operating in, is the question. Is it pure LEGO? Or
is it build by a wooden system or something like that?
Scott, can you please give us some information about those items? Book, website,
where you got the robots mechanical design from? Or, if its your own design,
please put some pictures to your homepage, showing us how to construct your
robot? Such, that we can rebuild it? Regardless of the state of your efforts.
Please consider the thougths of my last posting.
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |
+-+-+-+-+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
Above, you see two theoretical 5x5 maze maps. The lower left of the first
(upper) and upper right of the second (lower) share the same cell.
Can you imagine, you need a 9x9 native map to allow the robot, to be placed
anywhere in the maze as the starting point?
If the physical maze, the robot lives in, has border walls with no gaps in it,
it is possible to write a program that recognises the maze mapping has happend.
This condition could finish the mapping algorithm.
After the maze mapping has been finished, it is possible to transform the 9x9
maze into a 5x5 maze and extract the starting point in the 5x5 maze. The
starting point in the 9x9 maze is allways the same, the overlapping cell in the
above picture.
We construct our software carefully and assure, the above option can be added
later. So we define starting point and goal being software constants. Meaning,
they are fixed and we work with a 5x5 maze. Starting point and goal are fixed
within the maze, not defined as outside of it.
Now, and my philosophics comes to its conclusion, it is possible to let the goal
be a gap in the border walls of the maze. As you might imagine, a gap in the
border wall could drive the mapping algorithm cazy. Because it might move him
outside of the 9x9 native map positions. But this could be programmed
explicitly, if it is possible to recognise this situation.
At last, our robot can be placed anywhere in the maze as starting point and the
goal is a gap in the maze border wall.
If the robot runs out of the maze, he simply has to recognise no known wall
distances. This will make him drive back into the maze.
By this way we come to the question, how the distance sensor(s) work, to measure
the distance to the next wall.
Imagine this 5x5 maze (its a labyrinth):
+-+-+-+-+-+
| |
+ +
| |
+ +-+-+-+ +
| | | |
+ + + +
| | | |
+ +-+ + + +
| G|S| |
+-+-+-+-+-+
S = Starting Point
G = Goal
The first thing we need is a distance sensor scaling algorithm, that tells us 0
or 1 or 2 or 3 or 4 cell distance to the next wall.
This could make a special measurement scaling equipment necessary. Make shure,
that you can measure the values 0, 1, 2 ,3 4 without the influence of side
walls. The special measurement scaling equipment consits of an obstacle system,
allowing to focus the above values by adjusting the sensors.
To identify the goal outside the maze, after the robot has moved through a gap
in the border wall, we must recognise endless cell distance. You follow? Means
cell distance greater 4. Pose no objects outside the maze.
Distance sensor fine tuning can be used to center the robot in a cell, according
to the distance to a specific wall. If nessesary.
Next we need a subroutine, to move the robot from one cell to the other. To know
the problems, a maze mapping algorithm will encounter, when he moves the robot
though the maze, we need to write a program trying it.
Let the subroutine be named "moveRobot( direction )".
Imagine a sequence of moveRobot() calls that travel the above maze and drive the
way from the starting point to the target. Simply give the moving direction as
parameter to run.
moveRobot( n );
moveRobot( e );
moveRobot( s );
moveRobot( e );
moveRobot( n );
...
n: north
e: east
s: south
This lower level subroutine must be brought to work at first.
Can you help me?
Dedicated to you, Timothy, i have prepared a special answer on how to map Scotts
maze map to an NQC bit map. Expect it it next weekend.
Greetings
Ralph
|
|
Message has 3 Replies:
 | | Re: maze solving algorithm
|
| (...) Wood would make more sense instead of wasting a ton of legos on the walls (unless you have a ton of Duplos) (...) I gave a last option to Scott that allowed him to use a 5x5 map in the robots memory that only needed a reorientation algorithm (...) (21 years ago, 14-Jun-03, to lugnet.robotics)
| | | Re: maze solving algorithm
|
| For the robot design I used a synchro drive robot. On top of the robot is a distance sensor mounted on a technic turntable. I'll try to gets some pics of it for you. For the maze I used wooden (specifically 1/4" masonite) walls. I made it so that it (...) (21 years ago, 15-Jun-03, to lugnet.robotics)
| | | version of firmware
|
| Where can i see the version (1.5 or 2.0) of the firmware that is loaded into an RCX? thanks, Rich ___...___ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! (URL) (21 years ago, 16-Jun-03, to lugnet.robotics)
|
8 Messages in This Thread:
 
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
Active threads in Robotics
|
|
|
|
|
|
