How to build a Maze Robot

by Mike Linnen 15. December 2007 12:48

Overview

The following article was originally posted by me on the Phoenix Area Robotics eXperimenters web site.  I moved the article here on my blog as I no longer belong to the Robotics group.  You can find the original article on the PAReX site.

Building a Maze Robot

My maze robot DR X took first place in BotBash’s 2000 Autonomous Maze competition. The competition consisted of three mazes with different configurations. The robot that completed all three mazes in the shortest time wins the event. Each robot had five chances to complete all three mazes. The shortest three times where summed up for the final score. DR X was the only robot able to complete all three mazes in the allotted time frame. This article was written as an attempt to explain the techniques used to allow DR X to accomplish first place.

There are several techniques that can be used in solving mazes:

  • Random
  • Wall Following
  • Mapping

Random navigation does not seem like a very elegant way to master a maze so my choices were mapping or wall following algorithms. Mapping a maze can be very difficult to do and this competition did not really reward such a task. So that leaves wall following as the best bet to complete the maze.

Wall following can be best explained by imagining yourself in a maze with your eyes closed. If you could place one hand on a wall and never let the hand leave the wall you will eventually find the end of the maze as long as the finish is not an island in the middle of the maze. It is very important to follow only one wall until you reach the end.

The following drawings show right and left wall following paths for a given maze.

wallfollow

Notice that in some cases it is better to choose one wall to follow over another. Here the shortest path from start (S) to finish (F) is via the right wall. So it is good practice to be able to command your robot to follow one wall over another before it is set in the start box. This can be accomplished by using the left and right bumper switches. Tapping the left or right switch before the start commands the robot to follow the left or right wall.

So I set out to build and program a maze robot to follow one wall. I choose to use a differential drive system on a round body. This would allow me to control the robot rather easily and prevent it from getting hung up on maze walls. I mounted two GP2D02 IR Sensors on a single shaft on top of a servomotor. The sensors were positioned 90 degrees apart. The servomotor allowed the robot to look straight ahead and the left or right wall at the same time.

DR X First Prototype

drxPrototype

In order to tell if the robot was getting closer or further away from a wall a minimum of two sensor readings would have to be taken over a period of time while the robot was moving. I had some difficulty in fine-tuning the reactions needed to prevent the robot from touching the walls. I quickly realized that this sensor arrangement had some shortcomings. I needed to be able to look at a wall and determine if the robot was parallel to it without moving forward. If I could achieve this, the robot would always start off parallel to a given wall. So I made some sensor placement changes that would not require the robot to be moving in order to determine if it was parallel or not.

DR X Second Prototype

drxPrototype2

I found out some other advantages of this sensor arrangement. While the robot was following a wall and it approached a doorway of the maze the first sensor would detect the opening (doorway) very easily. Once the second sensor detected the doorway I knew the robot was directly in front of the entranceway. A 90 degree turn towards the entranceway would position the robot perfectly for passage through the door. Passage through the door would also be easily detected. As the robot moved forward, the door jam could be detected by both sensors. The robot could successfully determine when a door was found and navigate through the door rather easily.

The following drawings show the robot navigating through a doorway.

The robot approaches the doorway

door1

The robot passes the doorway

door2

The robot turns left 90 degrees

door3

The robot moves forward into the doorway

door4

The robot is almost through the doorway.

door5

The robot is through the doorway.

door6

DR X Front View

drx_front

DR X Side View

drx_side

Improvements

Well this solution certainly has room for improvement and it is not the only way to solve a maze. One major enhancement that I saw was DR X needed a sensor that could look in front of the robot while it was attempting to follow a wall. This would have prevented the robot from having to collide with a wall before it realized it needed to stop and turn.

Conclusions

Well this project sure was a gratifying experience. To watch my little creation navigate the maze was a great thrill. A lot of last minute hard work went into this robot but come event day it all paid off.

Getting Tags to work in Windows Live Writer with BlogEngine.NET

