next up previous contents
Next: Future Enhancements Up: Reasoning About Path-Planning with Previous: Directional Reasoning

Summary of Path-Planning Issues

The EPB/PDO representation, as implemented for this system, provides a number of advantages in reasoning about motion. An important advantage is the way in which relationships between individual boundary elements are explicit properties of the elements themselves. This fact removes the need to search for information in global sets of relationships. Since most reasoning about motion involves reasoning about interaction between objects, and interaction between objects involves relationships between their boundaries, the reasoning system can be greatly simplified by making this information readily accessible.

Relative size information has been made more explicit in the EPB/PDO representation than in the ASSF representation by using the partial distance ordering. This extra information makes path planning easier, but accentuates problems caused by the lack of directional information. As stated above, the reason for failure of reasoning goals in this system is nearly always lack of precise directional information. This occurs whenever angles other than right angles are encountered - several non-right angles in a reasoning chain result in a completely unknown overall angle.

This poor directional information is allowed for by the distinction between vague and precise angles. This distinction allows the system to perform well when large numbers of right angles are in the scene, and also allows it to recognise where problems will result when there are not many right angles. The result is a reasonably robust system for using scanty directional information, but overall performance is limited by the lack of power of the simple four quadrant description of qualitative direction and angles.

In finding the rules for ``qualitative trigonometry'', it was clear that very few rules could be stated on the basis of right, acute, and obtuse only. The number of rules was more than doubled by the addition of two new qualitative angle ranges - very-acute and very-obtuse. This would continue to be true as new ranges were added, until in the extreme case the qualitative trigonometry table had as many entries as a numeric table. Although this would increase the power of the reasoning system, it is contrary to the objectives of this study, and the development of an alternative approach to qualitative expression of direction (perhaps based on a ``partial angle ordering'', or on order of magnitude reasoning) would be more valuable.

The use of multiple levels of detail on the object boundary did reduce reliance on precise directional information. Complex pieces of boundary with many ``vague'' angles were often represented at a coarser level of detail with fewer angles, and this enabled the system to perform coarse path planning more confidently. In addition to this, the lack of allowance for curved boundary segments in my implementation was of little importance for coarse path planning, because most curves can be represented at a coarse level of detail by two straight segments with a junction between them, where the angle of the junction approximates the curve. The places where this is not practical include calculation of extremities, which must include the bulge of the curve rather than the position of the extra junction, and reasoning about rotation involving curves.

The implementation of this system has shown that it is possible, using qualitative reasoning techniques, to solve practical path planning problems. The natural robustness available to a qualitative system is evident in the application of the partial distance ordering, and of relative angle precision. Both in angle and magnitude reasoning, the system is able to select from different data and geometric constructions to find the most precise data available. However imprecise that data is, the system can continue with its reasoning process, until it recognises that the data is now insufficient. In this case, it is still able to act on the lack of data, and ask a robot or an operator to gather more data.


next up previous contents
Next: Future Enhancements Up: Reasoning About Path-Planning with Previous: Directional Reasoning
Alan Blackwell
2000-11-17