In this paper, we argue for the need to distinguish between task and dialogue initiatives, and present a model for tracking shifts in both types of initiatives in dialogue interactions. Our model predicts the initiative holders in the next dialogue turn based on the current initiative holders and the effect that observed cues have on changing them. Our evaluation across various corpora shows that the use of cues consistently improves the accuracy in the system's prediction of task and dialogue initiative holders by 2-4 and 8-13 percentage points, respectively, thus illustrating the generality of our model.

We introduce a new method for size and orientation normalization of unconstrained handwritten words based on the Hough transform. A modified Hough transform is applied to extremum points along the y coordinate to extract parallel lines corresponding to the boundary lines separating different vertical zones of the handwritten word. One dimensional Gaussian smoothing with variable variance is applied in the Hough space to alleviate the problems caused by the large variation in natural handwriting and the sparseness of extremum points. The method has been tested with and incorporated into an HMM based writer-independent, unconstrained on-line handwriting recognition system and a 25% error rate reduction has been achieved.

It is well known that N-best decoding for speech recognition coupled with post-processing can provide significant accuracy advantages. We have implemented and experimented with N-best decoding for handwriting recognition, using an N-best decoding algorithm that employs a synchronous forward pass and an asynchronous backward pass. One novel aspect of our algorithm is the use of pruning in the backward pass to constrain the search to candidates whose likelihood score is within a threshold specified using the likelihood score of the best candidate. We show that this algorithm is more efficient than traditional N-best decoding algorithms. A two-stage method is introduced in which the language model changes from a relaxed model during the N-best search to a more constrained model for rescoring in a second pass. This method reduces the computation needed for more detailed pattern matching by preselecting the N-best most likely candidates.

It is well known that language models are effective for increasing accuracy of speech and handwriting recognizers, but large language models are often required to achieve low model perplexity (or entropy) and still have adequate language coverage.We study three efficient methods for stochastic language modeling in the context of the stochastic pattern recognition problem and give results of a comparative performance analysis.In addition we show that a method which combines two of these language modeling techniques yields even better performance than the best of the single techniques tested.

Hidden Markov model (HMM) based recognition of handwriting is now quite common, but the incorporation of HMM's into a complex stochastic language model for handwriting recognition is still in its infancy. We have taken advantage of developments in the speech processing field to build a more sophisticated handwriting recognition system. The pattern elements of the handwriting model are subcharacter stroke types modeled by HMMs. These HMMs are concatenated to form letter models, which are further embedded in a stochastic language model. In addition to better language modeling, we introduce new handwriting recognition features of various kinds. Some of these features have invariance properties, and some are segmental, covering a larger region of the input pattern. We have achieved a writer independent recognition rate of 94.5% on 3,823 unconstrained handwritten word samples from 18 writers covering a 32 word vocabulary.

The paper addresses the issue of how to efficiently incorporate a context free grammar into a large vocabulary speech recognizer while maintaining maximum recognizer performance. The new method uses an evolutional grammar (EG) model which produces finite state machines (FSMs) in real time or "on the fly" to accommodate context free grammatical rules. In addition, word models associated with those grammatical rules are built in real time. By optimizing a recursive transition network (RTN) before recognition, efficient instantaneous expansions of the grammatical rules can be ensured. Since all grammatical information is used at the same time that acoustical decoding is done, as opposed to application during a second "post processing" stage, the best attainable accuracy is ensured. Using these methods one can achieve 98% word accuracy and real-time grammatical decoding on the ARPA Naval Resource Management Task.>

Speech activated manipulator (SAM), a reasoning robotic system with sensory capabilities that interacts with a human partner using natural language, is described. The robot understands, in real time, about 1041 semantically meaningful naturally spoken English language sentences using a vocabulary of about 200 words. SAM includes developments in mechanical control, real-time operating systems, multiprocessor communication and synchronization, kinematics, sensors and perception techniques, speech recognition and natural language understanding, robotic reasoning with gripper and arm motion planning. Speech recognition is augmented with semantic analysis and evaluation to form a complete speech understanding system. Used in conjunction with error recovery rules in the robot expert and frame-based knowledge system, SAM is robust and resistant to user errors. The most interesting aspects of the SAM system are described. Observations and experiences are discussed along with some advice for those interested in building similar systems.>

A compiler for constructing optimized syntactic digraphs from easily written grammar specifications is described. These are written in a language called GSL (grammar specification language). The compiler has a preprocessing (macro expansion) phase, a parse phase, graph code generation and compilation phases, and two optimization phases. Digraphs can also be linked together by a graph linker to form larger digraphs. Language complexity is analyzed in a statistics phase. The grammar specification language has been used by several untutored users with good success. It is demonstrated that the optimization phase yields graphs with even greater efficiency than previously achieved by hand. Results of applying these techniques to intermediate and large digraphs are also discussed.>

Ultrasonic range finding is an inexpensive means of obtaining 3-dimensional information about the surrounding environment. Because of this ultrasonic detection methods have received considerable attention recently, particularly in the robotic community. Unfortunately, ultrasonic range finding suffers from shortcomings that are not found in more expensive techniques such as laser range finding. For example, a laser range finder can determine both range from the sensor and location of the reflection surface due to the narrow beam used. The ultrasonic range finder beam is much larger and reflection surface location can only be determined approximately for any single range sample (it is only known that a reflecting surface lies somewhere on a segment of the surface of a sphere of range radius centered on the sensor). This paper discusses techniques for obtaining much better surface information under certain conditions. These techniques form the foundation for more sophisticated methods described in another paper for extracting surface features. The techniques can be used with other range sensors and look particularly promising for adaptively controlling a laser range finder. We will outline the mathematical techniques employed and discuss some experience obtained with a robot mounted ultrasonic range sensor.

