Building an efficient maze robot that can get there fastest with the least effort

Mariano Gomez Plaza, Sebastian Lopez Rodriguez, Sebastisn Sanchez Prieto, and Daniel Meziat Luna

August 22, 2007

Mariano Gomez Plaza, Sebastian Lopez Rodriguez, Sebastisn Sanchez Prieto, and Daniel Meziat LunaAugust 22, 2007

Robotic electro-mechanical machinery is becoming an increasingly important element in industrial control systems, remotely piloted aircraft and vehicles, and even with consumer products such as vacuum cleaners.

Industrial robots are widely used in spray finishing operations, pick and place operations such as loading and unloading pallets and in the casting of metals and plastics, spot and arc welding as well as assembly.

Mobile robots are also used widely and include tele-op robots with the ability to sense and avoid objects. Automomous robots with random motion incorporating simple bump and turn algorithms are incorporated into consumer products such as the Roomba vacuum cleaner and Friendly Robotics lawnmower.

Key to the operation of these various robotic systems is the development 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 map of the "territory" and then make decisions about the sequence of motions that must be performed to accomplish a specific task.

Regardless of the physical implementation, the key element in such robotic movements is the development of an algorithm that allows the robot to search for and find the shortest path through a maze. This usually involves determining an optimal trajectory generation setup in the particular maze environment.

In this article we describe a new approach to optimal trajectory generation setup in a maze environment. To test and illustrate the features of the new algorithms we use a maze with a square geometry (right angled curves), constant wide of the maze corridors and where ther is only one entry as well as one exit.

The described method consists of dividing the main goal - getting out from the maze with no necessity to detect obstacles following the shortest path - in three sections or phases in order to simplify the complexity of the whole methodology: maze inspection, shortest trajectory generation and pursuit of the generated trajectory.

A brief history of mazes and trajectory planning
 In an industrial robots[1] [2], trajectory planning is used to control robotic arm joints to produce the desired movement. This is done by interpolating intermediate points and control cinematically and dynamically the arm joints [3] [4].

Nowadays, there are several open research topics in the trajectory generation applied to mobile robots called car-like robots [5]. The trajectory generation in these robots consists of processing data related to environmental mapping, obstacle positions, robot position, etc. [6] [7] [8] [9].

The trajectory planning must work with mobile obstacles in home or office environments, and the optimal path must be re-planned in real time [10]. This trajectory can delimit a way drawn up by only one robot [11] [12] or by a group of robots [13].

Some studies try to find the quickest path on rough terrain while maintaining the robot stability [14]. The idea is that the vehicle moves from an initial position to a final position through intermediate points which belong to the shortest trajectory.

Others researchers argue that the optimal path is a subset of the external trajectories [15]. Here, after a full inspection, the algorithm has the information to generate the optimal path. In this case, the initial position could be the maze entry, the final position, the maze exit, and the intermediate points, maze positions that belong to the shortest trajectory.

A maze algorthm with a difference
In some studies [11][16] these positions are known beforehand and the algorithm knows the final target towards where the robot must go. But in our case the exit of the maze is an unknown position and the algorithm only knows some possible alternatives that will derive from a total description of the maze.

Most of the works related to the resolution of the maze problem start with a reference position which must be reached and use algorithms in which the rows and columns of matrixes are the Cartesian coordinates of the maze. Matrix cells containing maximum values describe positions where walls and obstacles are located. The goal locations are described by a set of Cartesian coordinates with minimum values.

In the maze problem we developed to test out our algorithms, the robot must reach the exit of the maze knowing nothing about the environment and final position of the exit.

For this reason, our algorithms split the problem into three different phases in order to simplify the complexity of the whole methodology - maze inspection, shortest trajectory generation and pursuit of the generated trajectory. With this solution the robot through its sensors acquires data of the environment which must be analyzed in real-time in order to act and make decisions.

Figure 1: Relative co-ordinates system

< Previous
Page 1 of 3
Next >

Loading comments...