1.5 IMPLEMENTATION EVALUATION CRITERIA

This section is the most difficult to handle. In some cases the methods are excellent, but the implementations are so poor that they fail to display the merits of a path planning method. Up to now researchers have occasionally included run-times and machines, for their discussions, although some have not tested their methods. This variation is noticable, thus some standardization is needed. In this section some simple means for comparison are suggested. A quick list of general implementation evaluation criteria is also in order,

 

- minimum time for solution search

- minimum path time

- maximum forces

- minimum distance

- maximum torques

- 2D mobile robots or 3D linked manipulators

- feasible trajectories

 

1.5.1 COMPUTATIONAL TIME

One thing that needs definition is the Typical Execution Time. The problem with this criterion is computers, languages and programs run at different speeds, and various problems will vary between implementations. Thus the author proposes a set of two scenarios in 2D and 3D workspaces, and suggests that Typical Execution time be expressed in machine cycles (A good High Level Robotics programmming Language could save a lot of trouble at this point).

 

Figure 5.1 Path Planning Test Scenarios

 

These look like nicely packaged problems, but they call for a few exceptions. The classic "Piano Movers Problem" is a good example. The piano movers problem is perfectly suited to a mobile robot. If the routine is used for mobile robots, then both the scenarios above should be used on the object to be moved (without the arm). In both of these problems the consideration of manipulator links is important. In a 3D problem the path planner must consider all links of the robot as linked objects which are to be moved, without collision. The ideal minimum, to properly evaluate the methods on a comparative basis, would need planning time, setup time, travel time, and a performance index (covering stress and strain in the robotic manipulator).

These tests have one bias, both are oriented towards representation with polygons. This was considered acceptable because most objects in the real world are constructed of flat surfaces, or can be approximated with them (like Cylinders, Spheres, Toroids).

The ultimate path planning test could be a needle through a hole problem. In this scenario, a box with a hole in it could be held at an odd angle in space. The peg could be picked up off the ground, and inserted into the hole. The manipulator could then force the peg through the hole as far as possible, and then remove the peg from the other side and return it to its original position. This could also be approached as a single path, or as many as twelve separate paths.

 

1. Move arm near cylinder

2. Move to and grasp cylinder

3. Move to near hole

4. Insert peg in hole and release.

5. Move arm away from peg.

6. Move arm to near other side of peg.

7. Grasp peg.

8. Remove peg from hole.

9. move peg to near original position.

10. place peg on ground and release.

11. move away from peg.

12. Move arm to start position.

 

This evokes a number of different approaches. The most obvious is the use of both gross and fine motions. The second most obvious is a single path in which all of the tasks are located at via points on the path. Another approach is to combine steps into more efficient tasks. This problem allows flexibility for all path planners.

 

Figure 5.2 Peg Through Hole Problem

 

 

 

1.5.2 TESTING OF PATH PLANNERS

Testing a new method is very subjective problem. The points to consider are the type of method used, and its implementation. A few points by which to describe these methods are given below, but these facts are not always given in the path planning papers.

 

- Guarantee to find solution.

- Optimality of Solution.

- Ability for method to get trapped.

- Ability to find alternate paths.

- Degree of Automation in the Planning process.