A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees

We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.

An Algorithm for Parsing Flow Graphs

This report describes research about flow graphs - labeled, directed, acyclic graphs which abstract representations used in a variety of Artificial Intelligence applications. Flow graphs may be derived from flow grammars much as strings may be derived from string grammars; this derivation process forms a useful model for the stepwise refinement processes used in programming and other engineering domains. The central result of this report is a parsing algorithm for flow graphs. Given a flow grammar and a flow graph, the algorithm determines whether the grammar generates the graph and, if so, finds all possible derivations for it. The author has implemented the algorithm in LISP. The intent of this report is to make flow-graph parsing available as an analytic tool for researchers in Artificial Intelligence. The report explores the intuitions behind the parsing algorithm, contains numerous, extensive examples of its behavior, and provides some guidance for those who wish to customize the algorithm to their own uses.

Design and Control of a Closed-Loop Brushless Torque Actuator

This report explores the design and control issues associated with a brushless actuator capable of achieving extremely high torque accuracy. Models of several different motor - sensor configurations were studied to determine dynamic characteristics. A reaction torque sensor fixed to the motor stator was implemented to decouple the transmission dynamics from the sensor. This resulted in a compact actuator with higher bandwidth and precision than could be obtained with an inline or joint sensor. Testing demonstrated that closed-loop torque accuracy was within 0.1%, and the mechanical bandwidth approached 300 Hz.