@InProceedings{GutmanFikuchiFujita2005,
author = {Gutman, J., Fukuchi,
M., Fujita, M.},
title = {Real-time path planning for humanoid robot
navigation},
booktitle = {Proceedings of the International Joint Conference on
Artificial Intelligence}
crossref = {},
key = {}
pages = {1232--1238}
year = {2005}
editor = {}
volume = {}
number = {}
series = {}
address = {}
month = {}
organization = {}
publisher = {},
note = {}
annote = {}
}
This paper regards an implementation of a real time path planning for a humanoid robot navigation, as the title would suggest.
There are many reasons that make this a difficult problem to solve. The main one being that moving an object through space has been shown to have time complexity exponential to the degrees of freedom [p1]. This paper deals with a mobile robot and the implementation to reduce the degrees of freedom to make real time calculation possible.
The authors decided to treat the robot as two cylinders in order to simlify the calculation of collisions. However they are quick to note that this is an oversimplification, because a robot requires additional room to turn [p1].
Another way they reduced the possible degrees of freedom was to reduce the set of possible robot actions to a set of "well chosen actions" [p1].
One difference between this paper and another similar study by Shiller et al. [2001] is that shiller maintained an obstical space for each one of the descretized actions. By using multiple cylinders to represent the robot, only one obstacle space was needed yeilding proformance gains [p1]. In addition to this, this study's robot selects the behavior depending on the environment, not planned behaviors.
Their robot moves in a two dimensional world, the different levels of ground are projected onto the plane, and are viewed as a grid of evenly spaced cells [p2]. The cell size was decided to correspond to the turning radius of the robot. In one cell the robot can be in one of eight orientations.
_ _ _
|_|_|_|
|_|_|_| robot in center
|_|_|_|
- robot has possible actions: forward backward turn-left turn-right
side-left and side-right
- a 45 degree turn followed by a forward or backward allow the robot
to move on diagonals
The cylinders as mentioned above, are a tight fit to the robot, however more space needs to be accounted for for walking forward and turning. Walking sideways is therefore the robot movement that takes up the least space [p2].
With the cylinder representation, a collision can be calculated in constant time, that is, compairing the distance to the object to the radius of the cylinder [p2]. In addition to that, asumptions about the world are made such as the world is either floor or obstacle, there arnt two floor levels at the same point, and that the robot can tell the difference.
The robot can then create a FOG (floor height map) of its surroundings using its range data from stereo vision to create a 2.5 D height map [p3]. Then a NAV (navigation grid) is computed using the FOG to store floor types and distance to obstacles.
Floor type is decided for the robot by checking if steps in elevation are greater than the maximum stair height [p3]. Stairs will have a different path cost than steps and borders will be treated as obstacles.
Since the FOG represents heights, the clearance of the robot is easily calculated aswell, as the height of the smaller cylinder representing the legs is compaired to nearby objects. Thus the program calculates which cylinder comes into play and allows for the closer passing of short objects [p3].
d(floor) of cell (x, y) is the minimum distance to each obstacle, and is computed efficently by evaluating a constant growing region of the map.
Path planning is represented as a sequence of transitions [p3]. An allow(c, a) checks if a move is allowed by clearance and other limitaions such as not being able to turn on stairs. Some initial and goal states are solvable, some are not. The optimal path is the path of interest and thus a cost function is also used [p4].
Costs imposed are relative to time, for example, walking sideways is slower than walking forward [p4]. Floor is prefered to unknown, and the safer path is more heavily weighted. An A* algorithm is used, and possible paths are ranked by a function that is the sum of the path cost so far and a heuristic that is both optimistic and a larger cost estimate than euclidean distance [p4]. This method is known to find the optimal path.
This all was then implemented in a small Sony humanoid robot. It has three 400 mhz cpu's and a stereo camera with 45 degrees of view [p4]. A stage 4 meters long and 1 meter high was constructed including several obstacles. The robot evaluated its surroundings by spinning. It was then instructed to move to a point 3 meters away. The path included the robot moving between 2 very close obstacles, forcing the robot to move sideways through it. It later climbed stairs, and manuvered other objects until it reached its destination.
While the decision algorithm is still quadratic, in this example computation time was always < 100 ms [p5]. Worst case exits when the goal is placed at an impossible location, which this robot took 900 ms in this example.
Limitaions of their current approach include inaccuracies due to the grid size and grid itself, and using only 8 orientations, which limits the robots ability to manuver [p6]. Future work for this team includes refigning the grid, the capacity to step over or go under obstacles, and implementing turns on stairs, so the robot can traverse a spiral staircase.