The primary goal of this research is to construct a theoretical framework for understanding and design of reactive devices starting from the description of a high-level task. The research is based on a new class of robot algorithms that the PI calls ``reactive algorithms.'' These offer insights into how a robot itself can use its body parts like "analog computers'' and be computationally more powerful than its "digital brain,'' and perhaps may ultimately shed some light on the question of how insects with far fewer neurons than a robot are able to accomplish much more complicated manipulation and locomotion tasks. So far the main applications of these ideas have been in constructing new parallel-jaw grippers and multifingered (2- and 3-fingered) hands, a "twirling-machine'' and a walking machine. The PI has built a prototype parallel-jaw gripper ("NYU reactive gripper'') based on these algorithmic ideas. The resulting gripper reduces the necessary computing power to only a few simple digital circuits, utilizes primitive sensing abilities, i.e., no more than a dozen infra-red emitters and detectors and operates in a smooth manner without disturbing or damaging the manipulated objects. The PI has been investigating how to describe these devices and prove their correctness using the Ramadge-Wonham Discrete Event System (DES) formalisms. Another goal is to understand the "computational'' complexity of these devices based on a framework for analyzing the "competitiveness'' of on- line algorithms in comparison to an idealized clairvoyant algorithm. Other theoretical questions relate to the effect of noise, algorithmic modification for immunization against noise, the sensor-placement problem, and stability and convergence properties.