by Mike Linnen 15. December 2007 11:16
There is a great post (http://nyveldt.com/blog/post/Windows-Live-Writer-Customization-for-BlogEngineNET.aspx) by Al Nyveldt on getting the two to play nicely together.

Moving to another blog software solution

by Mike Linnen 15. December 2007 08:07

Well I have really neglected my blog over the last 1.5 years!  I originally decided to write my own blog software just because I could.  Well the fact that I became very busy the first thing to be neglected was this blog.  So I decided to final start changing that by moving to a blog solution with more features than I had but also allow for me to customize it when I wanted to.  In addition to what my current solution already had I wanted the following:

  • Track back
  • External API for using Windows Live Writer or some other thick client blog authoring software.
  • The ability to insert pictures or files right into the post
  • The ability to apply themes
  • Open source
  • Extensibility

So I choose BlogEngine.NET because it had all the current features my solution already had (which wasn't a big list) and many more.

Tags:

Ashley takes 1st Place at Tournament

by Mike Linnen 12. March 2007 07:23
Ashley takes 1st Place at Tournament

Well we had another great weekend with fencing. This time it was Ashley stepping up to the strip and taking first place at the Mid Atlantic RYC Y10 Women’s Saber. This is an awesome achievement for Ashley. This fencing tournament qualifies Ashley for the 2007 Fencing Nationals in Miami this year.

We went to the University of North Carolina in Greensboro for this event on Saturday March 3rd and it was Ashley’s first tournament outside of the KOS home events. Was she nervous? She sure did not look like it!

Just to refresh your memories on how one of these tournaments works. Fencers are placed in groups called pools. Depending on the number of fencers there could be 1 or many pools. In the case of this tournament there were 3 fencers so only 1 pool was formed. The object of the pool is to get as many wins and points as possible. When the pool is complete the points are totaled up and the fencers are ranked. Based on the ranking results the fencers are paired up to compete in a direct elimination tournament. In direct elimination the winners advance to the next round and the losers go home.

Ashley ended up fencing two other fencers in this pool. She won 1 and lost 1 and the end result of the pool she ended up ranking 2nd out of 3 fencers This created an elimination tournament where the #1 ranked fencer would get a bye for the first round and Ashley would have to fence the #3 rank in round 1 Take a look at the elimination bracket shown below to get a visual idea of what I am talking about.

RYC 2007 DE Bracket

In direct elimination each round consists of the best 2 out of 3 matches of 5 points each. This means the fencers fence up to 3 matches of 5 points each. The first fencer to reach 2 wins advances to the next round.

Ashley won the first two matches in round 1 against Ross with a total score of 10 to 4. This meant Ashley was moving up to the finals against Margaret. Ashley started off a little slow in the first match against Margaret and she ended up loosing the match 5 to 3. Shawn quickly came to Ashley’s side and started coaching her for the next match. Ashley started off slow again but she came from behind to win the 2nd match 5 to 4. This was very exciting to see Ashley come from behind and win the match to tie up the series. The final 3rd match was going to need to be played to determine the 1st place winner. During the final Match Ashley did not start off slow at all and she took the win 5 to 1. We were so excited that Ashley displayed so much courage to come from behind in a difficult match and win 1st place!!

In the picture below Ashley is on the right side and Margaret is on the left. As you can see in the picture both fencers are lunging for an attack but Ashley had right away in this case and she ended up with the point Ashley is showing great form in this picture with her front foot pointed forward and her left arm stretched back to give her great balance in her lunge.

Ashley Fencing at RYC 2007

Tags:

Family

BX24 and PowerShell for managing a build process

by Mike Linnen 18. July 2006 21:01
BX24 and PowerShell for managing a build process

I have been doing some BX24 development again lately.  I have also been reading a lot about the new shell support that Microsoft has pre-released called PowerShell (formerly known as Monad).  Well since I have been using the same batch files and VBScript files to manage my build process for BasicX source since 2001 I thought it might be time to look at another alternative. 

I need to be able to do the following:
  • Perform command line compiles of the BX24 project
  • Allow for the source to reside anywhere on the hard drive and still be able to compile.
  • Initiate a compile of all BX24 projects so I do not have to do them one at a time
  • Parse the BasicX.err file to determine if the compiler found errors
  • Launch an editor that shows the BasicX.err file only when an error exists
  • Be able to manage some registry entries specific to the BasicX IDE
  • Have a limited set of scripts that do not require any changes to support the build process
  • Allow for multiple project files to co-exist in the same folder. This means I need to save off the BasicX.err file into another file if I want to preserve what the results where from the compile.

After reading some about PowerShell it was very apparent that it would support anything I needed to do.  The main huddle I needed to over come was learning the syntax that revolved around PowerShell.  Fortunately it is based on the .Net framework so the majority of it was fairly easy to adjust to. 

Since I already had a VBScript file that did most of the above tasks I started dissecting what it did first.  The last time I touched this script was in 2001.  The script did the pieces around changing the registry entries and launching the compiler but it had no support for parsing the error file and managing many project files.  Here is the script that I ended up with:

param ([string]$WorkingDirectory)
# Define some script variables$chip_type="BX24"
# Save the current dirrectory so we can return to it
Push-Location
# If a working directory was passed in lets change to it
If ($WorkingDirectory){Set-Location $WorkingDirectory}
# Get the project files to process
$projectFiles = Get-ChildItem *.bxp 
foreach ($project in $projectFiles){$project_file = $project.name.split(".")[0]
# Use the current directory as the working directory
$work_dir = $project.DirectoryName
# Set some registry entries for the basicx IDE
$configEntry = "hkcu:\software\vb and vba Program Settings\basicx\config"
Set-ItemProperty ($configEntry) -Name Chip_Type -value 
$chip_typeSet-ItemProperty ($configEntry) -Name Work_Dir -value 
$work_dir
# determine from the registry where the basicx executable is installed
$program_dir = Get-ItemProperty ($configEntry) -Name Install_Directory
# Map the P drive to the basicx install directory for convieniance
if (Test-Path p:) {}else {subst P: $program_dir.Install_Directory}
# Remove the error file if it exists
if (Test-Path basicx.err){del basicx.err}
if (Test-Path ($project_file + ".err")){del ($project_file + ".err")}
# Launch the compiler
P:\basicx.exe $project_file /c
# Wait for the compiler to finish
$processToWatch = Get-Process basicx$processToWatch.WaitForExit()
# Unmap P: drive
if (Test-Path p:){subst P: /d}
# Check for errors and launch the error file if some do exist
$CompileResult = get-content basicx.err
If (($CompileResult -match "Error in module").Length -gt 0){notepad basicx.err}
# Copy the error file off so it does not get overwritten when multiple
# projects are being compiled in a single directory
copy-item basicx.err -destination ($project_file + ".err")} 
# Restore the original location
Pop-Location

Well that was pretty painless.  I basically had a script that managed processing all BasicX project files in a given folder.  Next I needed to have another script that found all the project folders for a given folder.  This also meant processing projects in sub folders.  This higher level script would launch the script above to do the compile.  I ended up with the following script:

# Save the current dirrectory so we can return to it
Push-LocationSet-Location ..\
# Get a list of all projects
$project_Files = Get-ChildItem -recurse -include *.bxp | sort $_.DirectoryName$lastDir=""
foreach($project in $project_Files)
{
# Since we can have multiple projects in a folder and we send the
# working folder to the build script we want to skip folders we already
# processed
if ($lastdir -ne $project.DirectoryName)
{./tools/build $project.DirectoryName  $lastDir = $project.DirectoryName}}
Pop-Location

Well that too was pretty easy.  I am beginning to really respect the power of PowerShell.  I can do so much more than what I was able to do with VBScript and do it easier.  Later I will but together a sample BX24 project showing how I use these scripts and the folder structure I place them in.

Using an alternative editor for the BasicX IDE

by Mike Linnen 16. July 2006 16:13
Using an alternative editor for the BasicX IDE

Although the BasicX Integrated Development Environment works for writing, compiling and downloading source code for small quick projects once you start using it a lot for writing source code it tends to be lacking features.  However the folks at Netmedia were nice enough to allow for command line execution of their IDE to compile and download code.  This opens up the opportunity to use your favorite editor to write source code and launch the IDE via command line to compile the source.  I have been using these command line options since 2001 to make my development environment a little more to my liking.  In this blog post I will talk about how I manage the process and the tools I use.

First a couple notes about some things that might trip you up in using the command line options.  The BasicX IDE wants to know the base directory where your projects live.  This is ok if you want to manage this directory in the IDE every time you switch to another folder or if you only have one project.  However if you are like me you have many projects and you don't want to have to load up the IDE to change this base directory every time you work on one of them.  Next the chip setting for BX24 or BX01 is also set from the IDE and is needed for the command line compile.  I bounce back and fourth between projects that use one or the other chip so my IDE could be set for either one at any given time. 

Neither the base directory or the chip setting is offered as an option in the command line.  Although Netmedia does store these items in the Windows Registry so an external program can modify them before launching the command line compile.

So I created a vbscript that sets the IDE options and then calls the compiler.  The script accepts 3 parameters:
 1 (Required) - Project file
 2 (Optional) - /c
 3 (Optional) - /d

The script supports drag and drop capabilities so you can use it 1 of 2 ways. 
1 - Drag the project file onto the script
2 - Call the script from your editor or a batch file

I usually create a build.bat file that I just call from the text editor.  The build batch file is specific to the project that I am working on so I generally keep it in the main folder of my project.

I have included the script files along with a sample BX24 project so you can look at what I did and maybe make use of it for your own BasicX projects.

I also use a shareware text editor called TextPad.  This editor supports syntax highlighting and multiple documents.  The nice thing about it is that I can pass TextPad the project file and it can load up all the source modules that are associated with the project.  I often use a batch file to launch the textpad editor and open all the source code for the project.  I have also included this batch file in the bx24.zip so you can see how it is done.

Tags:

Robotics

Scrum process for a team of 1

by Mike Linnen 12. July 2006 01:41
Scrum process for a team of 1
del.icio.us Tags: ,

On my flight from Charlotte to Phoenix this week I listened to a number of podcasts.  One of my favorites is Hanselminutes.  Scott Hanselman talks about a lot of thins I am interested in.

In the Line of Scrumage podcast Scott talks about applying the Scrum agile process in his work place.  Most of what he talked about are things that we have been using at JDA Software Group Inc.  However Scott brings up an interesting point about applying Scrum processes to a 1 person team.  I have often thought about this for some of my own personal projects.  I often do small projects for myself and I end up playing the roles of product owner, business analyst, developer, and tester.  So could I effectively use Scrum as a way to manage these projects?  Well I have sort of attempted this on a couple projects and here is what I found out.

The part about building a backlog of stories that are features to get into a product and giving them a priority is something that has worked for me vary well.  I find it easier to express the features that I wish to get into my projects as a story.  The story format lets me capture the user, action and benefit in a quick step.  If I had to spend a lot of time working out the functional documentation of a given feature I am afraid I would not end up completing the feature in a timely fashion.  Even prioritizing the features helps me focus on what needs to be developed next. 

However the process of story pointing features and planning them out over multiple sprints just does not seem to give me any real benefit.  The main reason for this is that since these projects are personal projects they do not get a consistent amount of time dedicated to them.  I might have 3 hours 1 week and 0 hours the next to dedicate to the project.  So planning for sprints and trying to determine my velocity is somewhat difficult.  This aspect of Scrum ends up not being part of my personal projects.  This is ok for me though because I feel more organized by maintaining a backlog with priorities.

Web page updates

by Mike Linnen 6. July 2006 22:44
Web page updates

Added the ability for the blogger to receive emails when a new comment is posted to a blog entry.

Added the ability to contact me by email via a contact form.

Day 2 of USFA Nationals

by Mike Linnen 4. July 2006 14:01
Day 2 of USFA Nationals

Day 2 of Shawn's participation in the USFA Summer Nationals was on Monday 7/30/2006.  Check out Day 1 at USFA Nationals for some previous results.  Also check out the pictures that I posted that were taken during our trip. 

Wake up call at 5:30 am was surprisingly on time.  We headed to breakfast at 6:25am and then we hurried to the lobby to request out car.  How many valets does it take to find your keys you ask?  Well more than two.  After a 12 minute wait I headed in the room to assist in the search.  I searched high and low and finally found them laying on the floor.  Meanwhile Denise stood anxiously starring at her watch as the time we were supposed to check into the fencing tournament arrived.  We hurried on to the World Congress Center and fortunately when we arrived at 7:15am there was no line.  So Shawn checked in for his much anticipated saber event, hurried to base camp to wait to be summoned to the "Piste" (fencing strip).

Shawn's saber event had 97 other fencers.  The initial seading based on previous tournament results placed Shawn in 58.  This meant he fell pretty close to the middle of the other fencers.  After the pools are completed the seeding would be re-evaluated and Shawn would be matched up with his first Direct Elimination opponent. 

The pools started at 8:50am and completed at 9:40am.  Shawn fenced 6 bouts during the pool.  Shawn won 1 and lost 5 bouts.  Most of the bouts were very close and Shawn made them very exciting.  His last bout was where he earned his win.  Shawn used a fencing technique called the line to lure his opponent into a failed attack and then he scored by striking on the opponet's right side.  This worked for 3 of the five points during this bout.  The final score of this bout was 5 to 1 with Shawn as the victor.  Shawn moved up one spot in the seeding after the pools were completed.

After the pools the Direct Elimination (DE) tournament began on strip 44 of the venue.  Shawn's opponent was a little shorter than he was which was an advantage by reach for Shawn.  The DE is a best 2 out of 3 bouts that are 5 points each.  Shawn started off with the first bout on a win that was 5 to 3.  Very impressive start!!  The second bout went to Shawn's opponent in a 2 to 5 loss.  It was going to have to go to the 3rd and final bout to determine who was going to advance to the next round.  This sure makes a parent nervous watching your child get so close to winning his first National DE.  But Shawn ended up coming a little short on the points and he lost the bout 5 to 3. 

Well we once again are very proud of Shawn at how well he did in the USFA Summer Nationals of 2006!  He showed so much determination at doing his best and being a real winner even if he did not advance into the finals of the tournament.  Shawn had a lot of fun doing this tournament and we can all expect to see him at the next Summer Nations that will take place in Miami, Florida next year around the fourth of July. 

Tags:

Family

Pictures of the USFA Summer Nationals posted

by Mike Linnen 4. July 2006 13:26
Pictures of the USFA Summer Nationals posted

I uploaded some pictures of the Fencing tournament for anyone that is interested.  For right now I don't have a good way to allow for comments to be left on individual pictures.  So leave any comments about the pictures on this blog entry.

About the author

Mike Linnen

Software Engineer specializing in Microsoft Technologies

Month List