A QUALITATIVE REPRESENTATION FOR MANIPULATOR KINEMATICS AND OTHER VECTOR AND SCALAR FIELDS by • HEIDI THERESE DANGELMAIER B.Sc.,Western Washington University, 1986 . A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE 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 October 1989 © Heidi Therese Dangelmaier, 1989 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it 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. Department of The University of British Columbia Vancouver, Canada Date OCT lh i9?9 DE-6 (2/88) A b s t r a c t Over the last several years a branch of Artificial Intelligence called Qualitative Rea-soning has received much attention. A qualitative reasoner use qualitative values such as increasing, boiling and turbulent to analyze the behavior of physical systems. Existing qualitative frameworks have focused on physical systems whose qualitative values can be identified given the value of a single parameter. This precludes the application of qualita-tive models to physical systems whose properties require the values of several parameters. A n example of such a system is the kinematics of a robotic manipulator. With this moti-vation, this thesis answers the following: What is a Qualitative model? Although current approaches appear diverse, they share a common mathematical foundation. This foun-dation is used to reformulate the qualitative model as a set of equivalence relations. The other question answered is: What extensions are needed to handle multivariate properties such as those encountered in the manipulator paradigm? The equivalence classes associ-ated with qualitative models are geometrically shown to be connected hyperspaces. We show that existing frameworks are limited in the types of hyperspaces they can represent. The major ideas in this thesis are illustrated using manipulator kinematics. ii C o n t e n t s Abstract ii Contents iii List of Figures vi Acknowledgement vii 1 Introduction 1 1.1 Properties: Basic definitions and Restrictions 3 1.2 Why robot manipulators? 7 1.3 What Is A Qualitative Model? 10 1.4 Qualitative Equivalence Space 11 1.5 Contributions 13 1.6 Thesis Overview 14 2 Manipulator Background 15 2.1 Manipulator Structure and Description 15 2.2 Kinematics 18 2.3 The Mathematics Of Forward Kinematics 20 2.4 Qualitative Properties and Manipulator Kinematics 23 3 A Framework For Qualitative Representations 28 3.1 Property restated 29 3.2 Example properties 32 3.2.1 The Qualitative Partial Derivative 36 3.3 The Qualitative State 40 3.3.1 The Pullback Partition 42 3.3.2 Property Compositions 45 3.4 State Transition 47 iii 4 Qualitative Equivalence Space 50 4.1 Property Reformulation 51 4.1.1 Analytic restatement 51 4.1.2 Geometric restatement 54 4.2 The Aggregate model 64 4.2.1 Inequality Restatement 64 4.2.2 Geometric Restatement: QES 65 4.3 Qualitative Partial Derivatives and QES 66 4.3.1 Example: The Robotic Manipulator 69 4.4 Computation and QES 74 5 Comparisons and Usage 77 5.1 QES And Existing Representations 77 5.1.1 Qualitative Dynamics and multivariate properties 78 5.1.2 Qualitative Kinematics 82 5.2 Reasoning and Control 85 6 Conclusion and Future Work 89 6.1 Summary 90 6.2 Future Work 91 Bibliography 93 iv r L i s t o f F i g u r e s 1.1 Properties are used as symbolic descriptions of physical phenomena. . . . 4 1.2 A canonical robotic manipulator 8 1.3 Manipulator control overlaps the focus of kinematics and dynamics. . . . 9 1.4 QES, an intermediary representation 11 2.1 An abstraction of a two-link revolute manipulator 17 2.2 The lack of inverse kinematic equations is frequently due to redundancy. 20 2.3 The end-effector trajectory, with ji = c 25 2.4 Kinmatics described using the qualitative values Increasing(l),Decreasing(D), and Static(S) 26 3.1 A property is composed of a function and a partition 33 3.2 Properties, partitions, and characteristic functions 34 3.3 Point-type, a complex property 35 3.4 Monotonic-dependence and the manipulator 39 3.5 A partition on p-space associated with a property and its partition B. . . 42 3.6 The pullback partition 43 3.7 To ensure consistent transitions, state domains must be connected. . . . 49 4.1 Graph o f / ( x i , x 2 ) 55 4.2 Cross-sections associated with T\, T?, T 3 57 4.3 The projections associated with the cross-section T\ and T 2 58 4.4 Continuous surfaces can be equated to the partition B 59 4.5 The contour map for f(x\,X2) and Ti , 7/2,7/3 61 4.6 The qualitative gradients of a bivariate scalar field 68 4.7 The qualitative partial derivatives of the two-link manipulator 71 4.8 The qualitative gradients of the two-link manipulator 72 4.9 The qualitative Jacobian of the two-link manipulator 73 5.1 The Dsi of existing dynamic systems are hypercubes 79 5.2 The set of joint values j,-(t) defines a path in C-space 81 v Monotonic-dependence changes qualitative values at intersections vi A c k n o w l e d g e m e n t s This thesis has weathered a tribulation filled phase of my life. There are several people whose support and encouragement have provided me the strength needed to not despair. It is with the deepest of sincerity that I say the following appreciative words: Jim Little: To quote a simile, "third times a charm", the third and irrefragably the superlative supervisor. (Ab)Norm Goldstein: Your mathematical expertise coupled with your kind heart have helped me grow both emotionally and academically, I am so blessed to know you. Jane Mulligan: Always an ear to listen, it has remained tacit too long that you are a sensational friend. Mike Bolotski: Your stop-moping-and-just-get-it-done manner gave me just the impetus I lacked and needed in the end, a heartfelt thanks. Manny, Hilde: My dear neighbors and so much much more, your care and support made a difficult summer beautiful. And last a peculiar acknowledgement to Alan Nichol who played a convoluted role in the whole process. vn C h a p t e r 1 I n t r o d u c t i o n In introductory calculus one learns that the general behavior of a function can be de-duced from knowing its relevant qualitative properties [35] [1]. Among the most informa-tive qualitative properties are sign, slope-sign, and concavity. Knowing these properties, an approximate graph depicting the behavior of a function can be generated. Although qualitative models do not give exact numeric values, enough information is retained to determine where a function experiences significant change. 1 Consider the property slope-sign which characterizes a system by distinguishing intervals of the domain where the slope of a function is uniformly negative, positive or zero. This characterization is qualitatively analogous to knowing the derivative. This description provides locations of the local extrema and intervals in the domain where the value of the function is in-creasing, decreasing, and static. Al though classifying slope as increasing, decreasing, and static is not informative enough to distinguish variations in magnitude, this classification Significance is intentionally vague and is particular to the task at hand. 1 CHAPTER 1. INTRODUCTION 2 preserves enough detail to differentiate direction. A branch of Artificial Intelligence called Qualitative Reasoning employs qualitative properties to describe, analyze and make control decisions pertaining to the behavior of physical systems. Researchers in qualitative reasoning argue that there are tasks in which qualitative representations are preferred to quantitative representations. There are several reasons why qualitative representations are advocated. The predominant reasons are that qualitative representations: abstract away the details providing an overview of a system's behavior; are amenable to symbolic reasoning; permit a priori generation of all behaviors afforded by a system. These advantages are attributed to two primary factors. Firstly, qualitative models are discrete and hence more tractable. Secondly, qualitative properties are descriptive because they emphasize behavioral versus numeric change. For these reasons, qualitative representations have been used in modeling dynamic [21] [16] [10] [32] and kinematic systems [19] [14] [25]. Current modeling frameworks are not capable of handling the multivariate functions needed to represent the qualitative analog of the partial derivative which describes de-pendence of the value of a function on its parameters. This precludes the application of qualitative reasoning to control situations like robotic manipulator navigation. This inability reflects a more general limitation of existing formalisms; they are inadequate to handle any property whose classification requires the value of more then one variable. Identifying the source of this limitation is essential to the extension of qualitative models. Unfortunately, existing qualitative formalisms use quite diverse modeling frameworks: constraints[21], processes[16] mechanisms[10], and contacts[14] are the most predomi-CHAPTER 1. INTRODUCTION 3 nant. This diversity obfuscates the theoretical basis of these representations, and hinders extensions. This thesis outlines the common mathematical underpinnings of qualitative models in terms of properties, states and state transitions. By casting the frameworks in unified mathematical terms, the extensions required to incorporate multivariate properties are elucidated. A class of qualitative properties based on functions and partitions is iden-tified. The mathematical characteristic of this class are used to demonstrated that the qualitative model is set of equivalence classes, and the possible continuous transitions between them. Subsequently the structure of these equivalence classes is explored and reformulated as connected sets of inequality-invariant functions. Finally, the qualitative model is shown to be isomorphic to a geometric model denoted Qualitative Equivalence 5pace(QES). The geometry of QES is used as a basis to explain the inadequacy of existing frameworks. For systems composed of algebraic properties we examine computational is-sues and show that in principle algorithms based on cellular algebraic decomposition can be used to generate the qualitative model. Manipulator kinematics are used to illustrate basic concepts of this work. 1.1 P r o p e r t i e s : B a s i c d e f i n i t i o n s a n d R e s t r i c t i o n s Properties are symbolic metrics used for classifying quantities of a system and are the primitive elements of a qualitative model. This section establishes the family of properties dealt with in this thesis. A more concise definition of properties follows in Section 3.1. There are several types of qualitative properties. For instance, qualitative properties CHAPTER 1. INTRODUCTION 4 can be univariate or multivariate and can portray general characteristics of functions or characteristics particular to specific applications. Despite these variations, all prop-erties serve a similar purpose; they describe a physical system using a set of symbolic descriptions called qualitative values. Figure 1.1 portrays is the contrast of qualitative properties to analytic functions. Physical system Analytic function (characteristic function) Property Actual Behavior Real-value Qualitative Value Figure 1.1: Properties are used as symbolic descriptions of physical phenomena. This thesis was motivated by the need for a general representation of multivariate properties. A property is univariate if its qualitative description can be based on the value of one parameter where a qualitative description is a set of qualitative values. For example, the slope-sign of a continuous function f(t) is univariate; The qualitative values increasing, decreasing, and static are determined by evaluating the univariate function CHAPTER 1. INTRODUCTION 5 f'{t). Classifying a system using properties that have multivariate dependencies requires more than one variable; the qualitative values vary as a function of a set of independent variable. For example, determining the sign of a scalar multivariate function requires knowing the value of al l variables. Properties mentioned so far are general; their values are of interest to most systems. A second type of property are system-specific properties. These properties have more restrictive uses, and are relevant only to specific paradigms. For example, a property like fluid-flow, which classifies the flow of a viscous fluid using the qualitative notions laminar, transient, or turbulent, is pertinent to only fluid applications. This property is also multivariate; determining the qualitative properties requires calculating the Reynolds number which is based on the parameter values of density, average velocity, pipe diameter and viscosity[38]. The above properties, although apparently dissimilar share an underlying mathemati-cal structure. This structure has been used implici t ly in previous representations but has never been made explicit. The premise assumed by existing systems is that all properties have two common components, a characteristic function and a part i t ion on the image of that function. The characteristic function is a continuous mapping from a set of parameters that we call p-space to a image(a subset of Rm) Characteristic function : SK™ —• SR7™ where m,n > 1. The p-space of a univariate property is linear while that of a multivariate property is CHAPTER 1. INTROD UCTION 6 a manifold in 3ft", n > 1. For example p-space associated with fluid flow in a pipe is the cross-product of fluid density p, pipe diameter D, fluid viscosity 77, and fluid velocity v. The second common component is a parti t ion on the image of the characteristic func-t ion. This part i t ion is a finite set of intervals that serve as to decompose the continuous range of a function into groups which exhibit similar behavior. Each subinterval cor-responds to one qualitative value. The boundaries of these subintervals are denoted thresholds. Thresholds delimit where the qualitative behavior of a system experiences a change. Thresholds are not required to be time invariant, although time-invariance reduces the amount of computational effort. The property slope-sign illustrates the concepts of characteristic functions and thresh-olds. The slope-sign of the continuous function f(t) is classified using the characteristic function / ' ( £ ) , the derivative of f(t). Determining the qualitative values of this function is achieved using zero as a threshold. In Section 4.3 it is shown that the qualitative partial derivative fits this framework. The p-space of properties is also subject to restrictions. This work has principally focused on systems whose properties which are defined on the same p-space. A n impor-tant example is the qualitative Jacobian and gradient which arises in the aggregation of several qualitative partial derivatives. Mathematically these are vector fields. Vector fields are compound functions whose components are scalar fields defined on the same < 0 then / (£ ) is Decreasing at t = 0 then f(t) is Static at t > 0 then f(t) is Increasing at t CHAPTER 1. INTRODUCTION 7 range. Symbolically / ( x i , . . . ,xn) = / i (x ! , . . . ,x n )e! + . . . + fm(xi,... , z n ) e m , where e i , . . . , e m are the basis vectors. Comments on how violations of the outlined restrictions affect the proposed frame-work can be found in Section 6.2. 1.2 W h y r o b o t m a n i p u l a t o r s ? The absence of a general representation for multivariate properties was discovered during an effort to describe symbolically the kinematics of a robotic manipulator. The manipu-lator is a program-controlled mechanical device employed for its hand-like capabilities. A generic manipulator is displayed in Figure 1.2. The need for symbolic primitives to assist in the planning and control of manipulators has been recognized by [6]. Qualitative properties were pursued as potential symbolic primitives because they are amenable to symbolic reasoning yet still founded in math-ematics. Despite the generality of the results, the manipulator domain was preserved as a testing ground for demonstrating the major ideas of this work. This domain is particularly suitable because: • It introduces the need for a new property, the qualitative partial derivative. • Many of the qualitative properties of this domain are geometric and therefore easy to visualize. CHAPTER 1. INTRODUCTION Figure 1.2: A canonical robotic manipulator CHAPTER 1. INTRODUCTION 9 • It illustrates the role of both domain specific properties, and general function prop-erties. • Manipulator control falls between the two research areas, kinematics and dynamics. Selection of appropriate control choices not only requires spatial knowledge but demands the ability to predict behavior. This overlap is shown in Figure 1.3 • Manipulator kinematics are a useful and practical area for improved control and planning. Endowing manipulator control with more intelligence could offer greater task flexibility. Qualitative Dynamics Qualitative Kinematics Manipulator Control Figure 1.3: Manipulator control overlaps the focus of kinematics and dynamics. CHAPTER 1. INTRODUCTION 10 1.3 W h a t I s A Q u a l i t a t i v e M o d e l ? A Qualitative Model is a state-space graph containing a symbolic description of the behavior of a physical system. Accurately portraying states and state transitions is the pivotal factor in selecting an appropriate representation of properties [25] [16]. It is generally accepted that states are used to differentiate separate behavior modes, and the transformation between behavior modes are modeled as state transitions. Thus admissible paths in the graph reflect the behavioral changes a system can undergo. For systems described wi th properties, states are invariant with respect to the qualitative values. State transitions occur when a qualitative value is no longer applicable. This thesis demonstrates that property invariance induces an equivalence relation on p-space and the associated equivalence classes comprise the states. A l l elements of the equivalence classes have identical qualitative values. States are linked to other states wi th state transitions. If a system can transit through two different qualitative values by continuous changes of its parameters, this transition is recorded in the set of state transitions. The quantitative analog of transitions are limits. We show that state transitions necessitate further refinements of the equivalence classes to account for set connectivity. The next section takes a closer look at the geometric and analytic form of states. Qualitative Equivalence Space is introduced as a geometric version of the qualitative model and a vehicle for unifying properties. CHAPTER 1. INTRODUCTION 11 1.4 Qualitative Equivalence Space Qualitative Equivalence Space(QES) is a geometric representation which is isomorphic to the qualitative model. QES is a decomposition of p-space into regions; all points within a region share the same qualitative values. Figure 1.4 shows how QES serves as a vehicle for aggregating properties. Property n Properties QES Qualitative model Figure 1.4: QES, an intermediary representation. The equivalence classes corresponding to states can be described analytically and their connected components have a special geometric form. These equivalence classes can be reformulated as a set of points in 3Jn that satisfy a conjunction of analytic function inequalities; if these sets are further divided into their connected components they meet the requisites of state-transitions. These sets are isomorphic to a decomposition of p-CHAPTER 1. INTROD UCTION 12 space and the topology of the resulting graph is isomorphic to the qualitative model. QES is used to demonstrate that the task of generating a qualitative model for systems with multivariate properties is equivalent to decomposing p-space with level sets. Level sets are subsets of the domain that map to equivalent range values, The term critical curve is used to denote the component of these level sets. Critical curves associate with slope-sign are the solutions of fit) = 0. Another example of a critical curve for fluid flow R which is mathematically defined as the scalar field: R = p * v * D/r]. The two critical curves are the hypersurfaces where the Reynolds number evaluates to 2000, and 3000. These sets delimit conditions when fluid flow changes from laminar to transient, and transient to turbulent respectively. Computational aspects of QES are equated to decision procedures used for applica-tions which can be encoded in the theory of the reals [5],[20]. 1 . 5 C o n t r i b u t i o n s Several of the ideas explained in this thesis are new. The contributions of this work to Qualitative Reasoning include the following: CHAPTER 1. INTRODUCTION 13 • Provides set theoretic and geometric definitions of qualitative models (Chapters 2 and 3 respectively). By using a concise mathematical framework to define a qualitative model, the confusions stemming from the diversity of previous models are reduced, and extensions are facilitated. • Provides a modeling framework(QES) for representing multivariate properties, point-ing to a class of decision algorithms potentially useful for constructing these mod-els(Chapter 3). • Formalizes the qualitative partial derivative, gradient, and Jacobian. • Identifies the shortcomings preventing current qualitative reasoning systems from handling domains that require multivariate properties (Chapter 4). • Demonstrates the utility of QES by applying it to the translational differential kinematic relations of a two-link manipulator. This domain is further developed with the integration of other manipulator attributes and a discussion of qualitative control(Chapter 4). 1.6 T h e s i s O v e r v i e w Chapter 2 reviews robotic manipulator kinematics and provides a visual and intuitive introduction to qualitative properties. Chapter 3 presents the qualitative model in a set theoretic framework. QES, the final translation of the qualitative model, is described in chapter 4. Chapter 5 elaborates on the implications of QES. Current modeling frame-works are contrasted with QES to expose their inabilities to meet the modeling needs of CHAPTER 1. INTRODUCTION 14 multivariate properties. In addition, a reasoning scenario is constructed in the manipu-lator paradigm. Chapter 6 concludes this thesis by addressing extensions and suggesting improvements to QES. C h a p t e r 2 M a n i p u l a t o r B a c k g r o u n d The following overview of robotic manipulator kinematics clarifies the aims of this research. This presentation first introduces the structure of a manipulator and then discusses translational kinematics 1 . For simplicity, the descriptions are terse; see [26] [8] [23] for more detail . This chapter concludes by recasting kinematics in the framework of properties, states and state transitions. 2.1 Manipulator Structure and Description A manipulator is a physical device comprised of a chain of rigid links. The distal point of the chain is the end-effector. The end-effector may be a gripper, welding torch, or other device depending upon the intended application of the manipulator. The motion of each link is constrained relative to the previous link. A few types of relative motions occurring between links are spherical, cylindrical , rotational, and translational. Rotat ional and ^^ This thesis omits a description of end-effector orientation. The majority of manipulators fall into the class of separable simple-chain manipulators wherein the translational planning is performed independent from the orientational. 15 CHAPTER 2. MANIPULATOR BACKGROUND 16 translational motions are used most frequently. The type of motion is determined by the joint. Pr ismat ic joints permit translational motion whilst revolute joints permit rotational motion. The degrees-of-freedom(DOF) of a joint are determined by the number of parameters required to specify the relative position of the two links it adjoins. Joints wi th spherical have three D O F while cylindrical motion has two D O F and translational or rotational motion have one. Typical ly, a joint sensor is attached to each joint to provide a readout of the displacement between the links. The joint parameters are used to represent these displacements. Figure 2.1 shows these structural features using the canonical manipulator, a two-link revolute manipulator. The links of this manipulator are of equal and constant length; L is used to denote this constant. Revolute joints have rotational freedom; therefore, joint parameters are defined by joint angles, jx, j2. Measurements of joint displacements are typically made following Denavit-Hartenberg conventions [12]. Using these conventions, the movement of a link is measured relative to its mating l ink. Affixed to every joint is a coordinate frame. Each frame is defined relative to the previous frame based on joint displacement, and the length, offset and twist of the l ink. A constant link length maintains a fixed spatial distance between adjacent frames. Manipulators are classified as free-axis mechanisms [30] because joint parameters are measured relative to a moving frame. The proximal link is an exception; its reference frame is inertial . Free-axes play a significant role in the modeling of the ma-nipulator system because they introduce non-separable multivariate dependencies. This significance is further elaborated on in Section 3.4, wi th the review of other qualitative CHAPTER 2. MANIPULATOR BACKGROUND Figure 2.1: A n abstraction of a two-link revolute manipulator. CHAPTER 2. MANIPULATOR BACKGROUND 18 kinematic representations. The two-l ink manipulator has constant l ink length, and no twist or offset. The measurement of is made wi th respect to a fixed frame while j2 has a dynamic reference frame. These reference frames, pictured in Figure 2.1, accord with the Denavit-Hartenberg conventions. The displacement of link two is measured relative to the normal of l ink one. This completes the structural description of the manipulator; this chapter now shifts to the modeling of manipulator motion with a discussion of kinematics. 2 . 2 K i n e m a t i c s Kinematics is the study of the motion properties of a manipulator irrespective of force 2. These properties include position, velocity and al l higher order derivatives of position. Kinemat ic equations can be divided into forward and inverse kinematics. This dichotomy determines which parameters comprise the p-space of the functions. The two principal p-spaces are Configuration Space and Workspace. Configuration space (C-Space)[28] [2] is the cross-product of the joint parameters. For an n - D O F manipulator with joint parameters ji, C-space is an n-space manifold defined as: C-Space = J! x ... x jn C 3?". The motion envelope spanned by the end-effector is the Workspace(W-space). W-space is a subset of Euclidean space. B o t h joint axes of the two-l ink manipulator pictured in Figure 2.2 are normal to the plane, thus the end-effector has planar extent and the shape 2The existence of servo-mechanisms capable of articulating the joints and maintaining desired con-figurations frees a kinematic controller from concerns about the forces causing motion. CHAPTER 2. MANIPULATOR BACKGROUND 19 of its W-space is a circular manifold in 9£ 2. The C-space of the two-link manipulator is toroidal. Kinematics involves mapping motion properties between C-space and W-space. The forward kinematics equations pertain to transformations from C-space to W-space. Hence, the p-space for these equations is C-space. Conversely, inverse kinematics are mappings from W-space to C-space. C-space is a preferred space for constructing and analyzing kinematics. The W-space is not a viable parameter space for the primary reason that functional descriptions of the inverse kinematics frequently do not exist. Closed form equations do not exist for many manipulators because two unique configurations can correspond to the same locus of the end-effector. Using X as a descriptor of the vector field position, this redundancy is stated 3 CUC2 s.t. C i , C 2 G C-space A Cx + C2 A X(d) = X(C2). Figure 2.2 illustrates this non-uniqueness using the two-l ink manipulator. Consequen-tially, this non-uniqueness prevents the representation of velocity o and acceleration as functions of W-space. To overcome these difficulties, control algorithms frequently use direct kinematic equations. These equations presume access to the current configuration. Henceforth, this thesis is restricted to functions of C-space. Under this premise, the focus turns to the mathematics of the forward kinematics. CHAPTER 2. MANIPULATOR BACKGROUND 20 Figure 2.2: The lack of inverse kinematic equations is frequently due to redundancy. 2.3 T h e M a t h e m a t i c s O f F o r w a r d K i n e m a t i c s This section acquaints the reader wi th the form of equations used in describing the position and velocity of the end-effector. A brief overview of path generation and control is also included. The position of the end-effector is a static geometric property and is mathematically represented as a vector f ie ld 3 . Static means that the range of the position functions are time invariant. For an n - D O F manipulator the position vector field has the form, X(ju---Jn) = Xi(ji,...Jn)e1 + ... + ^m ( j i,...,in)e m (2-1) 3There are manipulators whose position functions are separable; for example a Cartesian manipulator[22] require only the value of the one joint parameter to determine each coordinate of the end-effector. However, manipulators containing revolute joints, which accounts for the majority of manipulators, are non-separable. CHAPTER 2. MANIPULATOR BACKGROUND 21 the are the basis vectors of Euclidean space. This vector field maps a point in C-space to the corresponding locus of the end-effector in W-space. Each Xi is a scalar field evaluating to the coordinate of the end-effector measured in the direction of ej. For simpler mechanisms, this function is calculated geometrically. For complex mechanisms, this function is generated as successive products of homogeneous transformation matrices parameterized in accordance wi th the Denavit-Hartenberg conventions [26]. The position of the end-effector for the two-link manipulator is a function of j^and j2. The locus of this end-effector is determined functionally as X(j1,j2) = ( I c o s ( j i ) + X c o s ( j i + j 2 ) ) e i + (Zs in ( j i ) + Z s h n j i + j2))e2. (2.2) Because the distance the distal l ink displaces the end-effector is dependent on the value of ji, neither X\ nor X2 can be represented as a composition of univariate functions of the jx and j2. A path is a continuous trajectory of positions in workspace. Path-planning involves establishing a sequence of configurations that moves the end-effector through a desired trajectory in W-space. Mathematically, path-planning can be thought of as, given a continuous trajectory X(t)=X1(t)e1 + ... + Xm{t)e m find the functions ji(t), ... , jn(t) S . t . X^t) = X1(j1(t),...,jn(t)) CHAPTER 2. MANIPULATOR BACKGROUND 22 Xm(t) = X m ( j i ( t ) , . . . , j n ( t ) ) . Inverse—kinematic equations typically are not closed form; in general, an easily evalu-ated function mapping the position of the end-effector to a configuration does not exist. A s a result, par t ia l derivatives of inverse kinematic equations are used to servo the robot joints to follow prescribed endpoint velocity commands. The first part ial derivatives | ^ give the rate of change of Xi measured in the direction of positive jk- Simply stated, these part ial derivatives describe the direction and magnitude an end-effector w i l l dis-place when a joint is articulated. The jk(t) are determined using a matrix called the Jacobian. The Jacoabian's rows are the gradients V X , - . The gradient is a vector field that unifies the part ial derivatives of a scalar field. For the scalar field Xi(ji,... ,jn) the gradient vector is -*r i • • \ dXi dXi , . VXi{ju...,Jn) = 7 7 - ^ 1 + . . . +-x - I e n . (2.3) OJl OJn The gradient vectors for the two-l ink manipulator are V X i ( j i , j 2 ) = ( - X s i n ( j i ) - L s i n ( j i + j 2 ) ) e i + X s i n ( j i + j ' 2 ) e 2 VX2(ji,j2) = (Lcos(j1) + Lcos(j1+j2))e1 + Lcos(j1+j2)e2 The Jacobian has the following form: - M i dji 9jn dXm dXm - dji djn CHAPTER 2. MANIPULATOR BACKGROUND 23 The elements of the Jacobian change as the manipulator moves. Thus the jk{t) are computed iteratively, by mult iplying the inverse of the Jacobian by incremental values of the coordinates. The Jacobian of the two-link manipulator is, (-L sin(ji) - L s in( j i + j2)) L sm(jx + j2) (L cos(ji) + L cos(;'i + j2)) L cos(ji + j2) The above section constitutes a quantitative characterization of forward kinematics. Kinemat ic functions were shown to be vector and scalar fields. In the introduction, properties were introduced as an alternate description for modeling systems. In the next chapter we show how qualitative properties can describe kinematic behavior. The majority of examples in the remaining chapters w i l l be drawn from these properties. 2 . 4 Q u a l i t a t i v e P r o p e r t i e s a n d M a n i p u l a t o r K i n e -m a t i c s Navigating a robotic manipulator entails moving an end-effector from a starting location in its W-space to a destination. Supplementing this control task wi th a qualitative reasoner necessitates the ability to compose several multivariate properties into a unified description. The remainder of this thesis concentrates on a subset of these properties, the joint-dependencies describing the relation between the motion of the end-effector and the actuation of the joints. Joint-dependence was selected because it is a special case of the general qualitative partial derivative. This section provides the physical interpretations of dependence wi th visual examples of thresholds, level sets, and property composition. (2.4) CHAPTER 2. MANIPULATOR BACKGROUND 24 In the previous section the potential motion of the end-effector was mathematically represented as the gradient. The qualitative property joint-dependence characterizes this potential motion by classifying the differential relations between the joints and the coordinate of the end-effector. A first-order classification of these relations makes the most significant distinction, that being, determining whether a differential joint actuation results in an increasing, decreasing or zero change to the value of the end-effector's coordinate. Joint dependence varies as the manipulator reconfigures, so it is functionally dependent on a configuration, and must be classified at the differential level. The joint-dependence between jk and X{ at the configuration ji,... , c , . . . jn wi th the constant c in the position jk is defined as: ( < X i ( j i , . . . , j n ) then Decreasing(X1(j1,... ,jn),jk) if Xi(ju...,c + Aj, ...Jn) < = X i ( j i , . . . , j n ) then Static(Xx(ji,... ,jn),jk) { > Xi(jlt...,jn) then Increasing(X1(ji,...,jn)Jk) Where the qualitative values Increasing(Xi(ji,... ,jn),jk) denotes that X{ is in-creasing in its dependency on jk at the configuration (ji,... ,jn). The qualitative values Decreasing and Static follow accordingly. Joint-dependence is equivalently defined with inequality relations and partial derivatives. ' < 0 then D ecr easing (Xi(j i,... ,jn),jk) -0 then Static^X^ji,. . . ,jn),jk) > 0 then Increasing(X1(jl,... ,jn),jk) The value 0 is a threshold and divides the range of the partial derivatives into intervals ., dXi . . . d - T - U l . - " J n ) \ OJk of similar behavior. The physical meaning of this threshold is demonstrated with the two-link manipulator. Thresholds of a constrained two-l ink manipulator are easily visualized. Consider the ring portrayed in Figure 2.2; this ring is the trajectory in W-space rendered by rotating CHAPTER 2. MANIPULATOR BACKGROUND 25 the end-effector while holding ji constant. Mathematically stated Locus = (Xi(cij2),X2(c,j2)) | Xx(c,j2) = (Icos(e) + XcosO'2 + c)), X2(c,j2) = (Lsin(c) + Lsin(c +j 2))) The partial derivatives 4^-, and ^jf- are diagrammatically represented as the tangent vectors of the circular trajectory. Horizontal and vertical tangent lines correspond to the 0 thresholds; they delimit where joint-dependence changes qualitative values. At these thresholds, the slope of the tangent line changes from positive to negative. + x, Figure 2.3: The end-effector trajectory, with j\ = c. Critical curves are also easily visualized. The coordinate frame attached to the sec-ond joint is a translation of the Workspace coordinate frame. Each axis subdivides CHAPTER 2. MANIPULATOR BACKGROUND 26 configurations into four intervals: two semi-circles and two points. These intervals are subsets of C-space where the joint-dependence property is invariant. Composing the joint-dependence relation for X\ and X? results in eight subintervals. These intervals are the state domains; the dependence between the end-effector coordinates and the j? is invariant. Figure 2.4 is the state-space graph of this system. Figure 2.4: Kinmatics described using the qualitative values Increasing(I),Decreasing(D), and Static(S). The model just presented is not a complete kinematic-model of the two-link manip-ulator it has only one DOF. A complete qualitative model must aggregate the joint-dependence property for each coordinate, and each joint parameter. CHAPTER 2. MANIPULATOR BACKGROUND 2 7 A n introduction to the application of qualitative properties to robotics was provided in this chapter. The next chapter returns to more general representational issues with a formal definition of property, state and state transition. Joint-dependence wi l l be restated as a specific instance of the qualitative partial derivative. Chapter 3 A Framework For Quali tat ive Representations The previous chapter used the potential motion of a manipulator to illustrate how qualita-tive properties related to characteristic functions, thresholds and partitions of W-space. This chapter generalizes these relations and proposes a theoretical framework for de-scribing physical systems with qualitative properties. We begin by defining a property as consisting of a function and a parti t ion on the image of this function. This definition is substantiated by showing that it accommodates al l previously cited properties; addition-ally, the extensibili ty of this formalism is illustrated through the introduction of a new property type, the qualitative partial derivative. Bui ld ing on the posited definition of properties, qualitative models are defined. First we show that the states of a qualitative model are partitions on p-space induced by the inverse of the characteristic functions. Subsequently, we demonstrate that these partitions must be further refined to meet the connectivity requirements mandated by the definition of state transition. 28 CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 29 3.1 P r o p e r t y r e s t a t e d Qualitative properties are a medium for portraying gross behaviors of physical systems; this section formally defines the mathematical structure of these properties. There are two types of properties: simple and complex. Simple properties require only one characteristic function, while complex properties rely on the values of more than one function. The characteristic functions of simple and complex properties can be either general or system-specific. If a property is general, its characteristic function is just a prototypical, whilst a system specific property corresponds to a specific function. For example, the property slope-sign is a general property, and is an elementary metric used for describing the behavior of most continuous univariate functions. The prototypal characteristic function of this property is the first derivative. Simple and complex properties are defined next. A simple property has two components: a characteristic function and a partition on the range of this function into subintervals. The value of the characteristic function and the parti t ion reflect the property and its qualitative values. Therefore, an example of a property is an n-ary scalar function / on p-space (p-space C 3£ n) : p-space - i - SJ (3-1) and its associated part i t ion B on SJ. B y the definition of partitions [31], the blocks of B, denoted Bi are mutually disjoint and their union covers SJ. Formally stated, BiHBj = 0 V i ^ j (3.2) \jBi = SJ. (3.3) t=i CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 30 Each block Bi is a subinterval of 3t- whose boundary values are the property thresholds T. Thus Equat ion 3.1 can be rewritten as p-space Bi U...U B„ A property can also be a conjunction of ra characteristic functions of the same p-space, and a par t i t ion on 3 t m . This type of property is referred to as complex. Formally, a complex property is a vector-valued function / = ( / i , . . . , fm) and a partition B on •ft7™ wherein p-space -A 3ftm (3.4) p-space [jBi (3.5) where the blocks, are a cross-product of one block Bij from the range of each Symbolically, Bi = Bij x . . . x Bmk z = U BiJ where \B\ — z and each Bij is a (closed, open, or half-open) subinterval of the range 5^ , of jy This formalism does not require that the Bij are distinct. Loosely speaking, the partitions "break up" a range into blocks which exhibit similar behavior. Each block corresponds to one qualitative value of the property. These qualita-tive values are described wi th relations. If z denotes the cardinality of the partition then CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 31 the property has z qualitative values, each of which is described wi th one relation. For ex-ample, a simple property defined wi th the sign-invariant parti t ion {(—oo, 0) , [0], (0, oo)}, and the characteristic function / ( x ) correspond to three qualitative values and three unary relations. These are Reh(x) : f(x) G (-oo,0) Rel2(x) : f(x) G [0] Rel3(x) : f{x) G (0 ,oo) where x G p-space and denotes { ( - c o , 0 ) , [0], (0, oo)} BX,B2, andf? 3 respectively. For example the complex property defined by the characteristic function / = (/i, / 2 ) , whose associated parti t ion is the cross product of sign invariance, {(—oo,0), [0],(0,oo)} the associated relations are: Rel\{x) • /i( x) G ( - o o , 0 ) A / 2 ( x ) G ( - c o , 0 ) Rel2(x) : /i( x) G (-oo,0) A / 2 ( x ) G [0] Rel3(x) : /i( x) G (-oo,0) A / 2 ( x ) G (0,oo) ReU(x) : fi » G [0] A / 2 ( x ) G (-co,0) Rel5(x) •• fi » G [0] A f2(x) G [0] Rel6(x) •• fi [x) G [0] A / 2 ( x ) G (oo,0) Relj(x) •• fi (0,oo) A / 2 ( x ) G (-oo,0) Rels(x) : fi [x) G (0,oo) A / 2 ( x ) G [0] Rel$(x) • fi ' 0 Maxima :BA = ([0], (-oo, 0)) f'(x) = 0 f"(x) < 0 Undefined :B5 = ([0],[0]) f(x) = 0, f"(x) = 0 The property point-type is illustrated in Figure 3.3. The generality of the proposed definition of properties facilitates the generation and incorporation of new property types. This extensibility is demonstrated by creating a new property, the qualitative partial derivative. CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS Maxima Minima Undifined Figure 3.3: Point-type, a complex property CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 36 3.2.1 The Qualitative Partial Derivative The proposed framework for properties facilitates the extension of qualitative descriptions to include an informative and essential property, the dependence relation describing how the value of a scalar field changes relative to its independent parameters. This property, called monotonic-dependence, is the qualitative analog of the partial derivative. A reasoning system capable of predicting and controlling the time behavior of a scalar field must encapsulate the knowledge contained in the partial derivative. The importance of the partial derivative is appreciated in relation to its single variable counterpart, the first derivative f'(x), which is the rate of change of f(x) with respect to a differential change in x. The derivative is indicative of the expected time behavior of f(x) as x varies. Unlike a univariate function, the value of a vector field f(xi,... , x n) is simultaneously dependent on each x,-; its value can change with respect to differential changes to the x,-. Recall from Chapter 2 that the partial derivative is an operator which isolates these individual changes, yielding the rate of change of / relative to the x,-. A first order qual-itative description of this rate determines whether the value of a function is increasing, decreasing, or static relative to one of its parameters. We label these qualitative values monotonically-increasingjx.(MY), monotonically-decreasingfx.(MI)), and staticftXi(S) respectively. The function / is monotonically-increasing in its dependence on Xj at a fixed set of parameter values, (x 1 ? . . . , x n), if a differential increase to x,- causes the value of / to increase. Monotonically-decreasing and static are similarly defined. The corresponding characteristic function for the partial derivative of / with respect CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 37 to Xi is df, , The associated part i t ion of 3? is the three intervals {(—oo, 0)[0](0, oo)}. The qualitative values in conjunction wi th the associated relations for x € p-space are enumerated below. df Monotonically-decreasingjx.(x) : < 0 (3-7) Static f,Xi(x) '• = 0 (3-8) df Monotonically-increasingfx.(x) : ^ — > 0. (3-9) Monotonic-dependence is a general property and is applicable to many physical sys-tems. The property joint-displacement, defined in Section 2.4, is a special case of monotonic-dependence. Apply ing monotonic-dependence to the position of the end-effector results in the properties monotonic-dependence and joint-dependence having the identical physical interpretation. Example: The Two—link Manipulator Monotonic dependence can be used to describe the possible ways a coordinate of the end-effector changes value. This motion is governed by the dependence between the scalar field Xi (Definition 2.1) and its joint parameters. As defined in Equation 2.2, the Xi coordinate of the end-effector is determined by the function Xi(juj2) = -Lcos(ji) + Lcos(j1+j2) CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 38 Describing the potential displacement of X\ requires two instances of monotonic-dependence, one for the dependence of X\ on ji, and a second for the dependence of X2 on j2. The monotonic-dependence property applied to j\ uses the partial derivative given in Equa-tion 2.4 and reads Vja,J6 € C-space Monotonically-decreasingXl^(ja,jb) '• {—Lsin(ja) — Lsin(ja+jb)) < 0(3.10) Staticxijiijajb) • {-Lsin(ja) - Lsin(ja+jb)) =0(3.11) Monotonically-increasingx^^daJk) : ( — Lsin(ja) — Lsin(ja+jb)) > 0.(3.12) The dependence of Xi on j2 is defined likewise. These relations are equivalent to joint-dependence that is, if monotonically-increasingXl ^ then the X\ coordinate of the end-effector is increasing in its dependence on j\. The property monotonic-dependence applied to the manipulator domain is illustrated in Figure 3.4. Up to this point, we have only focused on quantizations of the range of the charac-teristic function. Classifying a system using properties also partitions the p-space of the system. When properties are used, a system is characterized by the applicable relations. Unlike the values of most quantitative functions, the values of a qualitative property (e.g, relations) typically hold over continuous variations of the independent parameters. For example, in Figure 2.3 the p-space is a circle. The properties implicitly partition the circle into quadrants; within each quadrant each component of the tangent vector is sign-invariant. Actually, the circle is partitioned into eight regions: the four quadrants CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS Continuous Function : dXi/djt Partition: B= {(-~,0),[0].(0,~)} Qualitative Values : MI, S, MD Thresholds: 0 2XiG«jO Figure 3.4: Monotonic-dependence and the manipulator CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 40 and the four points at the intersection of the circle wi th the axes. A t these four points one of the tangent vector components is zero-valued. These regions correspond to the three monotonic-dependency relations. Properties additionally lead to a quantization of p-space into subsets that cause the characteristic function to evaluate to the same 5 , . This quantization is the foundation of a qualitative model, the subject of the remainder of this chapter. 3.3 T h e Q u a l i t a t i v e S t a t e A qualitative model aggregates the properties of a system into a unified state-space description. This description portrays the behavior of the system as a sequence of states and state transitions. The purpose of transforming a set of properties into a state-space model is to quantize p-space into subsets which exhibit similar behavior. This quantization results from the fact that the qualitative values of a property are invariant over large subsets of p-space. The requirements of qualitative states are explained in this section; the following section refines this definition to incorporate the state transitions. A qualitative model ( Q M ) is a state-space graph Q M = (S,T,D,L) (3.13) where S is a set of vertices T is a set of edges Tj, where T a ,4 indicates a possible transition from Sa to Sb\ and D is a set of Dst such that each Ds{ C p-space and the ele-ments of each Dst are invariant wi th regard to qualitative values of the properties. Using Reljtk to represent the kth qualitative value of the jth property, invariance is formalized CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 41 as V p i , p 2 6 Ds, ReljM => Reljk{p2). £ is a set of labels L 5 . containing the Relj,k associated wi th the qualitative values that are valid on Dsi- The definition of a function ensures that any element x of p-space is associated w i th one and only one qualitative value per property. More formally, V z V j 3! Reljtk(x). R is a set of relations, Rels^ which are invariant on each D 5 . . We assert that the set D is a parti t ion on p-space. This follows from the observation that a property and its qualitative value additionally induce a complementary parti t ion on p-space, hereafter called a pullback partition. We wi l l begin by demonstrating that a property induces a pullback parti t ion and then show that an aggregation of these properties addit ionally induces a pullback parti t ion. 3.3.1 The Pullback Partition A property leads to an equivalence relation on p-space. This claim is substantiated by showing that pul l ing the blocks Bi into p-space decomposes this space into a parti t ion of the type depicted in Figure 3.5 . The equivalence relation associated with this property states Vpi ,P2 G p-space (f(Pl) e Bj A f(p2) € Bj) P l = p2 (3.14) CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 42 p-space image ( f ) Figure 3.5: A partition on p-space associated with a property and its partition B. Points satisfying this relation are called qualitatively equivalent. The proof that this relation induces a partition on p-space is straightforward, and is based on the inverse of the characteristic functions. Figure 3.3 depicts the pullback partition associated with a property. The pullback partition of a subset Bx C 3? under / is the set of all elements for which / evaluates to a member of the set B\. Formally stated, f~\B1) = {x : /(*) € Bx.) (3.15) From the definition of function, we can assert two identities regarding the inverse. Given two subsets of Bx, B2 C 3ftn, i - \ B x U B2) = /^(Bi) U f-1(B2) (3.16) r*(Bx n -Ra) = r \ B x ) n r \ B 2 ) (3.17) CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 43 Figure 3.6: The pullback partition. Identity 3.16 leads to the corollary Bx n B2 = 0 => r 1 ^ ) n f~\B2) = 0 Both identities extend to an arbitrary number of subsets. The identities 3.16 and 3.17, in conjunction with definition 3.15, form the substratum for showing the inverse relation induces a partition. Using R to represent the Image(f) where R = {y \ 3 x A x € p-space A f(x) = y} the assertion that the inverse relation on the partition B induces a partition of p-space associated with the qualitative equivalence relation follows as p-space = /^(R) (Definition of inverse) (3.18) = f~1(B1 U . . . U 5 i ) CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 44 (3.19) = {x € p-space \Rel{(x)} (3.20) Statement 3.20 shows that elements of the sets f~l(Bi) accord wi th the definition of qualitative equivalence. B y the definition of function, the sets / _ 1 ( B , ) are mutually disjoint. If the sets were not mutually exclusive then which contradicts the definition of function. Hence, qualitative equivalence induces a part i t ion on p-space. A qualitative equivalence relation founded on a single property is not sufficiently com-prehensive to meet the requirements for a qualitative model. A qualitative model must aggregate several properties into one unified description. The necessity for aggregation is clearly justified in reference to the qualitative gradient and Jacobian. Recall , from Section 2.1, that a scalar field is simultaneously dependent on the values of al l its pa-rameters. These dependencies are contained in the gradient as a set of first order partial derivatives. Recasting the gradient in a qualitative framework involves representing the monotonic dependence classifications for every independent parameter. The necessity of aggregation is made even more emphatic in reference to the derivative of a vector field. The part ial derivative is represented by a Jacobian matrix. The qualitative Jacobian re-quires mxn monotonic dependence relations i f m is the order of the vector field, and n is the number of independent parameters. In the next section we wi l l show that the notion of qualitative equivalence extends to composite characteristic functions and conjunctions 3 x s.t. f(x) = a, A f(x) — b A a ^ b CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 45 of partitions on p-space. 3.3.2 Property Compositions A n aggregation of properties induces a pullback parti t ion on p-space. Let $ sym-bolize the compound function composed of the characteristic equations / , . For a system described wi th m properties, The image space for $ is the cross product of the R{(i = l , m ) , where i?, denotes the image space for /,•: p-space R\ x . . . x Rm. However, from the definition of cross-product, we know that if P, denotes a partition on Ri then Px x P2 = {(BluB21),...,(Bln,B2m)} ( m - n blocks) assuming the cardinahties of B\ and B2 are m and n respectively. Thus, R{ can be rewritten as Ri = \jBij. j Therefore, equation 3.3.2 is restated as p-space [jBu x . . . x \jBmj (3.21) j j letting Bi = \jBxj x . . . x \ j B m j (3.22) 3 3 CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 46 p-space —• \JB{ (3.23) These equalities, in addition to the definition of inverse, lead to the following partition of p-space p-space = ^ - \ R m ) = $-l(\jBi) (Identity 3.23) t = U* _ 1 (£ . ) t We argue that these blocks are exactly the Z>5t \JDS, = \j9-\Bi) (3.24) i » To show that the elements of the Z)s, are invariant with respect to the qualitative values of a property requires demonstrating that the same set of property relations are valid for all elements of D$r This is accomplished by decomposing the Ds{ for a specific index i: Ds, = (A, . . . , /m)- 1 ^,-) = ( / l ) • • • 5 / m ) _ 1 ( - B i l ? • • • 5 Bim) = {x£ p-space \ x € f^{Bn) A . . . A a: 6 f-\Bim)} (3.25) Equat ion 3.32 substantiates the claim that the pullback partitions assoiciated with $ are property invariant; each /~ 1 (5 , J ) corresponds to one qualitative value of the jlh property. CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 47 A qualitative model must encapsulate the information needed to predict the time behavior of a system. In qualitative terms of states, this requires knowing the transitions between the Si. These transitions are discussed in the next section. 3.4 S t a t e T r a n s i t i o n The time behavior of a system described using qualitative properties is given as a sequence of Rsr These relations portray how the qualitative behavior of a system changes as a continuous sequence of points in p-space. These changes are encapsulated in the quali-tative model as a path through its vertices, where T,j are the possible changes between the Ri. This section demonstrates that in order to accurately portray state transitions, the elements of Ds< must be connected. A simple example using the sign invariant parti t ion clarifies this necessity. The graph of / is depicted in Figure 3.7 The elements of the pullback partitions are f~1(Bi) = {x \ x < a A a < x < b} f-1(B2) = { i | i = a A x = b} f-\Bz) = {x | x > b} O f these sets / - 1 ( 7 3 1 ) and / - 1 ( / 3 3 ) are connected and f~1(B2) is disconnected. This presents difficulty in describing the time behavior. The possible state transitions vary depending upon the components of / - 1 ( i ? 2 ) . A direct transition is possible between f~l(B2) and / _ 1 ( B 3 ) only for the case x = a. Thus in order to meet the criterion of state transition the state domain must be CHAPTER 3. A FRAMEWORK FOR QUALITATIVE REPRESENTATIONS 48 further refined to satisfy the topological property connectivity. Thus Dsi are not simply the sets f~x(B) but the connected components of these sets. In the above example we distinguish the states where x = a, and x = b X Bz B 2 •H—R o <—B — B > 1 1 3 Figure 3.7: To ensure consistent transitions, state domains must be connected. This section presented a theoretic foundation for qualitative models. The next section transforms this foundation into an isomorphic geometric description called Qualitative Equivalence Space. Chapter 4 Qualitative Equivalence Space The previous chapter demonstrated that the definition of state domain, in conjunction with some of the mathematical structure of properties is an equivalence relation on p-space. The associated partition was called the pullback partition and equivalence classes corresponded to subsets of p-space where the qualitative values are invariant. These results are very general and stem from the definition of functions and various definitions and theorems about equivalence relations. Current representations in qualitative mod-eling make assumptions about the class of characteristic functions and partitions. In particular, characteristic function and associated partition are continuous. Continuity further restricts the form of the equivalence classes. This chapter begins by reformulating the qualitative model as connected subsets of p-space that satisfy Boolean combinations of functional inequalities. These connected subsets are then viewed geometrically, and an isomorphism is made between a qualitative model and a decomposition of p-space. This decomposition is called Qualitative Equiv-alence Space. Computability is discussed and for characteristic equations with algebraic 49 CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 50 description, generating qualitative models is reduced to a family of known problems in computational geometry involving algebraic-varieties[5]. We begin this chapter by reformulating properties; after a formulation based on in-equalities, level sets and contour maps are proposed as alternative geometric views of properties. This notion is then extended to the aggregation of properties resulting in Qualitative Equivalence Space (QES) . Qualitative gradients and Jacobians are used to illustrate Q E S , followed wi th an actual model using the kinematics of the two-link ma-nipulator. This chapter concludes wi th a discussion of current algorithms that are suited to the computational needs of the qualitative model. 4.1 P r o p e r t y R e f o r m u l a t i o n This section rephrases properties first as functional inequalities and second connected geometric regions in p-space. 4.1.1 Analytic restatement In Section 3.3.1 it was shown that qualitative equivalence was an equivalence relation on p-space whose blocks were the pullback partitions $ - 1 ( i ? t ) . This section utilizes the restriction that the Bi are subintervals of Image(f) to rephrase qualitative equivalence as inequality invariance. Recall that px, p2 G p-space are qualitatively equivalent if the same qualitative value can be used to describe the behavior of a physical system under these conditions, stated specifically f{pi,p2) € B{. CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 51 Restrict ing the Bi to intervals permits the associated equivalence classes to be re-formulated as subsets of p-space that satisfy a conjunction of functional inequalities. Section 3.1 denned Bi as either a closed or open interval whose upper and lower bounds are the thresholds J i , or a singleton threshold, Bi = (Ti,Ti+l) Bt = [Tt\. This structure permits the relations associated with the qualitative values to be expressed as a set of inequalities ( < , > , = , < , > ) between the values of the characteristic functions and the thresholds. For example, the sign invariant parti t ion and the simple characteristic function f(x) given in Equat ion 3.6 is rewritten as: Rek(x) : f{x) < 0 Rel2(x) : f(x) = 0 Rel3(x) : f{x) > 0 where x € p-space. The relations associated wi th the qualitative values of complex properties can also be constructed from conjunctions of inequalities. For example the the relations in Equation 3.7 associated wi th the complex property whose function and partitions are / = (fi,f2), and {(—oo, 0), [0], (0, oo)} 2 , are rewritten as: CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 52 Reli(x) : fi(x) < 0 A / 2( x) < 0 Rel2(x) : fi(x) < 0 A f2( x) = 0 Rel3(x) : /i(x) < 0 A f2 [x) > 0 Rel4(x) : /iW = 0 A f2 [x) < 0 Rel5(x) : fi(x) = 0 A f2 [x) = 0 Rel6(x) : fi(x) = 0 A f2 x) > 0 Rel7(x) : Mx) > 0 A f2 x) < 0 Relg(x) : fx(x) > 0 A f2 x) 0 Relc,(x) • Mx) > 0 A f2 x) > 0. Thus the pullback partitions are defined are a set of points satisfying a conjunction of functional inequalities. The pullback partition associated with the first qualitative value is f-\Bx) = {x | Mx) < 0 A Mx) < 0.} (4.1) In general, equivalence classes associated with the pullback partitions are subsets of p-space that satisfy some conjunction of inequalities of the following form: /.• < TiJ /. < Tij fi = Tij CHAPTER 4. Q UALITATTVE EQ UIVALENCE SPACE 53 fi > T>,i fi > Tu. Where <, > imply that a block contains its delimiting thresholds. In Section 3.5 we established the need to distinguish connected components of the equivalence classes. The restriction that characteristic functions must be continuous can be used to demonstrate that these components have an isomorphic geometrical descrip-tion. The geometry of connected components is the topic of the next section. 4.1.2 Geometric restatement This section demonstrates that these connected pullback partitions are regions in p-space generated from plot t ing selected level sets of / . It is shown that selecting thresholds for the constants of level sets decomposes p-space into qualitatively equivalent open and closed regions. The ideas of this section are strongly dependent upon the continuity of the characteristic functions. Preliminary Definitions This section begins wi th a preliminary definition of level sets and contour graphs. We show that contour graphs are a decomposition of p-space into inequality invariant regions. To assist exposition and visualization, the bivariate function / ( x i , x 2 ) , whose graph is portrayed in Figure 4.1, is used to demonstrate the major ideas of this section. A l l arguments can be generalized to higher dimensional functions. CHAPTER 4. QUALITATTVE EQUTVALENCE SPACE 54 Figure 4.1: Graph of / ( x i , i 2 ) CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 55 The function f(xi,x2) can also be represented as a contour map. Contour maps are constructed from level sets; a level set is a subset of p-space where a function has some constant value c Level Set = {x G p-space | f(x) = c.} Geometrically, level sets of a bivariate function are obtained by projecting horizontal cross-sections of the graph of / vertically from the surface of the graph to the xx, x2-plane. Figure 4.2 portrays the cross-sections corresponding to the level sets: f(x1,x2) = T i f(xux2) = T2 (4.2) f(xi,x3) = T3 Figure 4.3, illustrates the projections associated with Ti,T2. Cross-sections divide the graph of / into continuous surfaces that are identical to the subintervals Bi. For example, if B is the partition {(—oo,Ti), [ T i , T2], (T2, T 3 ) , ( T 3 , 0 0 ) } then this partition contains the same elements enclosed within cross sections shown in Figure 4.4; both are subsets of Image(f) defined as: Bx = {x\x< Tx} B2 = {x I Tx < x < T2} (4.3) B3 = {x I T2 < x < T3} B4 = {x\x> T3} CHAPTER 4. QUALITATTVE EQUTVALENCE SPACE Figure 4.2: Cross-sections associated with X i , T 2 , X 3 CHAPTER 4. QUALITATTVE EQUTVALENCE SPACE Figure 4.3: The projections associated with the cross-section Xi and CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE Figure 4.4: Continuous surfaces can be equated to the parti t ion B . CHAPTER 4. QUALITATTVE EQ UTVALENCE SPACE 5 9 Projecting these cross-sections vertically onto the xx, x 2 -p lane partitions p-space into connected regions, called the contour map. A region R is topologically connected if V x j , x 2 G R there exists a continuous path P ( x t ) such that every x,- £ R. In simpler terms this means a curve can be drawn connecting the two points which does not cross a level set. We now informally argue that if a contour map is constructed from the subinterval boundaries of the blocks Bi then the resulting decomposition of p-space is composed of the blocks of a connected pullback partitions of / - 1 ( f ? ) . To illustrate, consider the block B2 defined in Equation 4.3; the associated pullback part i t ion is f-\B2) = { ( x 1 , x 2 ) I Tx>f{xux2) T2} B y the definition of function these sets are mutually disjoint. Following as a corollary, we know that two level sets cannot intersect. If / is continuous then connected components of Si are separated from the connected components of S2 by the curve / ( x ) = T2\ any path connecting a member of Si to S3 must traverse through a point x £ S3. This assertion derives from the intermediate value theorem which guarantees that if a function / is continuous over a surface that contains the points / ( x j ) , a n d / ( x 2 ) where (f(xi) < f(x2)) then there exists at least one value x, for c satisfying the inequalities ( / ( x i ) < c < f(x2)) such that f(xi) = c. Informally, this theorem ensures that a function cannot "leap" values. We know that VXJ G Si Axk E S3 f{Xj) < T2 < f(xk) CHAPTER 4. Q UALITATTVE EQUTVALENCE SPACE 62 thus, using intermediate value theorem and equating T, to c, any path between Si and ^3 must traverse at least one Xi which is an element S2. In general we can assert that if p-space is decomposed using level sets wi th constant values equal to the boundaries of the I?,-, the elements of the resulting connected regions are confined to one subinterval of the image of / . App ly ing this assertion to and the contour graph portrayed in Figure 4.5, we conclude that a l l points wi thin the shaded regions are less then T2, but greater then T i . Note that the far right region also satisfies this set of inequalities. B y default, all shaded areas are are less then B2. Thus these two sets represent the connected components of The next section generalizes these ideas to properties. T h e geometry of properties. Properties and their associated partitions are easily couched in the framework of level sets and contour maps. This translation is straightforward and simply requires using thresholds for the constants of the levelsets. In Equat ion 4.1 the equivalence classes / _ 1 ( B 1 ) were redefined as the subsets of p-space satisfying a conjunction of inequalities. The connected components of inequalities were geometrically demonstrated to be connected regions of the type depicted in Figure 4.5. Thus, if the T,- are used for the constants of the level sets, the connected components of the equivalence classes / ~ a ( B ) are the subsets of p-space contained in the regions obtained by decomposing p-space wi th the fi(x) = T{j. The term critical curve is used CHAPTER 4. Q UALITATTVE EQ UTVALENCE SPACE 63 to denote these special level sets. Critical curves delimit the qualitatively equivalent subsets of p-space. This section demonstrated that level curves and contour maps are an alternate medium for generating the partitions associated with the properties. The aggregation of these partitions into a unified representation forms the foundation of the qualitative model. This foundation, called Qualitative Equivalence Space, is discussed next. 4.2 The Aggregate model Building from similar arguments of the previous section, this section first shows that the equivalence sets of the qualitative model are subsets of p-space satisfying several polynomial inequalities. Following the qualitative model is shown to be isomorphic to a decomposition of parameter space. The D„i are inequality invariant regions formed by intersecting the critical sets of all comprising characteristic functions, the transitions between these regions is given by the adjacency of these regions. 4.2.1 Inequality Restatement The inequalities introduced in Section 4.1 can be conjoined to define the equivalence classes associated with the pullback partitions Let Relij be the relation describing the jth property value of the ith property, the equivalence classes associated with the $ - 1 ( i? f ) are {x 6 p-space \ Relij(x) A ... A Relntk(x)} where k denotes the index of one qualitative value associated with the nth property. By CHAPTER 4. Q UALITATTVE EQ UTVALENCE SPACE 64 Definit ion 4.1 this formula can be written as a conjunction of functional inequalities. The geometry of these equivalence classes can be viewed as an intersection of contour graphs. The next section demonstrates that the qualitative representation is isomorphic to a decomposition of p-space wi th cri t ical curves. 4.2.2 Geometric Restatement: QES Earlier we showed that the pullback partitions are the regions delimited by the cri t ical curves fi = T , j . This section shows that the intersection of these crit ical curves corresponds to the connected pullback partitions (where 3> = ( / i , . . . ,fm)). This correspondence is substantiated by showing that every crit ical point of / , 6 (fii • • • i fm) is a crit ical point of $ and every crit ical point of $ is a critical point for some / , . These two assertions are simple to demonstrate and follow directly from the definitions of partitions and qualitative equivalence. We begin with the first assertion. A n element x € p-space is a cri t ical point associated with /,• if fi(x) is a boundary point of one or more Bij, 3i,j ft(x) EBij A (\imQ(fi(x) + e) $ Bij V ( l i m ( / t ( i ) + ^ ) ; ) ) (4.4) The elements wi th in a domain of a state are qualitatively equivalent. This requires that only one qualitative value from each property can be valid on Z)4 X. This is formulated as x E DSi -* Relij{x) V . . . V Relini(x), where rii denotes the total number of qualitative values assoicated with the ilh property. Since the validity of Relij(x) is determined by whether x € Bij, then it must be the case CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 65 that if a i delimits some Bij, then x delimits two qualitatively equivalent states; hence, x is a critical point of 3>. The contrary implication is just as simply demonstrated. A point x is a critical point of the aggregate system, if it divides two qualitative equivalent regions. The definition of qualitative equivalence defines two points as qualitatively equivalent if the same Relij are valid at these points. Therefore the boundaries the Dsi are subsets of p-space where a Relij invalidates. From the previous paragraph we know that this coincides with a point satisfy Equation 4.4. Hence if x is a critical point of (f> x is a a critical point of at least one function / , . By the above argument we know that at each critical curve associated with / , one or more qualitative values change so the aggregate qualitative description changes and the aggregate qualitative description changes only where the individual properties change qualitative values. The inclusion or exclusion of a critical curve in the -1(i?) is determineed by whether the relation associated with the critical curve corresponds to open or closed sets. The next section takes deeper look at the qualitative partial derivative; a decompo-sition of p-space using the actual partial derivatives of the two-link manipulator. 4 . 3 Qualitative Partial Derivatives and QES In Section 3.2, monotonic-dependence was introduced as the qualitative analog of par-tial derivatives. This section illustrates the qualitative model by aggregating several monotonic-dependence relations to form a qualitative gradient and Jacobian. The gen-CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 66 eral ideas are introduced first followed by an actual example using the manipulator kine-matics. In Section 2.3, the gradient of a scalar field / , ( x i , . . . , x n ) was defined as 1 dxn The qualitative analog of the gradient uses the qualitative partial derivative, monotonic-dependence. For a scalar field on n variables, the qualitative gradient requires aggregating n monotonic-dependence properties, one for each independent parameter. The charac-teristic function of the qualitative partial derivative has the form, and the partitions are al l sign-invariant. The composite model is thus and the associated part i t ion 5,- = { ( -oo ,0 ) , [0 ] , (0 ,oo)} n . For a bivariate scalar field, the qualitative gradient has one of the forms illustrated in Figure 4.6. W i t h i n an equivalence class, each element is sign invariant. Thus each Dsi is a mapping from a subset of p-space to { M I , M D , S } n , where n represents the number of independent parameters. The qualitative Jacobian for a vector field a similar form. The Jacobian is the collec-tion of partial derivatives of the vector field / = / i e i + . . • + / m e m CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 67 Qualitative Gradients [-,-] [-,0] [-,+] [0,-] [0,0] [0,+] [+,-] [+,0] [+,0] Figure 4.6: The qualitative gradients of a bivariate scalar field. CHAPTER 4. Q UALITATTVE EQ UTVALENCE SPACE 68 where each row i is the gradient associated wi th fi r 3xi dfm - 8x\ dfm 3x„ thus $ = (—(x 1,...,x n)..., df (xi,..., *»)) dx n For a vector field / = (/i, / 2 ) of two variables the label set of each Dsi is Lai e{MI,MD,S}4. 1 W i t h i n each DJ the signs of al l the partial derivativs are sign-invariant The next section demonstrates the qualitative gradient, Jacobian, and associated Q E S model for the robotic manipulator. 4.3.1 Example: The Robotic Manipulator The kinematic relations of the two-link robotic manipulator can be described in qualita-tive form by a decomposition of C-space2 wi th the critical curves The multivariate coordinate functions Xi(ji,... jn) are transformations from C-space to workspace. The first partial derivative |^»- (k = 1,..., m) give the rates of change of Xi measured in the direction of positive jk. 1It is necessarily the case that every possible combination of these qualitative values can be physically realized by a system; The union of all L„- may only be a subset of {MI, MD, S}4. 2Recall from Section 2.1, that C-space is the cross product of the joint parameters dX i = -L sin(ji) - L sin(ji + j2) (4.5) dn CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 69 dX = Ls\n(ji+j2) (4.6) dX - r r ^ = LcosO'O + XcosO'! + j2) (4.7) ^ = LcosCji+ia) (4.8) The associated decompositions of p-space are depicted in Figure 4.7 Each decomposition is generated from plott ing the crit ical curves OJk In these diagrams the shaded regions correspond to MI, solid lines S, and the white regions MD. The aggregation of the partial derivatives given in Equations 4.5, 4.6, 4.7 and 4.8 are the gradients V X ^ j i , ^ ) and VX2(ji,j2) respectively. The associated decompositions of C-space corresponding to the qualitative description of these is depicted in Figure 4.8. Each pattern represents a different sign combination. The Jacobian aggregates the elements of the gradients, VXx(ji, j 2 ) a n d V A " i ( j i , j2) the resultant qualitative equivalence space is shown in Figure 4.9. State transitions are given by the adjacency of the regions. A state change implies a qualitative value of the partial derivative w i l l change to or from static. Describing the foundations of qualitative models in a concise framework has several advantages. We have demonstrated that this framework eased the extension of qualita-tive properties to include domains like robotic manipulator kinematics. A n additional advantage of this framework is that it reveals that qualitative models fit a broader family Figure 4.7: The qualitative partial derivatives of the two-link manipulator. Figure 4.8: The qualitative gradients of the two-link manipulator. F i g u r e 4.9: T h e q u a l i t a t i v e J a c o b i a n of the t w o - l i n k manipulator. CHAPTER 4. QUALITATTVE EQ UTVALENCE SPACE 73 of geometric problems. In particular, for those systems whose characteristic functions have polynomial form, the existence of a desirable qualitative state can be reformulated as a decision problem in the theory of the reals[5]. The next section describes this family of problems. 4 .4 C o m p u t a t i o n a n d Q E S The previous section redefined state domains as connected subsets of some 3£n that satisfy a conjunction of functional inequalities and potential state transitions as the adjacency of these regions. If the characteristic equations have algebraic descriptions, the qualitative model can be encoded in the theory of the reals and the D3{ as semi-algebraic sets. Given a formula as a boolean combination of polynomial inequalities, a semi-algebraic set in Rn is a set of variable values for which a formula is true. [5] [20] A formula is defined as a logical construction of atomic formula where an atomic formula has the form fi x o where < € {<,<,=,>,>} and each /,• is a polynomial in n real variables. If the $ is composed of polynomials of this type then, in principle, algorithms based on algebraic cell decomposition can used to generate the connected qualitatively equivalent Dsi, and the existence of a transition Tij can be proved by computing cell adjacency [34] Several algorithms have been developed, particularly in the area of robotic motion CHAPTER 4. QUALITATTVE EQUTVALENCE SPACE 74 planning to construct algebraic-varieties. For example the algorithms of [4] and [7] based on algebraic cell decomposition [5] can be used to generate these sets. Unfortunately they do not contain the adjacency information needed to ensure connectivity[20]. In [20] Yap and Kozan provide a cell decomposition which has the adjacency information necessary to construct the connected components of $ . We wi l l use the notation of Yaps formalism to show the relation between constructing algebraic-varieties and the Dsr Given a set E of polynomials with rational coefficients in d variables a sign assignment maps a : E —• —1,0,+1. Each sign assignment sigma represents an equivalence class Xa = {xe$d\ sign({p{x)) = a{p(x)), p G E} called the sign classes of a. The consistent sign classes are the non-empty sets. Yap's algorithm finds the connected sign classes of a given set of polynomials and pro-vides full adjacency of these classes. Our domain is easily translated into this framework given $ = / i , . . . , / n then £ = {9i I 9i = fi ~ Tid V i , j = 1 . . . n,} where n,- denotes the the total number of thresholds associated wi th fi. The connected pullback partitions can be generated by util izing adjacency information to union the resulting sign classes. Unfortunately these algorithms are double-exponential in the number of variables just in the case of polynomial functions. Ce l l decompositions for analytic functions are CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE 7 5 even more challenging. However, if thresholds are time-invariant, the time complexity of these algorithms is not a hindrance. Chapter 5 Comparisons and Usage The previous chapter established some of the theoretical underpinnings of qualitative models. State domains of a qualitative state were shown to be connected regions delimited by the cri t ical curves of properties. This chapter uses the geometry of state domains to demonstrate that current qualitative frameworks are l imited to either properties whose cri t ical curves are parallel with the axes of p-space, or properties whose critical curves are reduced to a restricted class of bivariate functions. Also , the uti l i ty of qualitative partial derivatives and the advantages of a mathematically precise representational framework are demonstrated wi th a hypothetical control scenario involving the robotic manipulator. 5.1 Q E S A n d E x i s t i n g R e p r e s e n t a t i o n s Currently, the types of reasoning performed by existing qualitative representations di-vides into two branches: dynamics and kinematics. Dynamic systems model how the behavior of a system changes over prolonged periods of time. In the manipulator do-76 CHAPTER 5. COMPARISONS AND USAGE 77 main, dynamics would model the path an end-effector follows in response to a series of joint actuations. Kinematics is the study of the spatial properties of motion. A kinematic analysis of the manipulator domain determines the possible motions of the end-effector at each configuration. Al though qualitative representations used by existing dynamic and kinematic systems are general enough to make the qualitative distinctions needed for their specific applications. They are unable to meet the representational demands of general multivariate properties. This section explains the source of these representational shortcoming. 5.1.1 Qualitative Dynamics and multivariate properties The fundamental l imi ta t ion of current representations used to model dynamics is that they solely support properties whose crit ical curves are parallel to the basis vector. For crit ical curves associated wi th the characteristic function f(x\,... ,xn) these are If cri t ical curves of this type are plotted in p-space, the shape of the Dsi are restricted to hypercubes. Figure 5.1 shows how this l imitat ion constrains Q E S in the case of a two dimensional p-space. This geometric l imitat ion is too restrictive to model the shape of the general critical curve for multivariate properties. The value of the characteristic function for a multivari-ate property / ( x i , . . . , x n ) is dependent on each x t . This dependence is mathematically c (5.1) where x,- 6 { x 1 ? . . . , Zn}-CHAPTER 5. COMPARISONS AND USAGE 78 Crimed Figure 5.1: The D „ of existing dynamic systems are hypercubes. stated as The functions representing the critical curves of multivariate properties are also multi-variate. To date, the representational framework described in Equation 5.1 has been a suffi-cient basis for qualitatively modeling dynamic because the characteristic equations of ex-isting systems are univariate. In particular, all existing frameworks for dynamic systems [16][32][10][22] are concerned with quantities that change as a function of time; therefore, the rate of change of a characteristic function /(x,-... x n) is viewed as a univariate func-tion of time under the constraints X i ( i ) , . . . ,x n(t). Substituting these constraints into / CHAPTER 5. COMPARISONS AND USAGE 79 leads to a new univariate of time To fully appreciate the corresponding reduction in the representational complexity of univariate properties, the time behavior of the end-effector is examined. In the robotic manipulator paradigm, the time behavior of the end-effector is a path Xi(Ji(t),...,jn(t)) corresponding to a constrained set of joint values, ji(t). This set is alternatively viewed as a continuous path in C-space, this alternative view is illustrated in Figure 5.2. Analyt ical ly the time derivative of Xi relative to a joint k is given by the chain rule as dXj djk. . djk dt [ ) where ^j*- denotes the rate of change of joint k wi th respect to time. This model reduces the partial derivatives associated wi th monotonic-dependence from functions of j , to a function of t. The are known as a function of time, hence using substitution again, the partial derivatives can be determined as functions of time, ^ i { m . . . j n { t ) ) ^ ^ l ( t ) . OJk OJk The Monotonic-dependence between a joint and a coordinate changes value at those points i n C-space where the path ji(t) intersect the critical curves of the unconstrained CHAPTER 5. COMPARISONS AND USAGE 80 J2 • J1(t). J2(t) C-SPACE Figure 5.2: The set of joint values ji(t) defines a path in C-space. partials (See Figure 5.3). Evaluations of are sign-invariant at the values of ji(t) that range between intersections. This reduces the complexity the and enables the critical curves delimiting these sets to be described in the manner given in Equation 5.1. The delimiters of the D,i can be described as either points in the p-space t (Kuipers [22], Sacks [32]) or as hypercubes , delimited by the lines ji = c. where c denotes a value of j,(t) which intersects a critical curves associated with the full p-space. This type of description is used by Forbus [16], and de Kleer [10]. Figure 5.3 illustrates these alternative descriptions of Neither of these representations are sufficient for representing qualitative partial derivatives or aggregations or partial derivatives. A complete description of the qual-CHAPTER 5. COMPARISONS AND USAGE 81 IKD. |2(t) • • • • ? Figure 5.3: Monotonic-dependence changes qualitative values at intersections, itative Jacobian requires the ability to describe Z}„- as an intersection arbitrary shaped critical curves in n variables. This section has compared the qualitative models used by existing dynamic systems with QES and demonstrated that current models cannot meet the representational needs of the general multivariate property. Representations for multivariate properties are also needed for modeling the qualitative kinematics of mechanisms. The next section discusses the qualitative modeling of free-axis and fixed-axis mechanisms. 5.1.2 Qualitative Kinematics The components of a kinematic chain have either free or fixed axes. The difference between a fixed axis and free axis is that the reference frame of a fixed-axes component CHAPTER 5. COMPARISONS AND USAGE 82 is fixed while the reference frame of a free-axes component varies. For example, the reference frame of link one in Figure 2.3 is fixed while that of l ink two varies as a function of the joint parameter of the first l ink. Current qualitative kinematic formalisms use a modeling framework which is sufficient for mechanisms composed of fixed-axes components but cannot meet the representational needs of free-axes components. The first half of this section w i l l demonstrate that existing qualitative kinematic formalisms complement the qualitative framework proposed in this thesis. The second half of this section explains why existing kinematic frameworks cannot encompass the representational needs of free-axis mechanisms. Quali tat ive kinematic systems describe the possible displacements of the components of a kinematic chain relative to other components in the kinematic chain. The qualita-tive kinematic frameworks proposed by Forbus[17], Faltings[14][17], Nielson[25][17] and Joskowicz [19], can be understood in terms of properties. A common premise used in each of these formalisms is based a mechanical observation made by Realeaux[30]. This observation is summarized as "Force in a fixed-axis mechanism is transmitted through contact and the net force is determined by summing the individual forces of each con-tacting pair". Joskowicz has extended Realeaux's proposition to kinematics, proving that the motion of any component in a kinematic chain can be separated into the pairwise motions between contacting components. If two components i and A; in a kinematic chain are in contact, Joskowicz asserts The dependence of component i on j is a function of the joint parameters of the contacting djk (jijk)-CHAPTER 5. COMPARISONS AND USAGE 83 pair. Joskowicz also states that the total differential displacement is linear and can be determined by adding the differential displacements incurred by each contacting pair. Joskowicz's claim coincides wi th the modeling formalisms presented in this thesis. In order for a component to impart displacement to another component, these components must be topologically connect. In the framework of this thesis, connectivity is viewed as a property whose qualitative values are contact, no-contact, and overlap. The qualitative value overlap is used to describe inadmissible configurations. B y Joskowicz's assertion the p-space of the property connectivity is the cross-product of the joint parameters of the contacting components. In [14] Faltings provides an algorithm to decomposition this p-space. This algorithm uses a set of functions he denotes applicability functions. These functions are analogous to the characteristic functions of complex properties; determining the signs of applicabili ty functions classifys the connectivity of two parts as contact, no-contact and overlap. Faltings algorithm is an algebraic decomposition of the type discussed in Section 4.4. The decompositions induced by Faltings algorithm can be further refined to distinguish if the dependence between two components is MI, MD, or S. Determining this dependence is the topic of [25]. The motion of a free-axes components, such as the such as the end-effector can-not be described using the pairwise component models. The dependence between the components in a fixed-axes kinematic chain cannot be described in a pairwise param-eter space. The partial derivative is a function of the joint parameters of every link in the kinematic chain. A n y subset of these parameters leads to ambiguity, because the monotonic-dependence between the end-effector and a l ink can change despite the fact CHAPTER 5. COMPARISONS AND USAGE 84 that the value of the joint parameter of the l ink did not vary. Model ing the kinematics of free-axes mechanisms, requires functions on the full c-space. 5.2 R e a s o n i n g a n d C o n t r o l This section presents a simplified control scenario which demonstrates the potential use of the qualitative Jacobian and illustrates the merits of a formal definition of quali-tative models. One aspect of controlling the trajectory of an end-effector entails selecting values of ji(t) that correspond to a desired path Xi(t) in W-space. In simpler terms, answering the question, "How can we articulate the joints to cause the end-effector to move towards a point p in workspace". A t each configuration j £ C-space, the consequence of differential rotation Aji of joint i is differential translation (AXl,..., AXn)1 of the end-effector. This translation is mathematically stated as, Vi AXi = I^Aj,, If this transition is described by its direction using the qualitative values increasing, decreasing and static the qualitative differential is given by OX-sign(AXi) = sign(-^)sign(Aji). In theory, the monotonic-dependence relations in conjunction with the desired sign of the differential translations could be used to select appropriate Aji. In a control *A 0 value of a differential translation is possible if the dependency relation is static CHAPTER 5. COMPARISONS AND USAGE 85 scenario, the A j , are the control choices, the A X , are the objectives, and the monotonic-dependence relations are the constraints. The relations MD, MI, S provide the informa-tion needed to determine the resulting direction of translation of X , given the sign of Ajk- For example, if the dependence relation between a coordinate Xi and a joint jk is MDik, we know a positive value of Ajk implies A A", w i l l be negative. Positive and zero valued Vjk result in positive and zero differentials, respectively. Similar reasoning applies to the dependency relation MI. In this case the same Ajk wi l l result in a A X , that is opposite in sign to MD. If the relationship between a coordinate and a joint is static (has the qualitative value S) a differential translation of the joint w i l l not cause the coordinate value to alter. W i t h i n a state domain monotonic-dependence is invariant. A t the crit ical curves the monotonic-dependence changes value, implying that the same sign of Ajk w i l l no longer render the same sign of AXi. The total displacement of the end-effector is a composition of the differential dis-placements incurred by actuating each joint. This net composition is called the total differential. The differential displacements are locally linear and thus for a n - D O F ma-nipulator whose workspace is a subset of 9 t m , the t ime derivative coordinates are, dt dXx djx djx dt + ...+ dXm djn djn dt dX, dt m dXm dH djn dt +... + dXm djn djn dt ' and the total differential is AXX dX i Adjx + ...+ dX, m Adj, dji djn n CHAPTER 5. COMPARISONS AND USAGE 86 AXm = ^ A d j 1 + ...+ ^ A d j n . The qualitative total differential leads to ambiguity because the information provided by the monotonic-dependence property is insufficient to determine the resultant sign of AX{. If one joint causes a coordinate to increase, while the other joint causes the coordi-nate to decrease the net displacement cannot be determined without further information. Selecting appropriate signs of Aji for is analogous to solving a set of simultaneous equa-tions. Reasoning systems for choosing consistent solutions of this type can be found in [22] and [10]. The ut i l i ty of qualitative partial derivatives is better demonstrated in a more complex domain. Frequently a desired trajectory of the end-effector is required to satisfies several other criterion. For example, the orientation of the elbow must be controlled and obsta-cles must be avoided. B o t h elbow orientation and obstacle zones can be integrated as additional properties in Q E S . In the case of the elbow, the relevant qualitative values are elbow-up, elbow-down, and straight-arm. Obstacle contact additionally fits the mathe-matical framework of properties, algorithms by [29] and [13] part i t ion C-space according to obstacle and free zones. A n additional qualitative property that could be beneficial to computation is classify degenerate and nondegenerate configurations. Degeneracies occur when a manipulator loses a degree of freedom. These degeneracies can be determined by examining the eigenvalues. The advantages of of a qualitative description is that the objectives are weaker, thus several combinations of joint displacements may be able to CHAPTER 5. COMPARISONS AND USAGE 87 satisfy thes objective. A reasoner could conceivable provide the choices of sign(AJk) which could achieve a set of desired set of A X , and eliminate these choices according to whether they satisfy other constraints such as preferred elbow configurations. The proposed qualitative framework clarifies how to aggregate both the kinematic relations needed for controlling the end-effector, other important manipulator character-istics into a unified representation. Chapter 6 Conclusion and Future Work For a newcomer the existing qualitative modeling frameworks can be a bit perplexing. Two years ago an unsuccessful attempt was made to cast the kinematic relations of a robotic manipulator using existing representational frameworks for dynamics Kuipers[22], de Kleer[10], and Forbus [16]. Moreover, existing kinematic frameworks proposed by Falt-ings [14], Joskowicz [19] and Forbus [16] were not applicable to the manipulator either. The sources of these inapplicabilities was not readily apparent. However, identifying this source was pivotal to the extensions of qualitative representations. The lessons gleaned from investigating this inabili ty are contained in this thesis. Despite the differences of ex-isting formulations, closer examination reveals several mathematical commonalities. This thesis has attempted to provide for the theoretical underpinnings of these commonalities in hopes to ease the application of qualitative reasoning to new domains such as manip-ulator control. To close this thesis, results are summarized, and open representational issues are outlined. 89 CHAPTER 6. CONCLUSION AND FUTURE WORK 90 6.1 S u m m a r y This thesis provides the mathematical foundations of qualitative models in terms of continuous functions and partitions. The qualitative model is a graph G containing a symbolic characterization of a system. The nodes of the graph are qualitative states, and the possible changes are contained in the transitions. Each state has two components Dsi and Lai denoting the state domain and label. Each Lai is a set of relations associated with qualitative values. For a system defined with n properties, Dai —* Reh x . . . x Reln. This thesis demonstrated that: 1. The Dai are connected equivalence classes in 3£n satisfying a conjunction of inequal-ity relations between the characteristic functions fi and the thresholds. Geometrically these are regions in p-space delimited by the components of the critical curves / , = Tij. 2. Lai is the set of relations Relij valid on the Dsi. A relation is a member of Lsi if Vx € Dai x e f-\Bij) -* ReUj e L3i. 3. The maximal set of possible state transitions Tsi is isomorphic to the adjacencies of the Dsi. Symbolically TT~crJ7i -> sj e Tsi i <> j. CHAPTER 6. CONCLUSION AND FUTURE WORK 91 This framework was used to show that the inabilities of current representations to handle multivariate properties is due to the restricted geometry of existing domain de-scriptions. Section 1.1 established the family of properties which would be modeled in this thesis. Relaxing these restrictions opens the door to to further research. The last section of this thesis introduces open representational issues. 6.2 F u t u r e W o r k This thesis has been limited to a restrictive class of properties, specifically those with continuous functions that share the same parameter space. In addition the thresholds of properties were required to be deterministic so that qualitative model was time invariant. A natural set of extensions to the proposed framework is the integration of properties that violate these limitations. Following is a Listing of existing restrictions and a comment on their elimination. Discontinuities: The Intermediate Value Theorem was used to argue that connected components of / i - 1(J3) are contained between the critical curves. This theorem relies on the continuity of the characteristic functions. Extending the existing formalism to permit piecewise continuous characteristic functions is relatively simple. Characteristic functions with finite discontinuities can either be defined as a sequence of piecewise continuous functions and QES can be constructed by juxtaposing subsets of p-space in a manner similar to [33]. [13] and [28] also deal with merging partial functions of this sort. An alternative solution is to include special thresholds to account for discontinuities. CHAPTER 6. CONCLUSION AND FUTURE WORK 92 Thresholds can be extended to include nominal thresholds to represent singularities, and other discontinuities. Differing p—spaces: As yet we have only discussed aggregating properties which share the same parameter space. Two extensions are aggregating properties that share subsets of the same p-space, and properties who have no parameter in common. Com-posing the pullback partitions of properties which share a subset of the same property involves intersections and projections. This would be similar to robotic issues addressed in [29] and compositions of applicability constraints discussed by [14]. Properties that had no common parameters are easily modeled. The Dsi resulting from aggregating properties with different p-spaces is simply the cross-product of the individual pullback partitions. Curves as Thresholds: The partition B of the complex properties was restricted to intervals in the images of the fi . A further extension is to permit threshold curves in the cross-product of the images of the fi. All previous arguments can be shown to be valid under this extension. Time-vary ing Properties: The qualitative graph defined so far is time invariant; thresholds do not vary in time and are precomputable. It is forseeable that important properties may not qualify under this constraint. A good example is mobile obstacles. The complexity involved in generating p-space decompositions becomes a hindrance, since changing a threshold requires recomputing QES. Bibliography [1] Ralph H. Abraham and Cristopher D. Shaw: "Dynamics-The Geometry Of Behavior Part One: Periodic Behavior", Aerial Press Inc., P.O.Box 1360, Santa Cruz, California, 1985. [2] V.I. Arnold: "Mathematical Methods of Classical Mechanics", Springer-Verlag, New York, 1978. [3] K. Asakawa, F. Tabata and H. Komoriya: "A Robot with Optical Position Feedback", Proceedings of IEEE Industry Applications Society, pp. 1276-1281, October 1982. [4] M . Ben-Or, D. Kozen, and J. Reif: "The Complexity of Elementary Algebra and Geometry", J . Comp. and Sys. Sciences, Vol. 32, (1986), pp. 251-264. [5] J . Canny: "The Complexity of Robot Motion Planning", MIT Press, Cam-bridge Massachusetts,1989. [6] Y . C Chen and Vidysagar: "Some Qualitative Results On the Collision Free Space of Planar n-DOF Linkages", Proceedings of IEEE Int. Conference on Robotics and Automation, 1987. [7] Collins G . E and Loos R.: "Real Zeros of Polynomials", Computing Supplemen-tum 4, (1982) pp. 83-94. [8] J .J Craig: "Introduction To Robotics", Addison-Wesley, 1986. [9] Ernest Davis: "A Logical Framework for Solid Object Physics," New York University Technical Report 245, October 1986. [10] Johann de Kleer, John Brown: "A Qualitative Physics Based on Confluence", Artificial Intelligence Journal, 24 1984. 93 BIBLIOGRAPHY 94 [11] Johann de Kleer: "Qualitative and Quantitative Knowledge in Classical Me-chanics," MIT A l Lab TR-419, January 1978. [12] J . Denavit, R.S. Hartenberg: "A Kinematic Notation for Lower-Pair Mecha-nisms Based on Matrices," Journal of Applied Math, 22, 1955 [13] Bruce Donald: "Motion Planning with Six Degrees of Freedom," MIT A l Texh. Report 791, May 1984. [14] Boi Faltings: "A Theory of Qualitative Kinematics in Mechanisms,", UIUCDCS-R-86-1274, University of Illinois, 1986. [15] Ken Forbus: "A Study of Qualitative and Geometric Knowledge in Reasoning about Motion", TR-615, MIT A l Lab, Cambridge, M A , 1981. [16] Ken Forbus: "Qualitative Process Theory", MIT A l T R 789, July 1984. [17] Ken Forbus, Paul Nielsen, and Boi Faltings: "The Inferential Structure of Qualitative Kinematics," Proceedings of IJCAI 87, Milan, Italy, 1987. [18] Andrew Gelsey: "Automated Reasoning about Machine Geometry and Kine-matics," Proceedings of 3rd IEEE Conference on Al Applications, Orlando, Fla, Febuary. 1987. [19] Leo Joskowicz: "Shape and Function in Mechanical Devices," Proceedings of AAAI-87 Sixth National Conference on Artificial Intelligence, 1987. [20] Mieczyslaw M . Kokar: "Critical Hypersurfaces And The Quantity Space", Pro-ceedings of AAAI-87 Sixth National Conference on Artificial Intelligence, 1987. [21] D. Kozen, C K . Yap: "Algebraic Cell decomposition in NC", extended abstract, Proceedings of 26th FOCS, Oct. 1985. [22] Kuipers, Ben: "Commonsense Reasoning about Causality: Deriving Behavior from Structure" Artificial Intelligence Journal 24, 1984. [23] V. Milenkovic, and B. Huang: "Kinematic of Major Robot linkages", Proceed-ings of 13th Conference on Industrial Robots, 1983. [24] D.McCloy and M.Harris: "Robotics An Introduction", Open University Press, New York, 1986. [25] Paul Nielson: "A Qualitative Approach to Rigid Body Mechanics," Ph.D. the-sis, to appear: 1988. BIBLIOGRAPHY 95 [26] R. Paul: "Robot Manipulators: Mathematics, Programming and Control", MIT Press, Massachusetts, USA, 1981. [27] Helen R. Pearson and James R. Smart: "Geometry", Ginn and Company, Boston, 1971. [28] Tomas Lozano-Perez: "Spatial Planning: A Configuration Space Aproach", IEEE Transactions on Computers, Vol. C-32, Number 2, pp 108-120,1983. [29] Tomas Lozano-Perez: "A Simple Motion-Planning Algorithm for General Robot Manipulators", IEEE Journal of Robotics and Automation, Vol. RA-3, NO. 3, June 1987. [30] Franz Reuleaux: "The Kinematics of Machinery", Dover Publications, Inc., New York, 1876. [31] Steven Roman "Discrete Mathematics" Saunders College Publishing Philidel-phia, PA 19105 1896. [32] Elisha Sacks: "Qualitative Mathematical Reasoning", Proceedings of IJCAI-85, 1985. [33] Elisha Sacks: "A Dynamic Systems perspective on Qualitative Simulation", to appear Artificial Intelligence Journal. [34] J.Schwartz, M.Sharir: "On the Piano Movers Problem 11. General Techniques for Computing Topological Properties of Real Algebraic Manifolds," Advances in Applied Mathematics 4(1983) pp. 298-351. [35] Al Shenk: "Calculus And Analytic Geometry", Goodyear Publishing Company Inc., Santa Monica, California, 1977. [36] Yoav Shoham: "Qualitative Kinematics," Proceedings of the 9th IJCAI, Los Angeles, August 1985. [37] P.N. Sheth and J.J. Uicker, Jr.: "IMP, A Computer-Aided Design analysis System for Mechanisms and Linkage", Transactions of the American Society of Mechanical Engineers, May, 1972. [38] Young, H.D: Fundamentals of Mechanics and Heat, Second Edition, McGraw-Hill book company, 1964.