Subject:
|
Re: maze solving algorithm
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Sat, 14 Jun 2003 23:51:14 GMT
|
Viewed:
|
671 times
|
| |
|
|
In lugnet.robotics, Ralph Toepper wrote:
> 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?
Wood would make more sense instead of wasting a ton of legos on the walls
(unless you have a ton of Duplos)
>
> 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?
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 to opperate.
>
> 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.
I addressed this issue also.
>
> 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.
If the robot comes in from the east middle entrance of the maze, and exits at
the top middle, it would not be able to recognise that it was off the map yet.
Maybe an algorithm that looks for consecutive gaps over a 3 "cell" distance
would work better if it doesn't know it reached the edge of the maze.
>
> 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
Sorry, but the above maze is not a labyrinth, it can easily be solved by the
"hand-rule." Also, the above maze doesn't use the exit point of the maze as the
goal, your goal is inside the mazes walls.
>
> 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.
I know how to map the maze to memory....... I'm the one who suggested to Scott
how to do it. What I want to know from him, is how he decided to use my
suggestions(if at all). Because 25 variables out of 32, leaving 7 variables
makes it a bit tight to build a navigation and maze solving algorithm.
>
> Greetings
> Ralph
|
|
Message is in Reply To:
 | | Re: maze solving algorithm
|
| 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 (...) (21 years ago, 14-Jun-03, to lugnet.robotics)
|
8 Messages in This Thread:
 
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
