Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Statistical modeling of contact interaction for telerobotics and haptics Shi, Yunling 1997

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-ubc_1997-0475.pdf [ 3.31MB ]
JSON: 831-1.0051596.json
JSON-LD: 831-1.0051596-ld.json
RDF/XML (Pretty): 831-1.0051596-rdf.xml
RDF/JSON: 831-1.0051596-rdf.json
Turtle: 831-1.0051596-turtle.txt
N-Triples: 831-1.0051596-rdf-ntriples.txt
Original Record: 831-1.0051596-source.json
Full Text

Full Text

Statistical Modeling of Contact Interaction for Telerobotics and Haptics by Yunling Shi B.S., Tsirighua University, 1994 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF M a s t e r o f S c i e n c e in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia August 1997 © Yunling Shi, 1997 In presenting this thesis'in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, Pagree that the Library shall make i t freely .available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Computer Science The University of British Columbia 2366 Main Mall Vancouver, Canada V6T 1Z4 Date: Abstract Force signals provide essential information for manipulation. This thesis focuses on monitoring the contact state of a robot arm (or a haptic device) with the environment. We describe a procedure to segment and interpret force signals by using a statistical, model-based approach. This idea will be useful for high level robot programming, as force signals are not compatible between different devices (robot arm, or haptic device), and costly to transmit. To relate the force data stream to the parameters of interest, we address the criteria of dividing tasks into subtasks by detecting the changes of the observations based on a specific force signal input device, each of the subtasks corresponding to. an auto-regression model. Each hypothesized contact model has an estimator. The observations of position, velocity, and force are input into a collection of estimators. The estimators output the measure of match as well as the residual process to be fed back to the state change detector. So we can detect a subtask and select a model from a set of candidate models to determine the state of contact. In this thesis, we simplify and improve the traditional approach of change detection and estimation to make it suitable for manipulation tasks. The context is also a fundamental to manipulation. The sequence of subtasks ii determines the task structure, and thus the goal of the operator. The Markov process encodes the subtasks and prior knowledge with each subtask state. 111 Contents Abstract ii Contents iv List of Figures vii Acknowledgements x Dedication xi 1 Introduction 1 1.1 Manipulation Modeling and Identification . 2 1.2 Approach . . . 2 1.3 What Can Be Achieved Using This Method . 4 1.4 Thesis Guide 5 r 2 Overview 6 2.1 Feature Description and Detection . . '. 7 2.2 History for Manipulation Modeling and Detection 8 2.2.1 Thresholding in Feature Description and Detection 8 2.2.2 Trajectory Tracking 9 iv 2.2.3 Context Estimation . 10 2.2.4 Constraint Estimation 11 2.3 Other Related Detection Works 12 2.3.1 Speech Signal Recognition 12 2.3.2 Fault Detection and Diagnostics 13 3 Experimental Setup 15 3.1 Hardware Support 15 3.1.1 A460 Robot Arm . .' 15 3.1.2 Control Interface 16 3.2 Haptic Interface • • • 16 4 Sequential Hypothesis Matching - General Theory 19 4.1 Auto Regression Model - 19 4.2 Change Detection and Data Segmentation 23 4.2.1 Autoregression Based Change Detection 23 4.2.2 Change Detection with Knowledge of Mean 25 4.2.3 GLR (Generalized Likelihood Ratio) Algorithm . . 27 4.2.4 Kullback Divergence Test 29 5 Manipulation Subtasks 31 5.1 Introduction . 31 5.2 Criteria for Subtask Definitions 33 5.3 Subtasks 34 5.3.1 Non-Contact Model 34 5.3.2 Static Contact Models 35 5.3.3 Motion Contact Models 37 v 5.3.4 Advanced Contact Models 39 6 Task Segmentation and Identification 47 6.1 Introduction • • 47 6.2 Signal Properties and Measurements 47 6.2.1 Probing Flat Surface 48 6.2.2 Preprocess 48 6.2.3 Parameter Estimation 51 6.2.4 Changing Estimation 54 6.2.5 Segmentation 55 6.2.6 Recognition 56 6.2.7 Result 57 6.3 More Experiments 57 6.4 Context and Constraints 59 7 Conclusion and Future Work 67 7.0.1 Conclusion 67 7.0.2 Future Work 68 Bibliography 70 Appendix A Forward and Backward Procedure 74 Appendix B Viterbi Algorithm . 7 6 Appendix C Baum-Welch Algorithm ' 78 vi List of Figures 1.1 Future Application 4 3.1 A460 Robot Joints 16 3.2 Control Diagram 17 3.3 Control Interface for A460 . • 17 3.4 Pantograph 18 3.5 System Connections for Haptic Device 18 4.1 Basic Input-Output Configuration 20 4.2 Definition for the Windows of Estimation M 0 , MQ, and M i 29 r* 5.1 Sample Force Signal in Time (a) and Frequency (b) Domain. Sampled at 100Hz, subsampled at 33Hz. 658 samples of force signals range from -20.2N to 0.8N 40 5.2 Rest in Free Space. Sampled at 100Hz, subsampled at 33Hz. 133 samples of force signals range from -0.61N to 0.05N in Z direction (Calibration required). 41 vii 5.3 Moving in Free Space. Sampled at 100Hz, subsampled at 33Hz. 180 samples of force signals range from -1.6N to 0.7N in Z direction (Cal-ibration required) 41 5.4 Press in X(Y) Direction (Time (a) and Frequency (b) Domain). Sam-pled at 100Hz, subsampled at 33Hz. 180 samples of force signals range . from -5.0N to -1.3N in Y direction 42 5.5 Press in Z Direction (Time (a) and Frequency (b) Domain). Sampled at 100Hz, subsampled at 33Hz! 667 samples of force signals range from -9.6N to 0.7N in Z direction 43 5.6 Impact (Time (a) and Frequency (b) Domain). Sampled at 100Hz, subsampled at 33Hz. 11 samples of force signals range from -19.4N to 1.1N in Z direction. 44 5.7 Sliding over Flat Surface (a) and after Chebyshev Filter (Order=15) (b). Sampled at 100Hz. Subsampled at 33Hz. 100 samples of force signals range from -13.5N to 0.3N in Z direction 45 5.8 Sliding over Ragged Surface (a) and After Chebyshev Filter (Or-der=15) (b).n Sampled at 100Hz. Subsampled at 33Hz. 82 samples of force signals range from -14.0N to 0.9N in Z direction. A bump of 0.5cm wide is in X - Y plane 46 5.9 Two Ragged Shapes that Might Generate Similar Force Signal Re-sponse 46 6.1 Diagram for Segmentation arid Identification without Knowledge of Context and Constraint 49 6.2 Sample Force Signal of Probing the Flat Surface 50 6.3 Definition of Thresholds for the Detection of Contact (From C to D) 51 viii 6.4 Two Identical Models with Different Size of Windows. The length of the first model contains 200 force signal samples, the second model contains 40 samples. The errors for simulation in autoregression mod-els are: 1.048 and 3.081, respectively. . ." 53 6.5 Measurement Un for Force Signal of Figure 6.2. 7 local maximums which represent positions of changes are detected 55 6.6 Result for Segmentation and Recognition of Hypothesis, (a) is the original force signal with recognition result, (b) is simulation based in the autoregression parameters of hypothesis. The similarity of original data and simulated data reveals the success in segmentation and modeling : 62 6.7 Changing Magnitude of Vibration. The probe of robot arm press the side of a cube and the magnitude of vibration dies out gradually. . 63 6.8 Changing Terrain. The probe of robot arm slides over a surface with a bump of 0.5cm wide, (a) is the original force signal with segmenta-tion and identification, as well as the simulation using autoregression model, (b) is the filtered force signal through Chebyshev Filter. . . 64 6.9 Changing Stiffness. The probe of robot arm slides over a surface made of half wood and half sponge 65 6.10 Left-Right H M M Model. Circles represent states 65 6.11 Diagram for Recognition Using H M M Model 66 ix Acknowledgments I would like to take this advantage to express my special thanks to my supervisor Dr. Dinesh Pai for providing an environment allowing the opportunity to pursue in-teresting research ^ directions, and for providing valuable suggestions throughout the research and writing of this thesis. I am very grateful for the instructive discussion with him, and the constructive guidance from him. Many thank to my second reader Dr. David Lowe, for the time he spent reading and reviewing my work. His comments and suggestions were very helpful and valuable. In particular, I must thank Dr. John Lloyd, for providing me with the control software for data collecting and analysis. Thanks also to Rob Barman and Stewart Kingdon for their generous help and support. Y U N L I N G S H I The University of British Columbia August 1997 x To my. family xi C h a p t e r 1 Introduction The modeling of manipulation, and identification for haptic signals can be useful in the area of telerobotics, training, and prototyping of robotic systems. For instance, in telerobotics, from the local control of a robot manipulator, human operators can control or teach a robot by demonstrating a task. In this process, we can either send to the remote robot force signals or concise commands obtained from signals. The first solution is not desirable because (I) the signals themselves could vary greatly from device to device, (II) it is expensive to send all the data to the remote end (III) latency generated by the network will deform the signal. Therefore, the translation from force signals to commands understandable by the remote robot is essential in accomplishing this task. This thesis discusses algorithms for the modeling and identification of manip-ulation tasks, in particular contact states. The system treats force signals as input, and outputs contact states. The general criteria for the definition of device based phases of manipulation are addressed, and an example for a specific robot arm is presented. Further identification can be done using context and constraint models 1 such as Hidden Markov Models or Petri Nets. 1.1 Manipulation Modeling and Identification The role of manipulation modeling and identification is to provide feature descrip-tions and control primitives. Most of the research in teleoperated manipulation is of one of three types: • Traditional approaches rely entirely on a human operator to provide visual perception and control; • Threshold based feature detection approaches evolved next, which use sen-sory feedback such as weight or size of objects; • In recent years many people applied ideas that are widely used in other areas, such as speech signal processing or fault detection, to achieve better under-standing and control of manipulation signals. Among them, two works related to this thesis are Hidden Markov Model based task segmentation by Hannaford, and constraint estimation by Eberman. Both approaches are autoregression based because this technique is not complex and is powerful in doing the dynamic system modeling. .1.2 Approach Our goal is to distinguish the contact state sequence of a series of actions, and thus recognize the type of task a human operator is supposed to accomplish. The knowledge that we can acquire of those actions is forces and positions sensed by a certain sensor/sensors at the tip of the input device. The basic idea of sensing manipulation tasks is to determine the "Contact 2 Phase" for a signal according to the measurement of contact force and position. In order to monitor this process, a dynamic system measurement approach is required. This approach should be able to compare two pieces of signals, separate different phases, and give proper explanation to each phase according to hypotheses. Many powerful analytical tools are available. Our choice is a mechanism which can change this non-stochastic problem into a parametric stochastical prob-lem, more precisely, an autoregression model based general likelihood ratio and sequential hypothesis estimation. It is applied to scan the signals sample by sample, detect changes of states of the system, report the locations where changes occur, and estimate the error of the result using residue of the fitness of autoregression parameters. The result of diagnosis is fed to a recognizer to identify the type of contact for each piece of signal. This is a purely time series based algorithm, which unifies the mechanisms of segmentation and recognition, and can work either on-line or off-line. Autoregression based change detection approaches are not designed for a spe-cific kind of tasks. Its generality makes it neglect some features that are interesting to us. Another problem occurs to us is, some artificially introduced factors have an effect on the process of comparison of phases, which is not desirable. The main contributions of the thesis are: • We establish general criteria for the definition of device based contact phases, and provide an example for A460 robot arm. In experiments, we notice the importance of making use of the whole history of the force signals, the flexibility of the autoregression model, as well as physical properties of the tasks for intuitive match. < • We simplify and improve the traditional approaches of change detection 3 and estimation to get better results for this specific type of experiment, and discuss the method to choose parameters according to the properties of signal. 1.3 What Can Be Achieved Using This Method In future work, after we fully understand the potential of haptic technology, we will go beyond simple keyboard or mouse style robot programming, and produce creative frameworks of interactions between humans and robots. For example, in a virtual environment, a human operator would use a haptic device to contact virtual objects and perform manipulation tasks. The force signals generated from simulating the physical properties of objects (such as stiffness and damping) can be recognized, and thus the manipulation tasks can be abstracted in commands. This application is illustrated in Figure 1.1. Human Operator Task Demonstration Haptic Device Statistical Contact Model Task Analyzer Concise Commands Remote Robot Figure 1.1: Future Application 4 1.4 Thesis Guide Chapter 2 provides background for manipulation modeling and recognition using haptic devices. Most of the approaches used are of the following kinds: feature detection, context based modeling and detection, and constraint based detection. Modeling in other areas is also studied, such as speech recognition, whose approaches are related to ours. Chapter 3 discusses general contact cues, and introduces the experimental environment of the robot arm that we use. Chapter 4 presents the general theory for a statistical approach for modeling, segmentation and identification. The autoregression model, the General Likelihood Ratio (GLR) test and some related works are surveyed. Chapter 5 describes the criteria to define contact features in terms of manip-ulation phases based on input devices. An example of a subtask system is given. Chapter 6 applies the general theory to develop the segmentation and iden-tification algorithm without knowledge for context and constraint. Some practical issues in the selection and estimation of parameters are illustrated, and some revi-sions are done to the general theory to make the system more efficient and robust. Further recognition using context is also briefly discussed. Chapter 7 concludes the thesis, summarizes the results and provides ideas for future work. 5 Chapter 2 Overview Conventional methods for robot programming are inflexible and require significant expertise. Therefore, people are seeking approaches of teaching robots by human demonstration. . • , Using human actions to guide robot execution greatly reduces the program-ming complexity. The idea is to analyze a given sequence of sensory data for a certain task performed by a human operator, then divide it into constituent parts which can be individually studied, and linked with context. Features are abstracted for the purpose of guiding the robot. A rich history for solving this problem exists, and various situations have been studied, for example, force-based and vision-based observations, low level and high level manipulations. Among them, one of the earliest approach is threshold based feature detection, which guards a motion according to maximum/minimum force or position information; some later methods are-trying to handle more com-plicated cases such as vision guided grasp and rolling tasks, high level manipulation with context and constraints, or tasks that need only limited knowledge or even no knowledge. Our approach uses an easily available observation of force and position sig-nals, and defines general manipulation phases with consideration of specific input devices. Since the autoregression and change detection approach has valuable ap-plications in the area of speech signal recognition and fault detection, related works in those areas are also mentioned in this chapter. 2.1 Feature Description and Detection Most of the sensory information processing systems have certain algorithms elab-orately built for the specific situation or event. The observations could be vision information, force information, vibration information, geometric information, and so on. . The common goal for all those systems is to find out a feature set that serves the purpose of classification and identification ([25]). As for such a system, a model class is an abstract space of models about the world, which is cut into several categories. Statistical methods are used to select good features, build model classes, and perform the recognition on the basis of this model structure. High level feature detection systems would also be highly context dependent, and can update features locally during the procedure of learning. The general theory of finding a good feature is not in the scope of this thesis. But in the following section, some research and experiments on feature description and detection in different areas are discussed and compared. 7 2.2 History for Manipulation Modeling and Detection The challenge of manipulation detection lies in the versatility of the system. Obser-vations monitoring this dynamic system can be gained through vision, force sensors, and position sensors. Specific techniques are generated accordingly. Two main foci are hence the generality of modeling simple tasks, and precision of modeling complicated tasks. 2 . 2 . 1 Thresholding in Feature Description and Detection Feature detection approaches that use intuitively clear thresholds or other basic properties are most widely used approaches, and by far the earliest ones designed to monitor and guide motions. It is relatively simple and general. In this case, command is given to, or information is obtained from a mov-ing robot, when a certain threshold, for example maximum or minimum force is achieved. The work involves both recognition and robot programming. It usually focuses on finding out or using the natural properties of the contact objects, for example, experiments in [9], [32] and [30]. Howe [32] presents an environment identification problem, which collects sensory information during telemanipulation tasks, and automatically segments the data collected during the elaborately designed tasks. Only some basic physical knowledge is required to conduct the motion in order to obtain necessary property information. The state segmentation is done by comparing some single data stream or combined data in certain forms to some empirically set thresholds. This is an easy yet effective way to understand the remote environment, for example, in conducting a peg-in-hole task. The limitations of this kind of techniques are also obvious. For instance, 8 the force is very noisy and changes from device to device, and from experiment to experiment. Therefore, the threshold is hard to select and the result can hardly be precise enough in many cases. Another prospective weakness is, this test is only suitable for simple examples. For complex situations, every possibility needs to be analyzed individually. 2.2.2 Trajectory Tracking Geometric information is a common choice for manipulation detection. One ap-proach of teaching robot grasping tasks by human demonstration is to use solely vision and graphical means. It defines the sketch of an action, namely, a 3D graph-ical structure of contact points between the hand and the grasped object and uses a glove-like device with sensors attached to supply the data. [26] presents the method of segmentation of grasping task sequences based on human hand motion. In this work, the grasping task is composed of three basic phases: pregrasp phase, static grasp phase, and manipulation phase. The fingertip polygon (preshape) and the speed of hand movement are analyzed to distinguish states in a task, for example: approaching object, grasping object, manipulating object, placing object, and departure. The advantage of this method is: it inherits ideas of vision and graphical based gesture detection and motion detection which have been studied for a long period. But on the other hand, some difficulties in solving geometric problems also „ arise in this work, for example, the variability and complexity. It turns out that those approaches are desirable in dealing' with tasks such as grasping, where more geometric information is involved, but are not quite flexible, especially when working with abstract constraints. 9 2.2.3 Context Estimation One of the main approaches for high level analysis of manipulation tasks is to take advantage of task structure. Hidden Markov Model, which contains stochastic func-tions of Markov nets, is widely used for this purpose. The complexity is moderate when the size of task set is small or medium. Several experiments have been developed in [22], [21], [20], and [27]. The methodology is fairly standard. The sensory signal such as force and/or torque data arise from interaction with the environment, the Markov process encodes the subtask sequences and the structures. The observation densities encode expected sensor signals. The setting up of the model is either random or based on some engineering knowledge of the tasks. The model is trained using the Baum-Welch algorithm, and the model is refined using Viterbi algorithm. The recognition is done by applying Forward Procedure. More details are discussed in Appendix A, B, and C. The use of Hidden Markov Model has contributed greatly to advance recog-nition results. This approach is broadly applicable to various cases under different situations. However, most of experiments done so far using this algorithm are simple, the size of the task set is small, and not many unique properties for manipulation tasks are studied under this model. One factor taken into account is the complexity of initializing the model and learning based on specific input device. The initialization for H M M is addressed in Chapter 6. Another reason lies in some limitations of this model ([31]). One major limitation is that H M M assumes successive observations are independent. Another 10 limitation is that H M M assumes the individual observation distribution parameters can be well represented using Gaussian densities. 2.2.4 Constraint Estimation As another category of high level recognition, constraint estimation has many simi-larities with context estimation. Some of the constraint estimation approaches also evolve from the ideas of Hidden Markov Models. In constraint estimation, more properties of the tasks themselves are taken into consideration, as it assumes a much higher probability of successive states. One major difference between Hidden Markov Models and prospective constraint estima-tion approaches is that, the latter one is not limited to independent consideration as states in Markov graphs, but allows correlation measurements between each state. The idea is to set up constraints of dynamics, for example in configuration space ([16]), or in the types of contacts ([12]). A map of the possible manipulations is produced from measurements of the contacts. Each node in the map represents a local constraint. In this approach, not only the contact information is required, but also geometry information such as the task configuration space or terrain of contact surface is necessary. Decision making based on constraints is one of the most robust methods available. More over, complicated geometric shape can be coupled to the object or j the environment. But good knowledge of the tasks and complete study for each specific situation is essential in this technique. 11 2.3 Other Related Detection Works The method we adopt is related to techniques that have been tested in the area of speech signal processing and failure detection. All these applications are based on the change detection model originally proposed by Wald ([36]), and studied by Basseville ([5], [4], [7], [8], and [6]), and Willsky ([37], [38]). 2 . 3 . 1 S p e e c h S i g n a l R e c o g n i t i o n Speech signal processing is a topic of long history. One category among the speech recognition approaches is based on autoregressive change detection method which is related to our work. In [2], Andre-Obrecht presented an approach to automatic recognition of continuous speech using an automatic segmentation of the signals into phonemes. This segmentation step is the first and the key step for the recognition. This al-gorithm is not the most natural in doing speech recognition as it assumes almost no knowledge of the signals. But it is simple and turns out to be successful. The segmentation module decomposes speech assuming autoregressive behavior of each state (phoneme) and measures the distance between to estimated states by applying likelihood ratio or evolved Kullback Divergence Test. Ordinarily, the likelihood ratio is not sufficient to ensure robust feature ex-traction and recognition, because it only serves'in the level of providing the prior probability of a world property, and is not able to raise higher posterior probabil-ity [6]. This measurement is explicit in representing intuitions from observations, and is implicit in representing a non-accidental feature. Speech signals are quite similar to the manipulation force signals in shape and behavior. However, there are still great differences between the two: 12 One of the major differences rests with the clear definition of phonemes of speech signals. There is obvious repeatability for speech signals (especially vowels), or say, the pattern of frequency which makes those phonemes very easy to process and recognize. Another difference is that speech signals tend to last for at least several periods, but this is not always true for some manipulation states, and makes the choice of parameters difficult in handling manipulation tasks. 2.3.2 Fault Detection and Diagnostics Another challenging task for computer-monitored system is to detect and diagnose faults in complex process plants. This problem consists of three parts, namely, fault detection, which indicates there is something wrong with the system; fault isolation, which finds out the precise location where fault occurs; and fault identification, which determines the type and size of the fault. The first two components are considered essential in the whole problem, and their approaches are closely related to our work. A survey of techniques to detect and isolate faults in technological systems is done in [19]. The methods are based on analyzing the signature of the mathematical models of the systems. As explained in [19], sensory measurements are compared to analytically obtained values for particular variable. The model is used to describe the relationship for present and previous measurements. The difference, or the residue, is checked and a logical pattern (signature) is generated for the purpose of fault identification. Basically, the general idea used is very similar to that in speech recogni-tion. One unique issue of this problem is that the fault behaves differently from 13 normal behaviors, while there is no corresponding component in speech recognition. Therefore the effect of noise becomes a specific consideration. 14 Chapter 3 Experimental Setup 3.1 Hardware Support 3.1.1 A460 Robot A r m The robot arm we use is an A460 industrial robot system, which is a Puma style, six joints (axis) robot. It is composed of an RSA-20-00T articulated robot arm without shoulder offset, and a RSC-13-30T Robot System Controller. The DC servo motors of A460 have harmonic drives (1-100 gear ratios) [1]. The articulated arm of A460 has five main components: the base, the shoul-der, the upper arm, the lower arm, and the wrist; and thus has six degrees of freedom, which are: the waist, the shoulder, the elbow, the wrist pitch, the wrist roll, and the wrist yaw (See Figure 3.1). A gripper is required to perform its intended tasks. The robot arm has a low level position controller. The position set points are updated at 1 millisecond intervals per joint. Trajectory generation is done at 100Hz for impedance control on a Sparc 5 using Solaris real time features and RCCL [1]. > 15 \ T 5 6 Figure 3.1: A460 Robot Joints 3.1.2 Con t ro l Interface In the application of using A460 robot arm to perform manipulation tasks, the projection of the workspace is the subtraction of two fan-shape areas as shown in Figure 3.3. The small white cross on the left represents the present x and y position of the gripper, the cross on the right represents the z position. During the task, nine channels can be monitored, they are: position, force, and moment in x, y and z direction, respectively. 3.2 Haptic Interface The haptic interface is a 2-dof Pantograph haptic interface designed by Hayward, [23] (see Figure 3.4). It is controlled by a microcontroller and a small on-board network of transputers developed in our lab (see [34] for details). Figure 3.5 shows the system block diagram. The device behaves essentially like a mouse with force feedback, with a workspace of 10cmX 16cm. 16 1 K H z Low Level Position Controller Transputer Trajectory Generator Programming Library Figure 3.2: Control Diagram 17 working space handle Figure 3.4: Pantograph Host (SGI) Geometric M o d e l Handle State Amplifier Handle Controller (T805) Joint Commands Joint State EMDC Current Encoder Pulses Encoder Pantograph Haptic Device Figure 3.5: System Connections for Haptic Device 18 Chapter 4 Sequential Hypothesis Matching — General Theory This chapter looks at a general theory for time-series based system identification and change detection. The system identification problem is to estimate the models. In our experiment, in the haptic signal generating system, the force signal is considered to be the output, the position of the force sensor is the input, and contact types are estimated based on the observations of input and output (See Figure 4.1). The change detection problem is to detect the boundary and the difference between two systems. This algorithm will be applied to separate different actions in one time series, and give proper explanation to each action. 4.1 Auto Regression Model The autoregressive (AR) model is one of the most popular parameter identification model in various science and engineering areas such as signal recognition ([2]), fault diagnosis ([17]), and image processing. As described in [28] and [29], three auto 19 tion: e Innova Position Information: u Dynamic System Force Signal: y Figure 4.1: Basic Input-Output Configuration regression models are commonly used. The simplest one is AR model, which only has a single signal output. In discrete time: A(q)y = e(t) (4.1) or: (4.2) y is ny dimensional output time series, e is white, Gaussian noise. A is a matrix of the size ny X ny: I 01,1 (?) al,2(9) ••• al,ny{q) 0.2,\{l)' a2,2(?) ••• a,2,ny{q) \ (4.3) ^ any,i(q) o,nyt2(q) . . . any,ny{q)' y A(q) = Iny + A\q~l + ... + Anaq~na (4.4) Where akj are polynomials in the delay operator na is the polynomial. 20 If the input signal is taken into consideration, the AR model becomes the A R X model: A(q)y(t) = B{q)u{t - nk) + e(t) (4.5) u is nu dimensional input time series, nk is the delay from input to output. B is matrix of the size ny X nu: ^ 61,1(9) 61,2(9) ••• h,nu{q) ^ B(q) = 62,1(9) 62,2(9) ^ Ky,i(q) KyAl) h,nu(q) ^ny,nu(q) j (4.6) B(q) =B0 + Blq-1 + ... + Bnbq-nb (4.7) Where b^j are polynomials in the delay operator </_1, nb is the polynomial. Another common, but more general model structure is A R M A X (Moving Average) model: A{q)y{t) = B{q)u{t - nk) + C(q)e(t) (4.8) C represents the moving average coefficients, and is a matrix of the size ny X ny: C(q) = { ci,i(?). ci,2(?) C2 , l(?) C2,2(9) c l , n y ( 9 ) c2,ny{q) (9) cny,2(q) . . . (9) (4.9) 21 C{q) = Iny + d q ' 1 + ... + Cncq~nc , (4.10) Where Ckj are polynomials in the delay operator q~l, nc is the polynomial. To perform the estimation, for example, a linear combination of damped sinusoids and exponentials can be used to solve a set of the so-called Yule-Walker Equations. Equation 4.11 is obtained by multiplying both sides of equation 4.2 by delayed y(t) and taking the ensemble expectation of the result, then the Yule-Walker Equations are Equation 4.12. <Pzz(t) i=l -i) v**(o) <pzz(l) ¥>«(!) • ••• ¥>zz(0) <pzz(na-- 1) Vzz{na - 2) h b2 V « ( 2 ) <pzz(na - 1) <pzz(na-2) ... V « ( 0 ) Vzz{na) (4.12) . Several popular techniques are available for the least square A R parameter estimation ([29], [13]): • Yule-Walker method, or the autocorrelation method (the characteristic nature of the process is reflected in its autocorrelation function, which obeys the homogeneous difference equation for the process ([18})). • LSFB, least squares with forward and backward residuals. • LSF, least squares with forward residuals only. • Burg's lattice-based method, a method of "maximum entropy" spectral estimation, using harmonic mean of forward and backward squared prediction errors. 22 • Geometric lattice approach, as in Burg's, except for using geometric mean instead of harmonic mean. To make it easy to study, our system is considered as multi-dimensional input, one dimensional output space, i.e., ny = 1, nu > 1. The recognition work is done in one dimension. 4.2 Change Detection and Data Segmentation In order to monitor dynamical systems, the problem arises of change detection and estimation of the place where change occurs. Instead of using traditional standard likelihood testing, a practical solution is to apply the idea of identification for change detection, setting up a statistical measurement under both hypotheses "no change" and "small change" which provides a global test of changes ([6]). This process decomposes signals into phases which can be labeled and recognized using the same model. 4.2.1 Autoregression Based Change Detection The basic quantity for change detection is the "residue", which is an artificial value. The residue is used to reflect the fitness of autoregression parameters for a piece of signal. Ideally, if the residue is close to zero, a good fit is achieved, and no change occurs during this piece of signal. This approach changes a non-stochastic initial problem into a parametric stochastic problem ([7], [10]). Generally, a stochastic process has a conditional distribution Pe{yn\yn-i, • • •, Vi)-A better hypothesis will be selected from two candidates Ho and H\: H0:9 = 90, (4.13) 23 0 = 0' forO<t<r-l, •Hill1 ~ " . • (4.14) 0 = 0! /or r < t < n. HQ is a constant state without changes. While in Hi, further processing has to be done to decide the location where change occurs, i.e., the value of r. Two procedures are devised: off-line measurement which sets the size of measured data to a constant, and on-line measurement which uses windows of growing size. Off-line measurement is more suitable to study the properties of both signal and the algorithm, and multiple changes are detected during global search. On-line measurement is based on the former one, and it detects each change serially. During on-line detection, a trade-off needs to be made for the delay of report, as this value should be minimized to locate the position precisely, at the same time, it should be large enough to keep a fixed false alarm rate. Our present research is mainly based on off-line detection. Also there are three open problems with a traditional autoregressive change detector ([7]): • First of all, the approach does not work well when the segments to be found are short. We will discuss this problem in Chapter 6 and raise some possible solutions and tradeoffs for our experiment. • Secondly, besides delay, other criteria for the detection should be optimized, for example some inspection cues. •~ Finally; the autoregression model may be of far lower dimension than the dynamic system. In solving this problem, we do some adjustment, e.g., based on similarity of two adjacent segments, after segmentation. Context and constraints are also helpful in eliminating errors. More details are also in Chapter 6. 24 4.2.2 Change Detection with Knowledge of Mean The sequence of observations is y. The mean of observation changes from /IQ to u-i at time r. The goal is to estimate the change time r. This is the simplest case for change detection and is the foundation for other complicated circumstances. y = Vk + ek, n = 0 or 1. ( 4 - 1 5 ) Where UQ if k < r — 1, /**.:( . " (4-16) fi if k > r. ek is the white noise with zero mean. Suppose both means [IQ and fi\ are known, the likelihood ratio between two hypotheses HQ and Hi are: T J ^ l M ( 4 . 1 7 ) where pk is Gaussian probability density of hypothesis k with mean fik-Take the logarithm of Equation 4.17, we have: M r ) = (ft - ^ ) = J f S J W ) (4.19) t=r ^ Where:. v = fii- fi0 (4.20) 25 s / f o i o - / * - £ ) , (4-21) So far, the detector monitoring the change of mean for the time series y is calculated as Equation 4.22. D n = A n(r„).= max5?(/xo,i/) > A (4.22) r < A is an artificially defined threshold. It is a parameter that is very difficult to tune ([2]). In order to reduce the rate of omission, small A has to be chosen with the risk of over segmentation. Similarly, in the Page-Hinkeley stopping rule: <7n = SiVo,* ' ) - min S[(p*,v)>\ (4.23) l<t<n In practice, only fi0 c a n be estimated by calculating it recursively. The jump of mean v and thus the mean \i\ need to be measured during the detection, as well as the jump time r. In this case, the detector becomes: Hi max max5"(// 0, v) > A (4.24) l<r<n v <^ Ho However, the double maximizations is actually a single one because for a fixed r, the maximum value over v is: 26 1 n i/n(r) — argmaxSrivo,^) = n — r + 1 J2(Vt ~ Mo) (4.25) 4.2.3 G L R (Generalized Likelihood Ratio) Algorithm When a model is established for a sequence of observed signals, an abrupt change is an additive disturbance to this model. The GLR algorithm studies the properties of the dynamic system from this view. It supposes that different models/changes generate different effects on the filter innovations, or say, different signatures. GLR is a recursive method calculating the likelihood of any possible event by correlating the innovation with corresponding signatures. The algorithm consists of a single Kalman filter, a matched filter correlation, and a likelihood calculation. Implementation details can be found in [37]. To monitor the observation j / i , . . . , yn, the decision between the two hypothe-ses Ho and H\ is made by the detector given below. The conditional distribution of the observation with respect to its previous values is used. The log-likelihood ratio becomes: Si{r,V90,Pe',VeC) = Elo§ r - l p6'o{yt I yt-i,• • - ,yo) Pe0{yt I i/t_i,:..,!to) n peAvt I yt-u---\yo) Pe0(yt I ?/<-i,...,yo) (4.26) t=r And the GLR test is: 27 max rainmaxmax5"(r)ps0,Po',W1) > A (4.27) l < r < n #o $'0 81 0 < Now let's consider the autoregression case. If Mo is an A R model under the hypothesis of no changes, M i is the AR model after change. The size of window for M i grows gradually. To implement the measurement function as shown in Figure 4.2, the log-likelihood ratio is maximized over r ([7]). 6$, 6'02, and 8\ are the variances for the innovations of the estimated models Mo, MQ, and M i , respectively ([8]). The maximum likelihood estimation of the hypotheses in Gaussian white noise case is given by: 9(W) = arg min £ (yt - £ a i y t . t \ (4.28) tew \ i=i ) where W is one of the three windows of Mo, M0, or M i . *2<w>=mj";Jw£r-|"'M (4-29) where card(x) is the cardinality of the set x. According to Equation 4.28 and Equation 4.29, the log-likelihood for GLR test of Gaussian autoregressive case is as follows: un(r) = n log §1 - [(r - 1) log(?02 + (n - r + 1) log§*] (4.30) A simplified measurement for Equation 4.30 is to fix the window size N — n — r + 1 for M i ([3]). So the change time can be detected at the second step. This measurement generates a result that is very close to Equation 4.30. 28 M , r-1 n-1 M, Figure 4.2: Definition for the Windows of Estimation Mo, M0, and Mi un (r) = n log 91 - [(n - N) log 0O2 + N log Of] (4.31) 4.2.4 Kullback Divergence Test The GLR algorithm is the benchmark for other measurements of the distance be-tween hypotheses Ho and H\. In Kullback Divergence Test ([7]), which is a more complicated test, the mutual entropy between two conditional distributions of observations is taken into account. The advantage of Kullback divergence test over GLR algorithm is obvious in real situations. Generally, the distance measurement for Kullback Divergence Test is: K\ (r> Pe0 ,Pe1) = J P90 (Vt I yt-i, • • •, yo) log poi(yt I y«-i,••-.!/()) P90(yt I yt-i,• • - ,yo) dy log P0i(yt I y t _i , . . . , yo) (4.32) Pe0(yt | y t-i,...,y 0) In the autoregressive Gaussian white noise case, the distance measurement becomes: 29 Where e is the innovation for the autoregression estimation: (4.33) A = Vt - Ei=i ak,iVt-i k = 0 or 1 (4.34) An interesting property of Kullback divergence measurement is its condi-tional drift is a symmetrical function of pg0 and p$1. This means there is no bias of looking for changes from model I to model II, and in the reverse situation. The symmetrical property will be useful in the further discussion in Chapter 6 of making the system simpler and more stable. 30 Chapter 5 Manipulation Subtasks 5.1 Introduction The nature of the force signal is determined by the type of contact and the properties of contact objects. With a force sensor (in our experiment, a 3 axis force sensor attached to the tip of the robot arm [1]), a great amount of information is available to us from the sensed forces. The magnitude of impulses of signals reflects the asserted force. The frequency of the pulses reflects the physical properties of the contact objects(Figure 5.1(a)). The spectrum of the signal detected has large energy around the contact event with a persistent residual at 7Hz which is the frequency of the controller of the robot (Figure 5.1(b)). In this chapter, we will begin with a general discussion of contact tasks. Ordinarily, a contact task, such as typing, pushing, or plugging-in, consists of several subtasks. The subtasks are recognized mainly based on a sensing-centered paradigm. Subtasks are defined based on event behaviors, like the source of the signals and source characteristics. The properties of every force signal are determined, the 31 changes when new events occur are detected, and new models are selected from candidate model set. This approach is not based on any particular task models, so it could be applied to all kinds of tasks. A separate context control system such as Hidden Markov or Petri Net process controller can be constructed on the top of the sensor-centered paradigm if necessary. In terms of task recognition, some previous works (e.g., [35] [14]) addressed vision based approaches. Those approaches are applied to manipulation tasks with obvious motions. The tasks are segmented and recognized through position and velocity information. Some other works that focus on trajectory tracking like [26], segment the task sequence into pregrasp phase, grasp phase and manipulation phase, each phase acquires speed and grip aperture profiles for individual analysis. There are also a lot of works on surface array sensors and using these sensors to obtain geometric information from static measurement [24]. Generally speaking, all the above works use, or essentially treat, the sensors as a primitive form of vision. A creative work for contact event discrimination is done by Eberman [16], in which 4 contact events are defined: impact model, slip model, non-contact model, and grasp model. Our interests are on both the geometric structure of the surfaces, and the contact events. The idea of sequential decision theory of [16] is inherited, some changes are made, and a finer subtask division is chosen based on our experiment. Criteria for the division and details for each subtask are addressed in the following sections. The subtask set is organized as below. A grasp model is not included in our experiment because no force is generated by the robot arm in this case. • Non-Contact Model • Contact Models 32 • Static Contact Models • Motion Contact Models 5.2 Criteria for Subtask Definitions The method is to make the decision of segmentation and recognition using the whole history of the force signal instead of an instantaneous value of measured signals. Even without any prior knowledge of the task input, the signal of time series alone provides plenty of contact event information. Some criteria for the definitions of subtasks are: • For recognition, the pattern of each hypothesis should cluster and have large enough distance between.each other. Segmentation requires discontinuities or obvious changes occur when those features, e.g., whiteness, mean, frequency, and envelope, are tested. In our experiment, specifically, different mathematical models are prepared for each hypothesis. • Scaled signals, either in magnitude or frequency, should not have effects on hypothesis selection. Apparently, pushing a heavy object along a flat surface should be recognized as a same model from pushing a lighter object in the same way. • Each subtask should have unique physical properties and intuitively match the physics of manipulation. This requirement is not theoretically necessary, but is greatly helpful in defining a concise subtask set, and constructing high level control diagram. Actually, it turns out that a well-defined subtask always has relationship with the real physical world. Those physics properties also furnish us with essential knowledge for simulation, which is the reverse function of recognition. 33 • The granularity of the division of subtasks is also an important criterion. The results of segmentation and sensor-centered matching will be fed to high level context controller such as Hidden Markov or Petri Net process controllers for the recognition of complicated tasks. Therefore, the complexity of those controllers has to be taken into consideration [25]. • The definition of the set of subtasks should be flexible and be able to expand when we upgrade our system, e.g., to devices with higher degree of freedom. • In order to achieve remote robot control, since commands are sent in the unit of tasks, subtasks set for different devices are allowed to vary from each other. 5.3 Subtasks The category of subtasks is based on the A460 robot arm we use for the experiment. This robot arm has some limitations in dexterity because of its structure. But on the other hand, our research is able to focus on more fundamental contact events. This robot arm senses force through intrinsic contact sensor in X , Y, and Z directions. This is analogous to human exploration using a rod. Our goal is to make the subtasks match human performance in this type of exploration. 5.3 . 1 Non-Contact Model Non-contact model, or free motion model, includes both the states of rest and moving the robot arm in free space. Examples of non-contact strain signals of rest or motion are shown in Figure 5.2 and Figure 5.3. Although the robot arm does not contact with any object, there is still background vibration which is mainly white noise. The white noise is of normal distributions, with most of the values fall around zero (or a certain small base value). 34 There are two non-contact hypotheses for static(i?o) and motion(//i) states, respectively. The parameters of mean (/z) and standard deviation (S) for each of them are different from experiment to experiment. Therefore, calibration is needed at the beginning Of every single experiment. N(no,4) (H0) (5.1) iV(MoX) (Hi) (5.2) 5.3.2 Static Contact Models Static contact models refer to two kinds: impact and press. The latter one includes: press in X and/or Y directions, and press in Z direction which is along the direction of gravity. Contact is modeled in different directions because the A460 robot arm is an active system, motions in different direction are controlled by different joints, and have different behaviors. Ordinarily, different devices can generate different signals based on their unique mechanism, even if they are doing the same task. That also makes the idea attractive of defining device-based subtask set, generating manipulation models from haptic input, and sending task commands instead of real data for control purpose. X / Y - a x i s Contact Static contact force in X or Y direction' is collected by pressing the side of a cube(Figure 5.4(a)). From the frequency domain (Figure 5.4(b)), we find the signal is mainly composed of two parts: DC and the frequency of the robot controller. A proper model for this kind of contact is an AR model: 35 f(t) = abC22aiy(t-i) + e(t)) + G (H2) (5.3) i = l f(i) = y(t)+G e(t)~N(0,a2) (5.4) / is the force signal, a is the amplitude of the vibration. Tt is decided by the properties of the contact object. Generally speaking, because of the influence of impedance, softer materials such as sponge will have smaller a, harder materials such as metal will have larger a. b is an exponential decay factor. In the task of knocking at a wall, after the sharp rises of the force (impact), the sensor continues to ring for an extensive period, and the vibration will fade gradually to zero. G is the proposed asserted force. Z-axis Contact The A460 robot arm is controlled using an active compliance algorithm system with six joints, the motion in each direction is highly dependent on the combination of joints. Contact events have different behaviors for different directions. This is caused by the resonance of impedance control, which is a well know problem of active systems. (Figure 5.5). In the probing event, the vibration will not die out as it does in other directions. A proper model for this contact is an AR model: f(t) = aC£aiy(t - 0' + e(t)) + G (H3) (5.5) i=l f(t) = y(t)+G e(t)~N(0,a2) (5.6) / is the force signal, a is the amplitude of the vibration, same as static contact model in X and Y direction. G is the proposed asserted force. 36 I m p a c t Impact, or initial contact is a very special kind of contact decided by many factors such as the shape of the objects, the inner structure of objects, and the contact point. Generally, it is a very short event. During this event, the energy will in-crease abruptly, reach a peak, and decay to a stable value shortly (Figure 5.6(a), Figure 5.6(b)). This is one of the reasons why it is hard to deal with. Another reason is the signal has large values for every frequency in a certain bandwidth, or say, it is a kind of noise in this bandwidth. Up to now, there are still no models that can simulate impact satisfactorily. An initial model of impact is designed in [15], which uses a spring-damper model and considers each impact between two objects M i and M 2 is an inelastic collision with a coefficient of restitution. But even this model does not work nicely as its shape differs from the original signal, and it does not fade as quickly as real data. The result for the A R model has the same problem. However, for the purpose of identification, impact model is not very impor-tant, as impact occurs only during two cases: impact only, and contact. In the first case we find a short energy release process. In the second case, impact status is not a major concern to us as what we want to learn is the stable contact, and we also know impact always happens at the very beginning. In practice, we are able to separate the impact event from other states, but we still consider it a kind of static contact model. Whether it is a hypothesis of H 2 or H3 is decided by the subtask that follows. 5 .3 .3 M o t i o n C o n t a c t M o d e l s Data for these models are collected by pushing the end point of the robot arm along a surface of an object. In contacting with a surface without obvious textures, 37 the acuity of the force sensor is not able to correlate the individual micro surface details [33], and thus detect the micro structure of the surface. Therefore, we divide the motion in contact into two kinds according to the fineness of a texture: even-surface-contact (Figure 5.7(a)) and ragged-surface-contact (Figure 5.8(a)). Flat surface of most of the objects, such as wood, metal, sponge, are of the first kind. Ragged surfaces are those surfaces that have small bumps or holes that the probe can go through. Test is done on the surfaces in x-y plane, as constant force load is guaranteed in z direction. The surface roughness is a crucial feature for the state of sliding over a surface. This parameter decides the standard deviation of the noise E(t). The model is: i f(t) = a(E aiV{t ~ j) + e (0) + G (H* -and for even and ragged surfaces) (5.7) f(t) = y(t) + G e(t)~N(0,a2) (5.8) The following figures (Figure 5.7(b), Figure 5.8(b)) show the difference in shape for even surface sliding model and ragged surface sliding model. They share the same AR model, but parameters vary greatly. The distance between two models becomes larger when the signals are fil-tered. We can use the filtered signal for further recognition, for example, informa-tion for the geometric shape of the terrain. But notice that some different shapes of terrains may generate similar sliding force signals (for example, in Figure 5.9). 38 5.3.4 Advanced Contact Models The subtask model set could be enhanced in different stages according to the abilities of devices. For example, for a multi-fingered robot, a task like rotating a pop can, or grasping two adjacent sides of a cube, could be broken into several subtasks, each of which is composed of cooperative states of several fingers. Brock [11] [12] used an action-centered paradigm in dealing with these kinds of problems specifically. Due to the limitation of our device, those models are not considered in this thesis, but could be added to the subtask set in future works. 39 3 0 0 4 0 0 t l m e ( s a m p l e ) (a) (b) Figure 5.1: Sample Force Signal in Time (a) and Frequency (b) Domain. Sampled at 100Hz, subsampled at 33Hz. 658 samples of force signals range from -20.2N to 0.8N. 40 SO 80 time (sample) Figure 5.2: Rest in Free Space. Sampled at 100Hz, subsampled at 33Hz. 133 samples of force signals range from -0.61N to 0.05N in Z direction (Calibration required). s o 100 time(sample) Figure 5.3: Moving in Free Space. Sampled at 100Hz, subsampled at 33Hz. 180 sam-ples of force signals range from -1.6N to 0.7N in Z direction (Calibration required). 41 - 1 . 5 -— 2 0 — 1 5 — 1 0 - 5 O 5 1 0 1 5 1 2 0 freq(Hz) (b) Figure 5.4: Press in X(Y) Direction (Time (a) and Frequency (b) Domain). Sampled at 100Hz, subsampled at 33Hz. 180 samples of force signals range from -5.ON to -1.3N in Y direction. . 42 300 400 time (sample) (a) Figure 5.5: Press in Z Direction (Time (a) and Frequency (b) Domain). Sampled at 100Hz, subsampled at 33Hz. 667 samples of force signals range from -9.6N to 0.7N in Z direction 43 5 I , : , , r — r— r time(sample) (a) 6 0 I • 1 • • • 1 so\-4 0 h 3 0 ^ 2 0 \-10h o L • • • • i i I — 2 0 - 1 5 - 1 0 —S O 5 1 0 1 5 freq(Hz) (b) Figure 5.6: Impact (Time (a) and Frequency (b) Domain). Sampled at 100Hz, subsampled at 33Hz. 11 samples of force signals range from -19.4N to 1.1N in Z direction. 44 1 4 ' ' 1 1 1 1 1 1 1 1 ' O 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 Q O 1 0 O time(sample) (a) — 3 . 8 | 1 1 ; 1 1 1 1 1 r Figure 5.7: Sliding over Flat Surface (a) and after Chebyshev Filter (Order=15) (b). Sampled at 100Hz. Subsampled at 33Hz. 100 samples of force signals range from -13.5N to 0.3N in Z direction 45 4 0 S O t i m e ( s a m p l e ) (a) 4 0 5 0 t i m e ( s a m p l e ) (b) Figure 5.8: Sliding over Ragged Surface (a) and After Chebyshev Filter (0rder=15) (b).n Sampled at 100Hz. Subsampled at 33Hz. 82 samples of force signals range from -14.ON to 0.9N in Z direction. A bump of 0.5cm wide is in X - Y plane. Feature 1 Feature 2 Figure 5.9: Two Ragged Shapes that Might Generate Similar Force Signal Response 46 Chapter 6 Task Segmentation and Identification 6.1 Introduction In this chapter we will discuss the segmentation and identification of subtasks as purely time series. Segmentation is done prior to identification. It is a statistically based approach, which scans sample by sample to provide rather accurate bound-aries, and makes sense of those boundaries from the view of physics of motion. The segmented results are fed to the subtask identification engine. This approach can be used in off-line or on-line detection. Context in the form of subtask sequence for certain tasks will be significantly helpful for high level recognition. 6.2 Signal Properties and Measurements This section discusses the process of segmentation without context, using a time-series model. We improve the algorithm addressed in Chapter 4 to'fit our application 47 of robot arm force signals. A simple example is used to explain the approach, and results for various tasks are also discussed. A diagram of the whole procedure is shown in Figure 6.1: The human op-erator uses a haptic device or robot arm to demonstrate the task, the force signals are sensed by the sensor attached to the input device. The force signals are cali-brated, filtered and separated in the preprocess module. The non-contact signals are processed by the standard deviation sensor and recognized. The contact sig-nals are measured using auto-regression models. Contact-states segmentation and adjustment will be done based on the measurement. Then the contact states are recognized according to manually constructed candidate model set. At last both the contact states and non-contact states are simulated with the obtained auto-regressive parameters. The simulations are compared with the original force signals to determine the accuracy of the whole segmentation and identification system. 6.2.1 Probing Flat Surface The task of probing the flat surface is used as an example to show the process of time-series-based segmentation and identification. This is a fairly simple task: we move down the robot arm until it gets contact with a wood table, then we pull the robot arm over the surface of the table, finally we raise the robot arm off the table. It starts from static non-contact state of the robot arm, and ends with the same state (Figure 6.2). 6.2.2 Preprocess The autoregression model is an expensive model. One way to decrease the com-putational cost is to use subsampling to decrease the order of the auto-regression 48 Force Signals; Force Sensor c3 Auto-Regression Models Contact Signals Preprocess Non-Contact Signals Deviation Sensor Auto-Regression Parameters Static Non-Contact States Motion Non-Contact States Measurements Un AR-Based Segmentation Local Maximum States Adjustment States Boundaries! Recognition Static Contact States Motion Contact States Proof Simulation •u o -a -3 c U o A Statistic Approach for Modeling and Identification Figure 6.1: Diagram for Segmentation and Identification without Knowledge of Context and Constraint model. The subsampling rate should retain at least two samples for each period of the highest dominant frequency to meet the Nyquist frequency rule. A practical rate will retain 6-10 samples. In our experiment the signal is sampled at 33Hz. Another way is to cut the amount of data fed to AR engine to minimum. When we study the signal input, we find that a lot of data are not needed for the autoregression segmentation engine, for example, those "silent" signals, i.e., non-contact states. What we need to do is to figure out the position when impact 49 5 I 1 1 1 1 1 1 1 1 r - 2 0 -— 2 5 1 1 1 1 1 1 1 1 1 1 1 O 2 0 0 4 0 0 6 0 0 8 0 0 1 0 0 0 1 2 0 0 1 4 0 0 1 6 0 0 1 8 0 0 2 0 0 0 time(sample) Figure 6.2: Sample Force Signal of Probing the Flat Surface occurs, and the position when contact ends. The task always starts from non-motion state and motion state in free space for calibration. Using very rough thresholds, these two states can be detected during this period. It is not necessary to find the accurate boundaries of the states, because only the middle part of each states is retained to calculate the means and standard deviations. Each sample of later signals will be adjusted by subtracting the mean of non-contact state. Different thresholds and different strategies are used for the beginning part and ending part of each contact-state, because it tends to release large energy at the beginning of each action, and the vibrations die down very slowly. To discriminate the contact events group from "silent" data, as shown in Figure 6.3, we start with a large threshold Ta. If the threshold is exceeded at time A, we trace backward from A until we meet periods of "silent" data at time B. To qualify as "silent", we require that the signal is below threshold T& for at least £1 seconds before B. Then we go forward from B to C which is above a threshold Tc 50 { (|TC| < \Ta\). C is defined as the beginning of a group of contacts. The end of the contact group D is the beginning of a "silent" period (below threshold Tj) longer than time interval t2. To tell the non-motion states from motion states is much simpler. It can either be determined from the position information, or by sliding a window along the "silent" data and comparing the local standard deviations. Figure 6.3: Definition of Thresholds for the Detection of Contact (From C to D) 6.2.3 Parameter Estimation The first few values of autoregression model are used to create the initial conditions. In a certain range, the larger the order of the auto-regression model, the better segmentation result. This is because more information is used. But larger order also increases the calculating time of solving the Yule-Walker Equations. In our experiment, we make a tradeoff between large order autoregression model and fast parameter estimation. Under the sampling rate of 100Hz, the order is set to 4. The first 4 samples that contain most of the energy information are the system initializer. The rest of the signal is the response for this initial condition. There are several ways for the measurement of signal changes. For two-model based solutions, in equation (6.1), there are two windows Mo and M i using windows (l..n) and (r..n), respectively. This is a simplified version for calculating 51 GLR, because the window of M\ is fixed, and the decision can be made in a second step. Equation (6.2) is the Kullback divergence test, with two models each referring to a discrete state: Mo is a long term or global AR model, and M\ is a short term pr local AR model. Equation (6.2) improves equation (6.1) in that it considers the relationship between the model before change and the model after change, hence it has a smoother behavior which leads to a more robust detector. General theory is in chapter 4. There is a problem with both the above approaches in our experiment: when the difference of length between two models Mo and M\ is substantial, the result does not correctly reflect the difference of two states. In equation (6.1), if n — r +1 is of M i . In equation (6.2), the two models are also not compared at the same level, as in the two signal pieces, the short one tends to have worse fit or say, large residue. For example in Figure 6.4, the errors for the two parts are 1.048 and 3.081 although they are of the same event. Our approach uses windows of fixed size for both Mo and M i , which makes the A R models for Mo and M i comparable, and makes the system simpler and more stable as well. In former algorithms [2], the Page-Hinkley stopping rule is adopted to detect the change of the events: un(N) = nlog(a02) - [(r - 1) log(cr02) + (n - r + 1) log(a2)] (6.1) (6.2) small, Mo and M 0 are close, the similarity of M Q and M 0 conceals the state change 52 m o d e l 1 m o d e l 2 Figure 6.4: Two Identical Models with Different Size of Windows. The length of the first model contains 200 force signal samples, the second model contains 40 samples. The errors for simulation in autoregression models are: 1.048 and 3.081, respectively. n Wn = Y,wk (6-3) k=l k=l m a x ( ^ - W'n) > A (6.5) The threshold A becomes a key issue as a wrong segmentation will have effect on later Wns. Another advantage for the new approach is that the measurement is no longer a function of segmentation, so it is more reliable. The choice of the size of windows depends on the sampling rate and the signals themselves. The larger the windows, the more accurate the AR models. But force signals such as impact may only last for one or two periods, this makes it very hard to do the segmentation. In order to avoid under-segmentation, L, the size of 53 windows should roughly equal to the life time of the shortest models. However, in a practical process, a tradeoff has to be made between under-segmentation and inaccurate measurement. Our experiment chose L = 40, which is twice the life time of the impact model. 6.2.4 Changing Estimation The function for changing estimation is a two-model residual-based measurement for dynamic systems. It inherits the format of wn (Section 4.2.4). Windows Mo and Mj are of the same size. In this experiment, they are set to 40 samples. (TQ and a\ are variances of residues of AR models, for which we use the Akaike's F i -nal Prediction Error (FPE) (FPE criterion is defined as an estimation of the mean square error in prediction expected when a predictive filter is applied to another independent observation of the same process) ([29], [39]). e° and e1 are prediction errors themselves corresponding to two different models." The A R model for the system is: Mq)y(t) = B] {q)u\t -nk) + ..+ B?(q)un(t - nk) + e^t) (6.6) i = 0 or 1 for M 0 and M i u3 are input signals, in this example, the position information Therefore, the measurement is: ei(t)^N(0,af) (6.7) 54 i = 0 or 1 for M0 and Mi . u. =.k{i-:H^)W-^ (6-8) Notice that different orders for A and B should be chosen based on the input to avoid singular result for the estimated parameters. For example, the order of input for position in y direction should be set to zero if there is no motion in this direction. The values of Un for the task of probing the flat surface are shown in Figure 6.5. I»7-P 2 pe Figure 6.5: Measurement Un for Force Signal of Figure 6.2. 7 local maximums which represent positions of changes are detected. 6.2.5 Segmentation For.Un, the local maximum is a better criterion than an artificially defined threshold as in Page-Hinkley stopping rule, because variances are in a wide range, and so are the values for Un. Moreover, a value of Un greater than a certain threshold A means 55 this period of data may contain two or more subtasks, but it does not indicate the beginning point of the second subtask precisely. Seeking local maximum in the range of half of the window size L, there are six (No. 2 to No. 7) distinct local maximum values for this example (Figure 6.5). From the end of the non-contact motion state to peak 1 is the stage of impact, this procedure lasts for 0.3sec, with the amplitude of the vibration rises to about 5N immediately and falls down' right away. From peak 2 to peak 3 is a static contact state between the robot arm and the surface. This process lasts for 4.5sec. From peak 3 to peak 4 is the sliding state over flat surface, followed by another static contact state: from peak4 to peak 6. Adjacent states could be combined to one to eliminate noises such as peak 5. The measurement function is still Un, but the size of window changes according to the initial segmentation result. Peak4-peak5 and peak5-peak6 come into one state because these two models are similar and of the same mean. 6.2.6 Recognition The procedure of recognition is to select a model structure from a set of candidates according to a criterion of fit. The candidate contact model set is selected manually, and stored in original signal format. An annoying property for the autoregression model is that it is not invari-ant during translation. For example, the parameters for sine function and cosine function are totally different though their shapes are exactly the same: for sine function, the parameters of A in the order of 4 are: 0, -1.996, 0, 1 for cosine function, the parameters are: -1.3332, 0, 0, 0.3334 This is also a common problem for all correlation based identification ap-56 proaches. A solution is to calculate the mean and period for each model, then discard the offset in the first period. Therefore, the initial conditions of the two models have the same behavior. Signals of the unknown model and a candidate model are pieced together to obtain the values of U N . In order to compare the two models, one of the models has to be scaled in amplitude and time axis, and the remain for the last period of the first model MQ is trimmed to make the transition smooth. 6.2.7 Result In Figure 6.6: The transitions of the states are: • Ho(no motion in free space) —> Hi(motion in free space) • H\ —>• H3(impact) • Hz —> Hz (non-motion contact in z direction) • Hz —> H4 (motion on even surface in z direction) • H4 —r Hz (non-motion contact in z direction) • Hz —> Hi (release) The upper figure shows a simulation using the Gaussian distribution and obtained autoregression models according to hypothesis in Chapter 5. A good sim-ulation result illustrates that these models are a nice fit for the original data, and the segmentation is reasonable. 6.3 More Experiments The approach discussed in the previous part is evaluated in terms of three criteria([15] • Do the segments make sense? 57 • Are the hypotheses the same as we expected? • Could the result be explained given a context? The results were tested in both for each discrete subtask and for more general examples which combine several events- under various circumstances. The basic testing set is applied particularly,for the recognition, in order to evaluate the pattern distances between each subtask. The way to build the testing set is the same as the candidate set. The advanced testing set is applied particularly for the segmentation, in order to evaluate and adjust the setting of parameters such as the size of windows. In the following experiments, some basic changes were performed to judge the flexibility of the models. Figure 6.7 is an example of moving the robot arm and pressing the side of a cube. The detected events in this task include: • i?o(no motion in free space) —> Hi (motion in free space) • Hi —> ^ (impact) • H3 H2 (press in y direction) • H2 —» H2 (press in y direction) • H2 —> ^ (unstable) • H3 —> Hi (release) This is a rather simple example to show how the autoregression model and the measurement of Un handle the exponential decay factor of vibrations. Figure 6.8 is an example of moving the robot arm over a surface with a bump. The detected events in this task include: • Ho(no motion in free space) —>• Hi (motion in free space) • Hi —» ^ (impact) 58 • Hz —> H3(non-motion contact in z direction) • Hz —> H$ (ragged surface sliding) • H5 —> i?4(even surface sliding) • Hi —> Hi (release) . . Figure 6.8(b) is the filtered signal. Compare Figure 6.8(a) with Figure 6.8(b), the boundaries for the ragged surface contacting derived solely from autoregression models and Un turn out to be accurate. Figure 6.9 is an example of moving the robot arm over a surface with changing stiffness, the first half is made of wood, the second half is made of sponge. The detected events in this task include: • Hr,(no motion in free space) —> Hi (motion in free space) • Hi —> /^(impact: wood) . > • Hz —> i?4(even surface sliding: wood) • H4 —> i/3(static contact: sponge) • Hz —> Hi (release) This example shows that an event can match the correct candidate state although it is in a totally different appearance. 6.4 Contex t and Const ra in ts The deficiency of the totally time series based approach is that, it may lose some states, or divide one state into two or more, or have some mismatches. These kinds of errors are very hard to eliminate purely by changing the candidate model set or parameters. Therefore, it is not enough for the time series based approach alone to recognize tasks. Context is essential for this reason. It can do the job from the result of subtask segmentation and matching, knowing the errors and missing 59 observations. In this thesis, we do not utilize context or constraints. However, we out-line the one model that handles context: Hidden Markov Model (HMM), which is also referred to as probability functions of Markov chain. It couples two stochas-tic processes with one of them not observable (Hidden). Several research works ([21], [20], [22], and [27]) adopted this approach to do the high level recognition. The best reference on general theory of this topic is [31]. In our experiment every subtask matches some physical properties. Let the number of states be N for a particular task, and the number of possible observa-tions, or in this experiment, the size of subtask set, be M. The H M M model for a task is: A = (A, B, w): Matrix A;vxiv is the probability of transitions between states: «ij = Pfa = Sjfa-! = Si],-1 < i,j < -N (6.9) Matrix BMXN is the probability of each observation for a certain state: bj(Ok) = P[vk\qt = Sj]t l<k<M, 1< j<N (6.10). 7r is the initial distribution: m = P[qi = Si], 1 < i < N (6.11) As time increases, the index of states increases. Therefore, a left-right model or a Bakis model is an appropriate design for this experiment (Figure 6.10): a i j = 0, j < * (6.12) 60 0 i ± 1 (6.13) 7T 1 t = 1 In application, no jump of more than two states is allowed, so the left-right a uniform distribution is used to set the initial values for A and n. The initial values of B are set by manually segmenting the observation sequences, and averaging each observation within states. Then the H M M model is trained using the observation sequences again to adjust the parameters following the Baum-Welch Algorithm (see Appendix A: Forward and Backward Procedure, Appendix B and Appendix C). To refine the model (e.g., the number of states and codebook for observations), the Viterbi Algorithm derives best matching states sequences from observation sequences. The recognition process is to calculate the possibilities of an observation sequence, given all the candidate models, and find out the best matches among them. The forward procedure is applied to solve this problem (see Appendix A: Forward Procedure). The diagram is shown in Figure 6.11. model becomes: aij = 0, j > i + 2 (6.14) 61 original force signal simulated force signal Figure 6.6: Result for Segmentation and Recognition of Hypothesis, (a) is the origi-nal force signal with recognition result, (b) is simulation based in the autoregression parameters of hypothesis. The similarity of original data and simulated data reveals the success in segmentation and modeling. 62 H3 H3 H2 H2 H1 H1 HO • — « -original force signal simulated force signal Figure 6.7: Changing Magnitude of Vibration. The probe of robot arm press the side of a cube and the magnitude of vibration dies out gradually. 63 original force signal s imulated force signal (a) 3 0 0 4 0 0 t i m e ( s a m p l e ) (b) Figure 6.8: Changing Terrain. The probe of robot arm slides over a surface with a bump of 0.5cm wide, (a) is the original force signal with segmentation and identifi-cation, as well as the simulation using autoregression model, (b) is the filtered force signal through Chebyshev Filter. ' g4 H4 H3 Ho-rn H3 H1 original force signal simulated force signal Figure 6.9: Changing Stiffness. The probe of robot arm slides over a surface made of half wood and half sponge. Figure 6.10: Left-Right H M M Model. Circles represent states. 65 K Training Observation Sequences ATI A,B,n Trainings (Baum-Welch Algorithm) Manual Segmentation 8,(p. P, qT Model Refinement (Viterbi Algorithm) B Hidden Markov Model a,P Forward, Backward Procedure Time-Serial Segmentation Engine Observation Sequence For Unknown Task Probability of Matching a Figure 6.11: Diagram for Recognition Using H M M Model 66 Chapter 7 Conclusion and Future Work 7.0.1 Conclusion This thesis discusses a method of monitoring and analyzing manipulation tasks. Ma-nipulation subtasks (phases) are defined as autoregression models or white Gaussian noises according to the characteristics of input devices. The procedure of segmenta-tion and interpretation uses a statistical, model-based approach to distinguish the boundaries of manipulation states and their properties. As a statistical approach, the interpretation module only gives the probability for each matching states, and this makes it possible for further context and constraint based recognition such as Hidden Markov Model based techniques. A possible application for this technique is in high level robot programming, as a human operator can demonstrate manipulation tasks through haptic devices in a simulated virtual world using, for example, spring-damper models, and the purpose of the human operator can be found out by applying this approach, and abstracted control commands can be sent to a remote robot. In this way, operators are freed from the need of understanding the characteristics for the remote robot, 67 and the chores of providing control details and precise estimation for each action. It is also helpful to decrease the size of the data transmitted to the remote end. One contribution of this thesis is in establishing the criteria for constructing feature-based manipulation phases on the basis of the properties of robots or haptic devices. The divisions of subtask sets are not necessarily the same for different devices, but the control commands based on those divisions are compatible and transferable. The machinery of statistical change detection approach has already had many applications in the area of failure detection, speech signal recognition,, and so on. In this system, another contribution is to simplify and improve the measurement specifically for manipulation tasks, in order to make the system more robust and faster. A demonstration of this technique is implemented on a A460 robot arm. This is an active system with six joints and a 3-D force and position sensor. The experiment shows that we are able to monitor the tasks performed by human oper-ators. This experiment is also transferable to haptic devices whose output force is simulated in the virtual world. 7.0.2 Future Work The experiment conducted based on this statistical method proved that the princi-ple can be used for high level robot programming. Several considerations are also suggested by the experiment. By using an autoregression model, some limitations are introduced. For example, the Yule-Walker Equation may have no solution or have multiple solutions, which will cause trouble in estimating the autoregression parameter. One solution to decrease the possibility of singular results is to add small artificial noises to 68 those signals that seem to be unchanged during a period. Another choice is to filter out stable signals using another module and only pass the filtered signals to autoregression estimator. We have tried both ways in our approach but we can not totally eliminate singular results as there are still cases applicable other than stable signals. Another consideration is based on the properties of the force signals. Autore-gression models may not be the most suitable ones for many devices because of, for example, low accuracy of sensor, low sampling rate, or high dimension of dynamic system. If that is the case, the model may have to be changed and more engineering characteristics need to be taken into account. Finally, to fully exploit manipulation models, more complicated phases or phase groups such as multi-fingered grasp, and phases with great uncertainty such as apply "wrench till tight" need to be completely studied. In order to assist and simplify the force-signal based recognition, the utilization of geometric and graphical information will also be essential, and valuable experiences can be found in research in other areas such as computer vision. 69 Bibliography [1] A460 series small industrial rotob system, technical manual. [2] Regine Andre-Obrecht. A new statistical approach for the automatic segmen-tation of continuous speech signals. Transactions on Acoustics, Speech, and Signal Processing, 36(1):29-40, Jan 1988. [3] U . Appel and A. V. Brandt. Adptive sequential segmentation of piecewise stationary time series. Information Sciences, 29, 1983. [4] M . Basseville. On-line detection of jumps in mean. Detection of Abrupt Changes in Signal and Dynamical Systems, 1986. [5] M . Basseville and A. Benveniste. Sequential detection of abrupt changes in spectral characteristics of digital signals. IEEE transaction on Information Theory, IT-29(5):709-724, September 1983. [6] M . Basseville, A. Benveniste, and G. Moustakides. Detection and diagnosis of abrupt changes in model characteristics of nonstationary digital sigmals. IEEE transaction on Information Theory, IT-32(3):412-417, May 1986. [7] Michele Basseville. The two-models approach for the on-line detection of changed in ar processes. Detection of Abrupt Changes in Signal and Dynamical Systems, 1986. [8] Michele Basseville. Detecting changes in signals and systems-a survey. Auto-matica, 24(3):309-320, 1988. [9] R. Bolles and R. Paul. The use of sensory feedback in a programmable assembly system. Technical report, Stanford AI Laboratory, 1973. [10] P. Bouthemy. A maximum likelihood framework for determining moving edges in image sequences. Research Report IRISA, 1987. 70 [11] D. L. Brock. Enhancing the dexterity of a robot hand using controlled slip. Technical Report TR992, MIT A l , 1987. [12] D. L. Brock. A sensor based strategy for automatic robotic grasping. PhD thesis, MIT, Department of Mechanical Engineering, 1993. [13] P. M . T. Broersen and H. E. Wensink. On the theory for autoregressive pro-cesses. In ICASSP'92 Acoustics, Speech & Singal Processing Conerence, vol-ume 5, 1992. [14] L. W. Campbell, D. A. Becker, A. Azarbayejani, A . F. Bobick, and A. Pentland. Invariant features for 3-d gesture recognition. Technical Report TR379, MIT Media, 1996. [15] B. Eberman and J. K. Salisbury. Segmentation and interpretation of temporal control signals. In Experimental Robotics I, First International Symposium, Kyoto, Japan, 1993. [16] Brian S. Eberman. Contact sensing: A sequential decision approach to sensing manipulation contact features. PhD thesis, MIT, 1995. [17] Paul M . Frank. Fault diagnosis in dynamic systems using analytical knowledge-based redundancy-a survey and some new results. In Proceedings of IF AC /IMAC/IF ORS International Symposium on Advanced INformation Pro-cessing in Automatic Control, Nancy, France, 1989. [18] Arthur Gelb. Applied Optimal Estimation. Ayalytic Sciences Corporation, 1979. [19] Janos J. Gertler. Survey of model-based failure detection and isolation in com-plex plants. IEEE Control Systems, pages 3-11, Dec 1988. [20] B. Hannaford. Hidden markov model analysis of manufacturing process infor-mation. In Proceedings IROS 1991, Osaka, Japan, Nov 1991. [21] Blake Hannaford and Paul Lee. Multi-dimensional hidden markov model of telemanipulation tasks with varying outcomes. In Proceedings of System , Man and Cybernetics, 1990 International Conference, 1990. [22] Blake Hannaford and Paul Lee. Hidden markov model analysis of force/torque information in telemanipulation. The International Journal of Robotics Re-search, 10(5):528-539, Oct 1991. 71 [23] V. Hayward, J. Choksi, G. Lanvin, and C. Ramstein. Design and multi-objective optimization of a linkage for a haptic interface. In Proc. of the Fourth Workshop on Adv. in Robot kinematics, 1994. [24] R. D. Howe and M . R. Cutkosky. Touch sensing for robotic manipulation and recognition. MIT Press, 1991. [25] Allan D. Jepson and Whiteman Richards. What makes a good feature. Sup-ported by NSERC Canada, IRIS Canada and CIAR. [26] S. B. Kang and K. Ikeuchi. Determination of motion breakpoints in a task sequence from human hand motion,. In Proc. IEEE Int'l Conf. on Robotics and Automation, San Diego, CA, May 1994. [27] Christopher Lee and Yangsheng Xu. Online, interactive learning of gestures for human/robot interfaces. Technical report, C M U the Robotics Institute, 1996. [28] Lennart Ljung. Theory and practice of recursive identification. MIT Press, 1983. [29] Lennart Ljung. System Identifacation Toolbox, For Use with Matlab. The Math Works Inc., 1993. [30] Karon E. MacLean. The "haptic camara": A technique for characterizing and playing back haptic properties of real environments. In Proceedings of the ASME Dynamics Systems and Control Division, volume 58, pages 459-467. ASME, 1996. [31] Lawrence R. Rabinar. A tutorial on hidden markov models and selected ap-plications in speech recognition. Proceedings of the IEEE, 77(2):257-273, Feb 1989. [32] T. M . Schultels, P. E. Dupont, P. A. Milliman, and R. D. Howe. Automatic in-dentification of remote environment. In Proceedings of ASME Dynamic System and Control Division, volume 58 of DSC, pages 451-458. ASME, Nov 1996. [33] J. Siira. Simulation of contact textures and forces with application to haptic interface. Master's thesis, University of British Columbia, 1996. [34] J. Siira and D. Pai. Haptic texturing - a stochastic approach. In Proceedings of IEEE International Conference on Robotics and Automation, volume 1, pages 557-562, 1996. 72 [35] Thad Starrier and Alex Pentland. Real-time american sign language recognition from vidoe using hidden markov models. Technical Report 375, MIT The Media Laboratory, 1995. [36] A. Wald. Sequential Analysis. John Wiley and Sons, 1947. [37] A. S. Willsky. Detection of abrupt changes in synamic systems. Detection of Abrupt Changes in Signal and Dynamical Systems, 1986. [38] A. S. Willsky. Recursive estimation. Technical report, MIT, 1990. [39] P. Zhou and A. D. Poularikas. Ar spectral estimation of segmented time signals. In System Theory, 1990 Southeastern Symposium, pages 536-539, 1990. 73 Appendix A Forward and Backward Procedure The forward procedure is to calculate the possibilities of a observation sequence, given the candidate model. Forward variable at(i) = P(Oi,02, • ••,Ot,qt = 5;|A). • Initialization: a1(i) = nibi(01), l < i < N (A.l) • Induction: N = E a * ( O « i A ( 0 t + i ) ; i < * < r - 1 , 1 < j < (A.2) i=l • Termination • . P(0\\) = jr<*T(i) (A.3) i-l The backward procedure is used in the task model parameter adjustment. Backward variable f3t(i) = P(Ot+i O t + 2 ... Or\qt = Si,X). 74 • Initialization: /3T(0 = 1 (A-4) • Induction: N /Mt) = 5>yMOt+i )A+iC/) ; t = T-l,T-2,...,l, 1< i<N (A.5) 75 Appendix B Viterbi Algorithm To find the single best state sequence Q = {qx, q2,qr}, given observation sequence o = {ouo2,...,oTy. St(i) = max P[qx q2 ... qt = i,Ox 02 ... Ot\\] (B.l)-91.92 , — >9t - l • Initializer: S1(i) = nibi(01), l<i<N (B.2) rpii = 0 (B.3) • Recursion: St(j) = max [ ^ ( ^ ^ ( O , ) ; 2<t<T, l<j<N (B.4) l<t<jV • MJ) = arg( max [<$,_! (t)^-]);- 2 < t < T, 1 < j < N (B.5) K t < N • Termination: P* = max [Mi)] (B.6) Ki<N W J K ' 76 It = arg( maxJST(?)]) (B.7) i<i<i\ • Result Backtracking: gj = ^+i(?;+i), i = T - l , T - 2 , . . . , l (B.8) 77 Appendix C Baum-Welch Algorithm For each task, there are K observation sequences to train the model. The reesti-mated parameters for the HMM model A = (A, B, w) are: ft = E « T ( 0 (ci) 8=1 E/t=i7^Ei=i «*(*)&(*) • 7r8- is not reestimated: TT\ = 1, 7r^  = 0 /or j ^ 1. 78 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items