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.

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

Interfacing a PC to the outside world Part 2

by Mike Linnen 24. November 2005 20:26
Interfacing a PC to the outside world Part 2

In Interfacing a PC to the outside world Part 1 I mentioned that I wanted to work on a set of articles to discuss interfacing your PC to the outside world.  In part 2 I am going to continue the series and talk about what my first connection to the outside world is going to be. 

 

There are a number of devices that are designed to communicate over I2C.  I2C is a serial interface developed in the 1980's at Phillips Semiconductor.  The architecture allows for multiple devices to co-exist on the same 2 wire bus.  You can get more information on the I2C bus at the following: http://www.esacademy.com/faq/i2c/. 

 

There are a considerable number of devices that support the I2C bus.  A compass can be used to determine direction.  A sonar module can be used to detect obstacles.  A motor controller can be used to drive motors on a robot.  A servo controller to drive hobby servo motors.  All of these I2C capable devices (and several more) can be found at www.acroname.com.  I have done some research on PC I2C devices but so far everything I have found is fairly expensive.  I believe I can make a device that will bridge the PC to I2C gap and open up the world of I2C devices to PCs.

 

So a .Net I2C library is going to be the first project that I will do.  The library will support communicating on the I2C bus to other devices.  The consumers of this library should not care how the I2C communication is actually implemented.  So the primary goal of this exercise is to architect a provider model for communicating to these devices.  The benefits of this model allows for different I2C providers to be used without affecting the consumers. 

 

The first provider I will be creating will be a micro controller RS232 I2C Provider.  This will be  a small device that sits between the PC and the I2C devices.  The micro-controller's job is to intercept the serial commands from the PC and convert them into I2C commands.  I will be using a BX24 from Netmedia as this micro controller.  Later I will create a parallel port I2C provider that can be used in place of the micro controller RS232 provider.

 

The PC to BX24 I2C solution is a little more expensive than I intended to start with.  However I have a few BX24s lying around from other projects so it won't take a dent out of my pocket.  Also I have a Deventech compass to try the library out on.  Besides I also intend to use the BX24 for other interfacing projects.

 

    

Tags: , , ,

Robotics

Interfacing a PC to the outside world Part 1

by Mike Linnen 23. November 2005 10:15
Interfacing a PC to the outside world Part 1
 

I have been reading some of the Coding4Fun articles that are on MSDN.  Several of the articles are focused on connecting your computer up to external devices and writing .Net code to interface with the devices.  This has always been a main interest of mine since I am interested in robotics and home automation.  The resent release of .Net 2.0 has made some nice features available for doing serial communications.  Also Microsoft has made the Visual Studio Express editions freely available for 1 year.  This makes up a great solution for the general hobbyist to play with software and hardware.  So I thought it was time that I start my own set of articles on building software and integrating it to hardware devices.

 

So I gave it some thought on where to begin.  What project will be a prime candidate?  How would I build the foundation so I could leverage different hardware solutions to a given interface problem.  So I decided on a few goals to keep in mind about the project:

  • Provide a solution to an interfacing problem that could be used in many projects.
  • Build the library using .Net 2.0.
  • The library should extract the consumer from any hardware implementation.
  • The library should be testable without hardware implementation. 
  • The library can use external pluggable components to fulfill the interface to the hardware itself.  So 3rd party components can be built and plugged into the library.

 

Stay tuned for a series of articles on this project

Tags: , ,

Robotics

Another Test example for the BX24

by Mike Linnen 20. October 2005 01:25
Another Test example for the BX24

A previous post I explained how simple it is to test your code even though you might not have a fancy test framework like NUnit.  In this post I am going to give another example of what I did to tackle a robot navigation problem and fully testing it without actually running the code in a real robot.  My point here is that it is a good practice to write test code to test sub modules to simulate all possible scenarios that would be tough to do in the real robot.

So here is the problem:

I have a compass module that outputs a heading value that equates to 0-359 degrees. I needed a module that when given a target heading and a current heading it could return the differance between the two in degrees. The return heading difference would range from -180 to 180 degrees. This return value could be processed further to determine which direction the robot needed to turn to reach the target heading. A negative heading ment to turn left and a positive number would mean turn right.