Ultrasonic range sensing has attracted attention in the robotics community because of its simple construction and low cost. However, determining range direction is made difficult by the signal beam spread of the transducer. This direction ambiguity can be reduced to some extent by increasing the operating frequency or diameter of the sensor but some ambiguity will still remain. A technique is described for obtaining the true surface normals to a planar surface using three sensors or three positions of one sensor. The solution is quite complex in direct form. A simplifying transformation applied to the direct form and a further simplifying sensor configuration are described which greatly reduces the solution complexity. An alternate formulation of the problem is described from which geometrical insight can be obtained. This alternate solution also lends itself to the generation of tangential constraint surfaces for bounding curved object surfaces.

Ultrasonic range sensing has attracted attention in the robotics community because of it simplicity in construction and low cost. However, determining range direction rather than just range magnitude is made difficult by the expanding signal beam of the sensor. This direction ambiguity can be reduced to some extent by increasing the operating frequency or diameter of the sensor, but some ambiguity will still remain. A technique is described for obtaining the true direction to a planar surface using three sensors or three positions of one sensor. A direct solution of the vector equation is discussed to illustrate the solution complexity in direct form. A simplifying transformation applied to the direct form and a further simplifying sensor configuration are described which greatly reduces the solution complexity. An alternate formulation of the problem is described from which a geometrical insight can be obtained. This alternate solution also lends itself to the generation of tangential constraint surfaces for bounding curved object surfaces. These local feature extraction techniques are extended to perform surface tracking for the extraction of global surface features. The connectivity of local features provides additional information. From this information classification of solid objects is possible.

Special purpose hardware for calculating dynamic time warp distances has been designed and tested utilizing TTL technology. The "Dynamic Time Warp Processor" (DTWP) performs all of the necessary arithmetic and decision making operations for selecting a word from a given vocabulary based on log likelihood distance measurements. The speed limitation in previously designed hardware was due to programmed decision making (often referred to as combinatorics). The combinatorics have been implemented in hardware in such a way that the decisions are made in the time of several gate delays rather than the time of several program cycles. Thus, a dynamic time warp (DTW) is performed on typical 40 frame templates in less than one millisecond. The DTWP serves as a slave to a 16-bit microcomputer. It performs all of the computation and control necessary for pattern classification. A board level implementation is now operational. VLSI implementation of the processor is currently in progress. All logic has been designed in 2.5µm CMOS polycells and has been simulated on the MOTIS timing simulator. The timing simulations indicate that the DTW time of 1 msec implemented at the board level can also be met on the integrated circuit.

An architecture for an integrated circuit to perform LPC-based feature measurement in real time has been developed for speech recognition applications. The integrated circuit architecture is suitable for both isolated word recognition, in which the pattern matching occurs after the end of the utterance, and connected word recognition, where the pattern matching proceeds in synchrony with the speech input. A major feature of this architecture is the presence of stored program control which implements the LPC-based feature extraction algorithm on a single set of computational resources. Preliminary timing analysis indicates that a portion of real time remains unused. Thus, in addition to performing standard LPC-based feature analysis in real time, through program modification and memory addition, the architecture is expected to support more advanced concepts in speech recognition such as vector quantization. To aid in program development, software tools which include an assembler and a simulator and run on the UNIX* operating system have been developed. The projected chip complexity is approximately 20,000 transistors of random logic, 40,000 bits of ROM, and 2,500 bits of RAM.

Robot grippers have previously been designed primarily without consideration of the dynamic responses that are sometimes required for delicate operations. In particular, the manipulation of fragile objects such as eggs or lightbulbs requires the gripper to be able to close on the object with minimal impact forces and yet maintain a static grip force sufficient to firmly handle the object. This paper describes a computer simulation of a two-fingered mechanical gripper with electronically controlled impedance. The analog control system allows independent control of the effective mechanical mass and damping of each finger as well as additional control of common-mode vs. differential mode response. The computer simulation models the gripper as set of nonlinear differential equations with time varying feedback parameters. The final form of the model has 10 degrees of mechanical freedom and 8 electrical poles, i.e., an 18th order nonlinear differential equation must be solved. This paper will describe the dynamic equations in detail and discuss results of the analysis. An appendix details the state equations used to solve the nonlinear differential equations. This analysis has resulted in the design of a gripper control system capable of providing controlled compliance and reduced finger impact forces while maintaining a quick response and firm grasp.

The technique of dynamic time warping (DTW) is relied on heavily in isolated word recognition systems. The advantage of using DTW is that reliable time alignment between reference and test patterns is obtained. The disadvantage of using DTW is the heavy computational burden required to find the optimal time alignment path. Several alternative procedures have been proposed for reducing the computation of DTW algorithms. However these alternative methods generally suffer from a loss of optimality or precision in defining points along the alignment path. In this paper we propose another alternative procedure for implementing a DTW algorithm. The procedure is based on the well known class of techniques for a directed search through a grid to find the "shortest' path. An adaptive version of a directed search procedure is defined and shown to be capable of obtaining the exact DTW solution with reduced computation of distances but with increased overhead. It is shown that for machines where the time for distance computation is significantly larger than the time for combinatorics and overhead, a potential gain in speed of up to 3 to 1 can be realized with the directed search algorithm. Formal comparison of the directed search algorithm with a standard DTW method, in an isolated word recognition test, showed essentially no loss in recognition accuracy when the parameters of the directed search were selected to realize the 3 to 1 reduction in distance computation.