Robotic electro-mechanical machinery is becoming an increasinglyimportant element in industrial control systems, remotely pilotedaircraft and vehicles, and even with consumer products such as vacuumcleaners.
Industrial robots are widely used in spray finishing operations,pick and place operations such as loading and unloading pallets and inthe casting of metals and plastics, spot and arc welding as well asassembly.
Mobile robots are also used widely and include tele-op robots withthe ability to sense and avoid objects. Automomous robots with randommotion incorporating simple bump and turn algorithms are incorporatedinto consumer products such as the Roomba vacuum cleaner and FriendlyRobotics lawnmower.
Key to the operation of these various robotic systems is thedevelopment of mapping algorithms to aid them in moving through a maze.The maze may be physical – such as moving a mobile robot across a room- or a conceptual one, involving the range of motions of a robotic arm.
In either case, the robotic “intelligence” must first create a mapof the “territory” and then make decisions about the sequence ofmotions that must be performed to accomplish a specific task.
Regardless of the physical implementation, the key element in suchrobotic movements is the development of an algorithm that allows therobot to search for and find the shortest path through a maze. Thisusually involves determining an optimal trajectory generation setup inthe particular maze environment.
In this article we describe a new approach to optimal trajectorygeneration setup in a maze environment. To test and illustrate thefeatures of the new algorithms we use a maze with a square geometry(right angled curves), constant wide of the maze corridors and wherether is only one entry as well as one exit.
The described method consists of dividing the main goal – gettingout from the maze with no necessity to detect obstacles following theshortest path – in three sections or phases in order to simplify thecomplexity of the whole methodology: maze inspection, shortesttrajectory generation and pursuit of the generated trajectory.
A brief history of mazes andtrajectory planning
In an industrial robots , trajectory planning is used tocontrol robotic arm joints to produce the desired movement. This isdone by interpolating intermediate points and control cinematically anddynamically the arm joints  .
Nowadays, there are several open research topics in the trajectorygeneration applied to mobile robots called car-like robots . Thetrajectory generation in these robots consists of processing datarelated to environmental mapping, obstacle positions, robot position,etc.    .
The trajectory planning must work with mobile obstacles in home oroffice environments, and the optimal path must be re-planned in realtime . This trajectory can delimit a way drawn up by only one robot  or by a group of robots .
Some studies try to find the quickest path on rough terrain whilemaintaining the robot stability . The idea is that the vehiclemoves from an initial position to a final position through intermediatepoints which belong to the shortest trajectory.
Others researchers argue that the optimal path is a subset of theexternaltrajectories . Here, after a full inspection, the algorithm has theinformation to generate the optimal path. In this case, the initialposition could be the maze entry, the final position, the maze exit,and the intermediate points, maze positions that belong to the shortesttrajectory.
A maze algorthm with a difference
In some studies  these positions are known beforehand and thealgorithm knows the final target towards where the robot must go. Butin our case the exit of the maze is an unknown position and thealgorithm only knows some possible alternatives that will derive froma total description of the maze.
Most of the works related to the resolution of the maze problemstart with a reference position which must be reached and usealgorithms in which the rows and columns of matrixes are the Cartesiancoordinates of the maze. Matrix cells containing maximum valuesdescribe positions where walls and obstacles are located. The goallocations are described by a set of Cartesian coordinates with minimumvalues.
In the maze problem we developed to test out our algorithms, therobot must reach the exit of the maze knowing nothing about theenvironment and final position of the exit.
For this reason, our algorithms split the problem into threedifferent phases in order to simplify the complexity of the wholemethodology – maze inspection, shortest trajectory generation andpursuit of the generated trajectory. With this solution the robotthrough its sensors acquires data of the environment which must beanalyzed in real-time in order to act and make decisions.
|Figure1: Relative co-ordinates system|
First, define the problem space
It is important to define the necessary input parameters required forapplying the algorithm. These parameters must be independent and areprovided by sensors mounted on the robot.
The sensors are related to the ones in charge of detecting theobstacles existing around the environment and the ones dedicated togive the position and direction where the obstacles or robot are/islocated.
Information about the possible data necessary to implement thealgorithm includes:
1. Robot Cartesian co-ordinates. TheCartesian co-ordinates could be relative with respect to a point ofreference or absolutes co-ordinates (e.g.: provided by a GPS). Figure 1above shows a relative system and the Figure2 below , an absolute system.
The algorithm can use both types of co-ordinates system. Accordingto Figure 3a and Figure 3b later in this article, theonly importantaspect is that the robot position (i.e. black point) is independent ofits movement directions. Only a fine tolerance can be allowed.
2. Robot orientation. Itwill be necessary to detect when the robot moves more than once pastthesame site, cutting the trajectory..
3. Obstacle detection . Itcorresponds to a signal that is activated when an obstacle is detectedby the sensor system.
4. Encoder. The obstacledetector system embedded in the robot where the present algorithm willrun is equipped with a three bit encoder whose goal is to detect thedirection of any obstacle. Despite the eight possible detectiondirections, only five directions will be taken into account: North,East,West, Northeast and Northwest. The robot is always considered to goforward (North).
|Figure2: Absolute co-ordinates system|
Another characteristic related to the environment (maze) in whichthe robot can move is the width of the corridors. This value should ata minimum bethe double of the detection distance, because the robot might detectthe presence or absence ofalternatives at the corridor's walls.
|Figure3a: Robot position (zoom out)|
|Figure3b: Robot position (zoom in)|
Mobile Robot structure
The vehicle is equipped with an obstacle detector system able toperform the detection in an area equal to 360º. However, if therobot is always moving straight ahead, it is enough to consider an areaequal to 180º for the obstacle detection. In this case, the robotcan detect five possible detection directions, shown in Figure 4 below :
|Figure4: Detection directions|
The platform of the robot mobile has two wheels, asshown in the Figure 5 below. Each wheel is controlled by a direct current motor in order to move therobot through the maze in the following possible directions: advance(two motors activated), right or left (if only one motor is activated),stop (if no motor is activated). On top of the platform is placed theobstacledetector system, the microcontroller board and the powersupply.
|Figure5: Rolling platform of the robot|
<>Inspecting the maze
The goal of the inspection process is to “know” the environment beforegenerating the shortest trajectory. This phase is considered the mostimportant because it is the baseline for developing the later steps.The final goal is to obtain a trajectory from an origin point to adestination – the exit of the maze. To generate this trajectory it isnecessary to have intermediate points which are not associated with anyobstacles. <>To get these points it is necessary to perform asounding of thecurrent position of the robot at periodic intervals of time. From thisdata an intermediate points table is created.
The more intermediatepoints are obtained, the more memory is needed. Therefore, it isnecessary to fix a sample time small enough toprovide useful information but not so large that it cannot fit into thememory embedded in the vehicle. When the robot is moving straightahead, its behavior with respect to the position where any obstaclesare detected is shown below in Table1 below.
|Table1: Initial behavior of the robot in the presence of an obstacle|
In order to make this behavior table, it is usually necessary toeither use an algorithmprogrammed in a classical sequence way or use an algorithm based onneuralnetworks. Due to the fact that the behavior of the system is the samefor any input, the algorithm needs neither learning nor does it need toevolve its behavior in the presence of new input samples. This allowedus to use a sequentialalgorithm rather than one based on neural networks.
A good idea before developing the inspection process is to considersome particular cases which can exist in the geometry of theenvironment or maze:
1. A maze like the onerepresented in Figure 6 belowcan appear in a real environment, where the entrance could be the pointnumber (1) and the exit thepoint number (2) .
2. When the mobile-robotgoes through the A-point again, it is necessary to remove the currenttrajectory and generate another one which goes through the alternativethat was not taken at the B-point.
3. Another problem couldoccur when the mobile-robot circulates through a corridor detectingobstacles as in the Figure 7 below.
|Figure6: Special zone in a maze|
|Figure7: Zig-zag possibility|
Modifying robotic behavior
The algorithm was able to solve both cases by just modifying themobile-robot behavior table for obstacle detections derived from theencoder. Detecting obstacles in the East and West directions instead ofturning, allows the discarding of alternative routes to either side ofthe robot without interrupting its original trajectory. In theinspection process the mobile-robot must consult allfound alternatives, indicated in Figure 8 below.
|Figure8: Results of the inspection process|
When the process is finished, the applicationwill have registeredinto a paths table all thepoints on the path from the entrance to the exit that could be possiblealternative points in an alternate route. The pseudo code of theinspect process is thefollowing:
Basically, the algorithm avoids obstacles by recordingalternatives at the both sides of the robot. If the exit or an oldposition is reached then the robot must go to the last alternativedetected. If the robot found an obstacle in its way, then the pathbetweenthe actual robot position and the next alternative is deleted from thepaths table.
|Table2: Behaviour of the robot in the presence of an obstacle|
Shortest trajectory generation
All the crosses that conform all possible paths are registeredafterthe inspection process. The shortest distance will be used in order tocalculate the optimum path (shortest trajectory). The pseudo code ofthis algorithm is the following:
This algorithm analyses the paths table that contains all the crosspoints that had alternatives detected in the inspection process andcopies the points that belong to the same path to a recording_tablewhere each possible path has all its points from the entrance to theexit.
Thus, from all calculated paths, the optimum trajectory (shortestpath) is chosen. The algorithm will draw all possible paths using theinformation obtained in the inspection process (Figure 9a below ). Thesepaths are shown in Figures 9b, 9c, 9d and 9e following, emphasizingthat the last path is the shortest path:
|Figure9: Paths generated after the inspection process|
At this point, the system has incorporated the Cartesian coordinates ofthe crosses that conform the shortest path into a table which will beused to:
1. Guide the robot from thefirst point of the shortest path (entrance of the maze), to thefollowing points of the table.
2. Stop the robot when thelast point (exit) is reached.
The broken line of the Figure 10below is the ideal trajectory that therobot must travel and the continuous line is the real one.
|Figure10: Guiding the robot by the shortest path|
Based on our investigation of the maze problem, in order for the robotto follow the shortest trajectory generation system, two things arenecessary:
1. The system must have acomplete knowledge of the surroundings to generate the optimum path.
2 . To have a delimitedtrajectory, just storing the locations of the various alternativecrosspoints indicated in Figure 8 is enough. These are the points wherethe robot mobile will have detected alternatives that would have takenit on a different trajectory.
In this design the system that provides the environmentalinformation to the robot is based on a laser sweep. This reduces thevision/knowledge range, so it's necessary to cross all the maze to findthe position from which the robot can detect alternatives.
It is also necessary to have a positioning system so that at anytime the application knows the exact postion of the mobile-robot. Withasystem of detection of obstacles based on artificial vision, knowledgeof the surroundings can be increased, reducing the amount ot timeneeded for the inspection process.
Mariano Gómez Plaza hasbeen an assistant professor ofoperating systems at the Computing Engineering Department of the Universidadde Alcalá. He iscurrently developing his doctoral thesis in the research topics relatedto intelligent control systems applied to mobile robotics. Hisinterests include mobile and space robotics and embedded real-timecontrol systems.
Sebastián LópezRodríguez since 2000 hasbeen working at INDRA in several projects about radar data management,aircrafts information distribution and radar plots tracking simulator.His interests include air traffic control and embedded real-timesystems. Since 1990 he has been with Escuela Politécnica of theUniversidad de Alcalá and since 1999 he has been an associateprofessor of operating systems and computer architecture at theComputing Engineering Department. His major research interests includespace technology, on-board satellite computer architecture, embeddedreal-time systems, and mobile robots.
Sebastián SánchezPrieto has since 1999 has been anassociate professor of operating systems and computer architecture atthe Computing Engineering Department. His interests include spaceinstrumentation, embedded real-time systems, and mobile robots.
Daniel Meziat Luna hassince 2000 been a professor of computerarchitecture at the Computing Engineering Department. His majorresearch interests include space technology, on-board satellitecomputer architecture, embedded real-time systems, and mobile robots. <>
 A. Barrientos, L. F. Pen, C. Balaguer and R. Aracil. “Fundamentos de Robtica”, Ed. McGraw-Hill, Madrid. 1997.
 D. Halperin, L. Kavraki and J. Latombe, “Robot Algorithms”. Algorithms and Theory of Computation Handbook, CRC Press, 1999.
 R. Mukherjee, B. R. Emond and J. L. Junkins, “Optimal Trajectory Planning for Mobile Robots using Jacobian Elliptic Functions”, The International Journal of Robotics Research, vol. 16 n 6, Ed. MIT Press. 1997.
 M. J. Atallah and S. R. Kosaraju, “Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel”, SICOMP Volume 17 Issue 5, 1988.
 J. M. Angulo and R. Avils. “Curso de Robtica”, Ed. Paraninfo, Madrid. 1985.
 P. Moutarlier, B. Mirtich and J. Canny. “Shortest Paths for a Car-like Robot to Manifold in Configuration Space”, The International Journal of Robotics Research, vol. 15 n 1, Ed. MIT Press. 1996.
 G. Dudek, K. Romanik, and S. Whitesides, “Localizing a Robot with Minimum Travel”, SICOMP Volume 27 Issue 2, 1998.
 A. Blum and P. Chalasani, “An Online Algorithm for Improving Performance in Navigation”, SICOMP Volume 29 Issue 6, 2000.
 S. Albers and M. R. Henzinger, “Exploring Unknown Environments”, SICOMP Volume 29 Issue 4, 2000.
 F. Lingelbach, “Path Planning using Probabilistic Cell Decomposition”, Proc. of the IEEE Int. Conf. on Robotics and Automation, 2004
 S. Yang and M. Meng, “Neural Network Approaches to Dynamic Collision-Free Trajectory Generation”, IEEE Trans. Syst., Man, Cybern., vol. 31, June 2001.
 J. G. Ecker, M. Kupferschmid, and S. P. Marin, “Performance of Several Optimization Methods on Robot Trajectory Planning Problems”, SISC Volume 15 Issue 6, 1994.
 A. Das, R. Fierro, R. Kumar, J. Ostrowski, J. Spletzer and C. Taylor, “A Vision-Based Formation Control Framework”, IEEE Trans. Robot. Automat., vol. 18, Oct. 2002.
 M. Kobilarov and G. Sukhatme, “Time Optimal Path Planning on Outdoor Terrain for Mobile Robots under Dynamic Constraints”. In IEEE International Conference on Robotics and Automation, Apr 2005.
 D. Balkcom and M. Mason, “Time optimal trajectories for bounded velocity differential drive vehicles”, IEEE International Conference on Robotics and Automation, 2000.
 D. Hsu, R. Kindel, J. Latombe and S. Rock, “Randomized Kinodynamic Motion Planning with Moving Obstacles”, Int. Journal of Robotics Research, vol. 21 n. 3, March 2002.