page 697

Figure 2.1 Dimensionality of Obstacles

2D

2.5D

3D

40.2.2 2D MOBILITY PROBLEM

When a simple mobile robot has to navigate across a factory floor, it must solve the classic ’piano movers’ problem. This representation is easily done with convex polygons, and it runs quickly. This problem is referred to as the piano movers problem, because it involves having to move a very large object (like a piano) through a cluttered environment, without picking it up. The perspective is that, the obstacles can be seen from directly above, but they are assumed infinite in height. This method may be adapted for a robotic manipulator, if it is working in a clear workspace, and is performing pick and place operations. The use of this method will save time, in all applicable cases.

As a result of the speed benefit of the 2D path finding solutions, they may be used as analytical tools. A special property can make the 2D methods applicable to 3D problems. If a 2D view of a 3D work space shows a path, then the same path will also exist in the 3D workspace. This has been used in some path planning methods, and can provide a ’trick’ to avoid extensive 3D calculations. Another trick which may be used, is to represent the moving object with a box or a circle. This result in a simple technique for maintaining a minimum obstacle clearance, for collision avoidance.

page 698

Figure 2.2 Simplification of 3D Problem

3D Space

2D Approximation

40.2.2.1 - 2.5D HEIGHT PROBLEM

When height is added to 2D objects, it is no longer necessary to assume that they have an infinite height. It is equivalent to changing the view from looking straight down on the workspace to looking at it from an angle. This can allow some very simple path plans in which the manipulator is now allowed to move over and around objects. With pick and place tasks this can be the basis for a method which guarantees that the payload, and manipulator links, are above collision height. This is a very practical approximation that is similar to the manipulations which humans tend to favour (i.e. Gravity fed obstacles and objects).

This method is faster than 3D solutions, while still allowing depth in obstacles. Any object in the real world that does not have a vertical orientation will be very difficult to model. Despite this problem, this is still a very good representation for solving most pick and place problems (in an uncluttered workspace).

40.2.2.2 - 3D SPACE PROBLEM

When we have a cluttered 3D space problem, it may not be possible to resort to the use of 2D and 2.5D representations, if obstacles have irregular surfaces which may not be represented in 2D or 2.5D. This is the most frustrating problem. This problem has fewer simplifying restrictions, and as a result the dimensions grow quickly for every new factor.

The most devastating setback to the 3D methods occurs when a multilink manipulator is added, without any limiting assumptions. The addition of each manipulator link will increase the problem complexity geometrically. This method may be simplified when spheres are used to represent moving obstacles.

The most successful attempts at solving this problem have been the optimization attempts.