Open Navigation Contest
(June 2003-March 2004 )

M3

These following is the progress of M3 for the Open Navigation Contest sponsored by the Alias Smith & Jones Robot Club.

June 15-30, 2003: As Jeff and I tentatively planned to go back to a micro mouse type navigation, I worked out the details and code for a maze mapper algorithm.

July 1-14, 2003: Next contest is not set, so I continued on mapping/dead reckoning improvements. Modified flood fill algorithm to solve a general N-branch maze.

July 1-14, 2003: With working on basic discrete IO routines for the ATMEL board, I'm seeing certain common problems, like it would be nice to have the hardware layer self initialize. Problem with static routines is you still have to delare an object to get the initialization of the object. Thinking maybe able to have a global core_init variable that every constructor first checks first; if not initialized, then performs initialization. Obviously, this incurs (a large?) overhead of extra test. Still maintain OOMRM class has subclassing TPU, QSM etc., but do not have every object subclass OOMRM.

  extern bool __core_init;
  if (!__core_init) ::OOMRM.init();

Aug 1-Sept 1., 2003: Worked out a Navigation System, tentatively calling the INS class (after a inertial navigational system). Several improvements:

1. Fixed the sine routine twice.
2. Fixed the old Mars Rover Syndrome--passed degrees to a function that expected radians.
3. Got tentative derivation for landing in center of a tile rather than at transition of tile.

Sept. 2, 2003: Finally fixed the waypoint RAM storage problem.

Sept. 13, 2003: Several convergences have led me to the idea of a mobile robot simulator. Mostly, the motivation stems from the sucesses with testing the mapping algorithm on strictly a PC board. Secondly, I noticed how similar the "core" code is between platforms (68332, ATMEL) thus leading me to believe a respectible simulation is possible. Third and major convergence is the idea of the abstract layer which is independent of hardware. As this layer is hardware independent, it is really a set of robotic "algorihms". Thus after talking with Jeff after the RSSC club, I decided to begin.

Sept. 15, 2003: Began simulation. After a few days of diving right into mapping M3 into DOS, I decided a DOS based simulation would be a bare to manage the input/output. Am putting in defines for the DOS portion. The advantage is I keep one code base; the disadvantage is you have a chance of breaking something.

Sept. 17-24,2003: Started FLTK GUI potion. Worked sucessively with oPWM, oEncoder, oEncodedMotor, oMobileRobot, oINS. each worked in individually. This also involved finishing an implementation of Object_List which keeps a list of some objects allocated dynamically.

Sept. 24-25,2003: Tackled problem of generating encoder clicks for encodedmotor based upon speed.

Sept. 25-26,2003: Tackled generating a map for the display. Seems sucessful.

Sept. 27, 2003: Sucessfully converted M3 code. For some reason, compiling back "real" robot produced some strange behavior. Was able to verify that simulated course of robot on map was very close to actual course taken by real robot! Given waypoint (4,3) they both started good, but missed angle on way back. Thus they were both in basic agreement.

Sept. 28-Oct 10, 2003: Added primitive mapping using grid floodfill class to simulator.

Oct 11-24, 2003: Looked to see what other work was being done in robotic system architectures to see if I could apply any to OOMRM. The architectures I looked at are as followed:

• Joint Architecture for Unmanned System : An architecture sponsored by the Office of the Under Secretary of Defense (OUSD) for Acquisition to be used on Programs in the Joint Robotics Program (JRP). This architecuture had some appealing features. Specifically I used certain ideas of breaking down the navigational into a base "Primitive_Driver" with higher navigational levels ("Waypoint_Driver", etc.) derived from this. I toyed with the idea of fully being compliant, but in the end, its messaging architecture was too bloated for fully self contained 68332 environments. Had some other problems that have to do with confusion on how much this architecture will really be supported in the future (See next item).
• 4D/RCS : A 4-D architecture for Real-time Control Systems (RCS) . Very interesting architecuture being used in the Future Combat Systems (FCS). Really too high level to be useful for this application though. What was confusing was the statement "...acceptance of 4-dimensional (4D)/RCS Demo III control system architecture as a reference standard for the Joint Architecture for Unmanned Systems (JAUS)...". Thus, the relationship between 4D/RCS and JAUS is very enigmatic at best.
• Robotics Engineering Task Force . Did not look very well developed...

Oct 24-Nov 11, 2003: Refactored oMobiileRobot, INS, and others into the Primitive_Driver, Waypoint_Driver classes.

Nov 11-22, 2003: Looked into Navigational Path Planning besides the Floodfill algorithm to better solve any obstacle course events. One particular method, A* looked to have potential.

Nov 11-23-27, 2003: Modified M3 to solve the Alias Smith & Jones Open Navigation Contest.

Nov 27, 2003: Wrote to Michael Yeh about his A* implementation to see if I could use his code in the library rather than write one from scratch.

Nov 29, 2003: Have approval from Michael Yeh to put his A* code in OOMRM also licensed under the GNU license. Thanks, Mike. That will save me some time and frustration!

Nov 30-Dec 04, 2003: Streamlining the A* implementation to better fit embedded design. Removed many float etc. Also created a separate "occupancy grid" layer that will keep the current mapped environment seperate from the A* code.

Nov 30-Dec 05, 2003: Sucessful small run (3x3') of contest using 3 points, but I found when using points on a larger grid, M3 was often off from the last point by 2". This prevented it from capturing the last waypoint value correctly (hmmm...)

Nov 30-Dec 6, 2003: Transition to 3 layered grid approach and design of Scene Editor for designing mapping scenarios. This is not really needed for the first phase of the contest, but will be handy if when we add obstacles to the contest.

Nov 30-Dec 08, 2003: Sucessfully ran 3'x3' course manipulating the wheel base. I maybe running into hardware produced errors...

Nov 30-Dec 6-12, 2003: Sucessfully implemented a mapping algorithm in the simulator. The simulator simulates an IR sensor and detects obstacles. Implemented a path flag in the A* algorithm. It sets a bit through which the robot will traverse. The mapping algorithm now checks the bit to see if the new obstacle will result in a collision.

Nov 30-Dec 12-14, 2003: Sucessfully implemented the path flag with replanning using A*; if an obstacle was found on the planned path, then it stopped and recalculated a new path using A*.

Nov 30-Dec 15-24, 2003: The last sucesss lead me to reconsider dynamic replanning...in particular, the D* or particularly D* Lite algorithm by Sven Koenig would be good. This has turned out to be very frustrating. I have a sample that is copyrighted and was not "pure" (had other code intertwined); decided to just use the pseuodo-code in the D* Lite literature to code. Either The psuedo-code is vague on how to reinitialize the map after detecting new obstacles or it just doesn't work! I have for now given up, and stuck with recomputing A* from scratch.

Nov 30-Dec 31, 2003: Held mini-contest at Jeff's house. Both our robots ran into technical difficulties. I believe everything was working as it should, but my problem is I need to practice positioning the robot on arbitrary coordinates! (It being late in the evening didn't help though)

Jan 1-Mar 16, 2003: Since my dynamic replanning is working (even if just recomputing the whole grid), I decided to try it on the real robot. Before such I have the ugly task of optimzing the interrupts. Currently, they take 30 ms. to execute without mapping. With mapping will get very ugly. Thus, I'm using the Motorobots libfixed library to optimize interrupts. This also is somewhat frustrating. For although it is cutting the interrupts down to about 20 ms., it has degraded some of the accuracy out. May need to put some floats back in :(

Mar 16 - Mar 16, 2004

Mar 17- Mar 23, 2004Created ability to upload/download maps from/to robot.

M3 Specification