IRIS-99-373

Dimensional Inspection Planning for Coordinate Measuring Machines

S. N. Spitz

This thesis documents the development of a fully automated dimensional inspection planner for coordinate measuring machines (CMMs). CMMs are very precise Cartesian robots equipped with tactile probes. Given a solid model of a manufactured part, the goal of dimensional inspection is to determine if the part meets its design specifications. The planner first generates a high-level plan that specifies how to setup the part on the CMM table, which probes to use and how to orient them, and which measurements to perform. This plan is then expanded to include detailed path plans and ultimately a program for driving the CMM. The planner has been implemented and includes an accessibility analysis module, a high-level planner, a plan validator (through collision detection), a simulator, and a path planner. We tested the planner on real-world mechanical parts and it is sufficiently fast for practical applications. The accessibility analysis module provides a suite of algorithms to compute global accessibility cones (GACs). GACs are sets of directions along which a probe can contact given points on an object's surface, and are used by the planner to determine part setups and probe orientations. The GAC algorithms make use of widely available computer graphics hardware, and are very efficient and robust. The high-level planner generates plans by solving a constraint satisfaction problem (CSP), where hierarchical constraints define the requirements of good plans. Plans are extracted using efficient clustering techniques. High-level planning by clustering and without backtracking is a novel approach. The path planner finds an efficient and collision-free path for the CMM to inspect a set of points. We use a roadmap method to connect the points through simple paths. Then, we find an efficient tour of the roadmap by solving a traveling salesperson problem. The path planner easily integrates CMM heuristics and is probabilistically complete.