So my approach was to first identify a list of target and current headings and what I would expect the return value would be for these input parameters. I did this for 17 different scenarios. I placed the values in a spread sheet and analyzed the pattern that emerged. I took this pattern and coded a simple class (module) that would impliment the pattern.

Here is the method of the class:

Public Function GetHeadingDifference(currentHeading as Integer) As Integer
  ' Returns the following
  ' -180 to + 180
  ' Negative number means the robot would have to turn to the left to get closer 
  ' to the targetHeading
  ' Uses module variable targetHeading
  
  Dim targetMinusCurrent as Integer
  targetMinusCurrent = targetHeading - currentHeading
  
  If (targetMinusCurrent<181) And (targetMinusCurrent>-181) Then
    GetHeadingDifference=targetMinusCurrent
    Exit Function
  End If
  
  If (targetMinusCurrent<-180) Then
    GetHeadingDifference=360 - ABS(targetMinusCurrent)
    Exit Function
  End If
    GetHeadingDifference=(360-ABS(targetMinusCurrent)) * (-1)
End Function

I then created another test class (module) that would call the navigation module and pass in the 17 scenarios and validate the return heading.

Public Sub Main()
  '.......... Test code ..........
  'This needs to be done only once per program, or when you want to change the baud
  Call UARTsetup(3, 19200)  
  InitializeNavigation
  Dim testResult as Integer
  Dim newHeading as Integer
  Dim targetHeading as Integer
  Dim currentHeading as Integer
  
  '****************************************
  'Test TestHeading
  '****************************************
  DebugPrintLine "TestHeading Tests"
  newHeading=180
  currentHeading=180
  SetTargetHeading newHeading
  testResult=TestHeading(currentHeading)
  If (testResult<>0) Then
    DebugPrintLine "Test 1 Failed"
  Else
    DebugPrintLine "Test 1 Passed"
  End If
  newHeading=180
  currentHeading=183
  SetTargetHeading newHeading
  testResult=TestHeading(currentHeading)
  If (testResult<>-1) Then
    DebugPrintLine "Test 2 Failed"
  Else
    DebugPrintLine "Test 2 Passed"
  End If
........... more test code omitted for clarity 
End Sub 

I used the 17 scenaros that I layed out on the spread sheet to prove out my logic. Since the module is fully tested based on these scenarios I have complete confidence that the module will work when it is included in the main robot code project.

Testing without a testing framework

by Mike Linnen 19. May 2005 06:53
Testing without a testing framework

I have been doing a lot of Unit Testing in my day job using NUnit as the framework. I find writing code to test code is very interesting and makes my coding efforts less bug prone. However in my off time I often mess around with non .Net programming projects and I miss the ability to write test code in these projects. Well it is not too hard to follow the same sort of unit testing practices when you do not have a testing framework in place.

Just recently I was writing some BX24 code for a robotic project. I needed to create some conversion procedures to go from a Byte/Integer to a String and a String to a Byte/Integer. How would I determine that my new procedures would work as designed? Certainly I could not rely on the production robot code to test the conversion procedure.

The BX24 programming language has the concept of projects and source modules. A project is nothing more than a collection of source modules. One of the source modules must be the main entry point of the project for starting execution. This concept allows me to simply create test projects that are designed to test a single source module.

So I moved my conversion procedures into a Conversion Module and made a Conversion Test project. Then I proceeded to write test code in the main module of the Conversion Test project to exercise the Conversion Module. I now had unit tests that exercised the outer bounds of the Conversion Module. I proceeded to fix bugs in the Conversion Module until all tests passed.

Of course without a framework I did not have the nice GUI with Red/Green lights to tell me a test passed or failed but it sure did help me determine if my module was fully functional or not. So if you have a programming project that does not have a nice unit testing harness but your IDE supports module level programming you to can use the above techniques to write bug free code.

Tags: ,

Robotics

About the author

Mike Linnen

Software Engineer specializing in Microsoft Technologies

Month List