Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A qualitative representation for manipulator kinematics and other vector and scalar fields Dangelmaier, Heidi Therese 1989

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

Item Metadata

Download

Media
831-UBC_1990_A6_7 D36.pdf [ 4.13MB ]
Metadata
JSON: 831-1.0051955.json
JSON-LD: 831-1.0051955-ld.json
RDF/XML (Pretty): 831-1.0051955-rdf.xml
RDF/JSON: 831-1.0051955-rdf.json
Turtle: 831-1.0051955-turtle.txt
N-Triples: 831-1.0051955-rdf-ntriples.txt
Original Record: 831-1.0051955-source.json
Full Text
831-1.0051955-fulltext.txt
Citation
831-1.0051955.ris

Full Text

A QUALITATIVE REPRESENTATION FOR MANIPULATOR KINEMATICS AND OTHER V E C T O R AND SCALAR FIELDS by •  HEIDI THERESE DANGELMAIER B.Sc.,Western Washington University, 1986  . A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE D E G R E E 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  degree freely  at  this  the  thesis  in  University of  partial  of  department  this or  publication of  thesis for by  his  or  Department  that the  her  representatives.  The University of British Columbia Vancouver, Canada  i9?9  for  an advanced  Library shall make  agree that permission for  It  this thesis for financial gain shall not  lh  requirements  scholarly purposes may be  of  OCT  the  British Columbia, I agree  permission.  DE-6 (2/88)  of  available for reference and study. I further  copying  Date  fulfilment  is  granted  by the  understood  extensive  head  that  be allowed without  it  of  copying  my or  my written  A b s t r a c t  Over the last several years a branch of Artificial Intelligence called Qualitative Reasoning 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 qualitative 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 motivation, this thesis answers the following: What is a Qualitative model? Although current approaches appear diverse, they share a common mathematical foundation. This foundation 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 associated 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.2 1.3 1.4 1.5 1.6  1  Properties: Basic definitions and Restrictions Why robot manipulators? What Is A Qualitative Model? Qualitative Equivalence Space Contributions Thesis Overview  2 Manipulator Background  2.1 Manipulator Structure and Description 2.2 Kinematics 2.3 The Mathematics Of Forward Kinematics 2.4 Qualitative Properties and Manipulator Kinematics  3 A Framework For Qualitative Representations  3.1 Property restated 3.2 Example properties 3.2.1 The Qualitative Partial Derivative 3.3 The Qualitative State 3.3.1 The Pullback Partition 3.3.2 Property Compositions 3.4 State Transition  iii  3 7 10 11 13 14 15  15 18 20 23 28  29 32 36 40 42 45 47  4 Qualitative Equivalence Space 4.1  4.2  4.3 4.4  50  Property Reformulation 4.1.1 Analytic restatement 4.1.2 Geometric restatement The Aggregate model 4.2.1 Inequality Restatement 4.2.2 Geometric Restatement: QES Qualitative Partial Derivatives and QES 4.3.1 Example: The Robotic Manipulator Computation and QES  5 Comparisons and Usage 5.1  5.2  77  QES And Existing Representations 5.1.1 Qualitative Dynamics and multivariate properties 5.1.2 Qualitative Kinematics Reasoning and Control  6 Conclusion and Future Work 6.1 6.2  77 78 82 85  89  Summary Future Work  90 91  Bibliography  93  iv  r  51 51 54 64 64 65 66 69 74  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 1.3 1.4  A canonical robotic manipulator Manipulator control overlaps the focus of kinematics and dynamics. . . . QES, an intermediary representation  8 9 11  2.1 2.2 2.3 2.4  A n abstraction of a two-link revolute manipulator The lack of inverse kinematic equations is frequently due to redundancy. The end-effector trajectory, with ji = c Kinmatics described using the qualitative values Increasing(l),Decreasing(D), and Static(S)  17 20 25 26  3.1 3.2 3.3 3.4 3.5 3.6 3.7  A property is composed of a function and a partition Properties, partitions, and characteristic functions Point-type, a complex property Monotonic-dependence and the manipulator A partition on p-space associated with a property and its partition B. . . The pullback partition To ensure consistent transitions, state domains must be connected. . . .  33 34 35 39 42 43 49  4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9  Graph o f / ( x i , x ) Cross-sections associated with T\, T?, T The projections associated with the cross-section T\ and T Continuous surfaces can be equated to the partition B The contour map for f(x\,X2) and Ti, 7/2,7/3 The qualitative gradients of a bivariate scalar field The qualitative partial derivatives of the two-link manipulator The qualitative gradients of the two-link manipulator The qualitative Jacobian of the two-link manipulator  55 57 58 59 61 68 71 72 73  5.1 5.2  The D i of existing dynamic systems are hypercubes The set of joint values j,-(t) defines a path in C-space  79 81  2  3  2  s  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: M y dear neighbors and so much much more, your care and support made a difficult summer beautiful. A n d 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 deduced from knowing its relevant qualitative properties [35] [1]. A m o n g the most informative qualitative properties are sign, slope-sign, and concavity. K n o w i n g these properties, an approximate graph depicting the behavior of a function can be generated. A l t h o u g h 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. T h i s characterization is qualitatively analogous to knowing the derivative. This description provides locations of the local extrema and intervals i n the domain where the value of the function is increasing, decreasing, and static. A l t h o u g h classifying slope as increasing,  decreasing, and  static is not informative enough to distinguish variations i n 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 dependence 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.  3  INTRODUCTION  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 identified. 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 issues 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 properties 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  f'{t).  1.  INTRODUCTION  5  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 a l 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. T h i s 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]. T h e above properties, although apparently dissimilar share an underlying mathematical structure. T h i s structure has been used implicitly i n previous representations but has never been made explicit. T h e premise assumed by existing systems is that all properties have two common components, a characteristic function and a p a r t i t i o n on the image of that function. T h e characteristic  function  is a continuous mapping from a set of parameters that we  call p-space to a image(a subset of  Characteristic  R)  function  m  : SK™ —• SR™ where m,n 7  > 1.  T h e p-space of a univariate property is linear while that of a multivariate property is  CHAPTER  1. INTROD  UCTION  6  a manifold i n 3ft", n > 1. For example p-space associated w i t h fluid flow in a pipe is the cross-product of fluid density p, pipe diameter D, fluid viscosity 77, and fluid velocity v. T h e second common component is a partition on the image of the characteristic function. T h i s p a r t i t i o n is a finite set of intervals that serve as to decompose the continuous range of a function into groups which exhibit similar behavior. responds to one qualitative value.  E a c h subinterval cor-  T h e 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. T h e property slope-sign illustrates the concepts of characteristic functions and thresholds. T h e slope-sign of the continuous function f(t) function / ' ( £ ) , the derivative of f(t).  is classified using the characteristic  Determining the qualitative values of this function  is achieved using zero as a threshold. < 0 = 0 > 0  then then then  / ( £ ) is Decreasing at t f(t) is Static at t f(t) is Increasing at t  In Section 4.3 it is shown that the qualitative partial derivative fits this framework. T h e p-space  of properties is also subject to restrictions. T h i s 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 i n 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  CHAPTER 1.  INTRODUCTION  7  range. Symbolically / ( x i , . . . ,x ) = / i ( x ! , . . . ,x )e! + . . . + f (xi,... n  where e i , . . . , e  m  n  m  ,z )e , n  m  are the basis vectors.  Comments on how violations of the outlined restrictions affect the proposed framework can be found in Section 6.2. 1.2  W h y  robot  manipulators?  The absence of a general representation for multivariate properties was discovered during an effort to describe symbolically the kinematics of a robotic manipulator. The manipulator 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 mathematics. 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 properties. • 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.3  1.  INTRODUCTION  W h a t  A Qualitative  Is A  10  Qualitative  M o d e l ?  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 i n 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 i n the graph reflect  the behavioral changes a system can undergo.  For systems described w i t h properties,  states are invariant w i t h respect to the qualitative values. State transitions occur when a qualitative value is no longer applicable. T h i s 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 w i t h state transitions.  If a system can transit through  two different qualitative values by continuous changes of its parameters, this transition is recorded i n the set of state transitions. T h e quantitative analog of transitions are limits. We show that state transitions necessitate further refinements of the equivalence classes to account for set connectivity. T h e 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.4  1.  11  INTRODUCTION  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 3J that satisfy a conjunction of analytic function n  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 = 0.  fit)  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 applications which can be encoded in the theory of the reals [5],[20]. 1.5  Contributions  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, pointing to a class of decision algorithms potentially useful for constructing these models(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  Thesis  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 frameworks 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 manipulator 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  T h e following overview of robotic manipulator kinematics clarifies the aims of this research.  T h i s presentation first introduces the structure of a manipulator and then  discusses translational kinematics . For simplicity, the descriptions are terse; see [26] [8] 1  [23] for more detail. T h i s chapter concludes by recasting kinematics i n 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. T h e distal point of the chain is the end-effector. T h e end-effector may be a gripper, welding torch, or other device depending upon the intended application of the manipulator. T h e 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.  R o t a t i o n a l 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  translational motions are used most frequently. the joint.  16  T h e type of motion is determined by  P r i s m a t i c joints permit translational m o t i o n whilst revolute joints permit  rotational m o t i o n . T h e 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 w i t h spherical have three D O F while cylindrical m o t i o n has two D O F and translational or rotational m o t i o n have one.  Typically, a joint sensor is attached to each joint to  provide a readout of the displacement between the links. T h e joint parameters  are used  to represent these displacements. Figure 2.1 shows these structural features using the canonical manipulator, a two-link revolute manipulator. T h e 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, j , x  j. 2  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 m a t i n g link. 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 link.  A constant link length maintains a fixed spatial distance between  adjacent frames. M a n i p u l a t o r s are classified as free-axis  mechanisms [30] because joint  parameters are measured relative to a moving frame. T h e proximal link is an exception; its reference frame is inertial. Free-axes play a significant role in the modeling of the manipulator system because they introduce non-separable multivariate dependencies. T h i s significance is further elaborated on i n Section 3.4, w i t h the review of other qualitative  CHAPTER 2.  MANIPULATOR  BACKGROUND  Figure 2.1: A n abstraction of a two-link revolute manipulator.  CHAPTER  2.  MANIPULATOR  kinematic representations.  18  BACKGROUND  T h e t w o - l i n k manipulator has constant link length, and no  twist or offset. T h e measurement of  is made w i t h respect to a fixed frame while j  2  has  a dynamic reference frame. These reference frames, pictured i n Figure 2.1, accord with the D e n a v i t - H a r t e n b e r g conventions. T h e displacement of link two is measured relative to the normal of link one. T h i s 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 m o t i o n properties of a manipulator irrespective of force . 2  These properties include position, velocity and a l l higher order derivatives of position. K i n e m a t i c equations can be divided into forward and inverse kinematics. T h i s dichotomy determines which parameters comprise the p-space of the functions. T h e two principal p-spaces  are Configuration Space and Workspace. Configuration  is the cross-product of the joint parameters. parameters ji,  space (C-Space)[28] [2]  For an n - D O F manipulator w i t h joint  C-space is an n-space manifold defined as:  C-Space  = J! x ... x j  n  C 3?".  T h e m o t i o n 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-link manipulator pictured in Figure 2.2 are n o r m a l to the plane, thus the end-effector has planar extent and the shape The existence of servo-mechanisms capable of articulating the joints and maintaining desired configurations frees a kinematic controller from concerns about the forces causing motion. 2  CHAPTER  2. MANIPULATOR  BACKGROUND  19  of its W-space is a circular manifold i n 9£ . T h e C-space of the two-link manipulator is 2  toroidal. K i n e m a t i c s involves mapping m o t i o n properties between C-space and W-space. T h e 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. T h e 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 CC U  2  s.t. C i , C  2  G C-space A C + C x  2  A X(d)  =  X(C ). 2  Figure 2.2 illustrates this non-uniqueness using the two-link manipulator. Consequentially, this non-uniqueness prevents the representation of velocity a n d acceleration as o  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: T h e 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  T h i s section acquaints the reader w i t h the form of equations used i n describing the position and velocity of the end-effector. A brief overview of path generation and control is also included. T h e position of the end-effector is a static geometric property and is mathematically represented as a vector f i e l d . Static means that the range of the position functions are 3  time invariant. For an n - D O F manipulator the position vector field has the form,  X(ju---Jn)  = Xi(ji,...J )e n  1  + ... + ^ m ( j i , . . . , i n ) e  m  (2-1)  There 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. 3  CHAPTER  the  2. MANIPULATOR  21  BACKGROUND  are the basis vectors of E u c l i d e a n space.  T h i s vector field maps a point i n C-  space to the corresponding locus of the end-effector i n W-space.  E a c h Xi is a scalar  field evaluating to the coordinate of the end-effector measured i n the direction of ej. For simpler mechanisms, this function is calculated geometrically. F o r complex mechanisms, this function is generated as successive products of homogeneous transformation matrices parameterized i n accordance w i t h the Denavit-Hartenberg conventions [26]. T h e position of the end-effector for the two-link manipulator is a function of j ^ a n d j . 2  T h e locus of this end-effector is determined functionally as X(j ,j ) 1  = (Icos(ji) + Xcos(ji + j ))ei  2  2  +  ( Z s i n ( j i ) + Z s h n j i + j ))e . 2  2  (2.2)  Because the distance the distal link displaces the end-effector is dependent on the value of ji, neither X\ nor X  2  can be represented as a composition of univariate functions of  the jx a n d j . 2  A path is a continuous trajectory of positions i n workspace. P a t h - p l a n n i n g involves establishing a sequence of configurations that moves the end-effector through a desired trajectory i n W-space.  M a t h e m a t i c a l l y , path-planning can be thought of as, given a  continuous trajectory X(t)=X (t)e 1  1  + ...  +  X {t)e m m  find the functions ji(t),  X^t)  =  S.t.  ... , jn(t)  X (j (t),...,j (t)) 1  1  n  CHAPTER  2. MANIPULATOR  BACKGROUND  =  X (t) m  22  X (ji(t),...,j (t)). m  n  Inverse—kinematic equations typically are not closed form; i n general, an easily evaluated function mapping the position of the end-effector to a configuration does not exist. A s a result, p a r t i a l derivatives of inverse kinematic equations are used to servo the robot joints to follow prescribed endpoint velocity commands. T h e first p a r t i a l derivatives | ^ give the rate of change of Xi measured i n the direction of positive jk- S i m p l y stated, these p a r t i a l derivatives describe the direction and magnitude an end-effector w i l l displace when a joint is articulated. T h e jk(t) are determined using a m a t r i x called the Jacobian.  T h e Jacoabian's rows  are the gradients V X , - . T h e gradient is a vector field that unifies the p a r t i a l derivatives of a scalar field. For the scalar field Xi(ji,...  -* i • VXi{j ..., )  •\  r  u  =  Jn  ,j )  the gradient vector is  n  dXi  7 7 - ^ 1 +  OJl  dXiI . . . +-x- en. OJn  , . (2.3)  T h e gradient vectors for the t w o - l i n k manipulator are VXi(ji,j )  =  ( - X s i n ( j i ) - L s i n ( j i + j ))ei  VX (ji,j )  =  (Lcos(j )  2  2  2  2  1  + Lcos(j +j ))e 1  2  T h e Jacobian has the following form:  - M i  dji  dX - dji  m  9jn  dXm djn  1  +  + Xsin(ji + j' )e 2  Lcos(j +j )e 1  2  2  2  CHAPTER  2.  MANIPULATOR  23  BACKGROUND  T h e elements of the Jacobian change as the manipulator moves. Thus the jk{t)  are  computed iteratively, by m u l t i p l y i n g the inverse of the Jacobian by incremental values of the coordinates. T h e J a c o b i a n of the t w o - l i n k manipulator is, (-L sin(ji) - L s i n ( j i + j )) (L cos(ji) + L cos(;'i + j )) 2  2  L sm(j + j ) L cos(ji + j ) x  (2.4)  2  2  T h e above section constitutes a quantitative characterization of forward kinematics. K i n e m a t i c 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. T h e majority of examples i n 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 i n its W-space to a destination.  Supplementing this control task w i t h a qualitative  reasoner necessitates the ability to compose several multivariate properties into a unified description. T h e 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. T h i s section provides the physical interpretations of dependence w i t h visual examples of thresholds, level sets, and property composition.  CHAPTER  2. MANIPULATOR  24  BACKGROUND  In the previous section the potential motion of the end-effector was mathematically represented as the gradient.  T h e qualitative property joint-dependence characterizes  this potential m o t i o n b y 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 i n a n 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 o n a configuration, and must be classified at the differential level. T h e jointdependence between jk a n d X{ at the configuration ji,... , c , . . . j  n  w i t h the constant c i n  the position jk is defined as: if Xi(j ...,c u  + Aj, ...J ) n  ( < < =  Xi(ji,...,j ) Xi(ji,...,j )  then then  Decreasing(X (j ,... ,j ),j ) Static(X (ji,... ,j ),j )  { >  Xi(j ...,j )  then  Increasing(X (ji,...,j )J )  n  n  lt  n  Where the qualitative values Increasing(Xi(ji,...  1  1  x  n  n  1  ,j ),jk)  k  k  n  k  denotes that X{ is i n -  n  creasing i n its dependency on jk at the configuration (ji,... ,j ). T h e qualitative values n  Decreasing a n d Static follow accordingly. Joint-dependence is equivalently defined w i t h inequality relations a n d partial derivatives. '<0 . . . d - T - U l . - " J n ) \ -0 OJk >0 ., dXi  then then then  D ecr easing (Xi(j i,... ,j ),jk) Static^X^ji,. . . ,j ),jk) Increasing(X (j ,... ,j ),jk) n  n  1  l  n  T h e value 0 is a threshold and divides the range of the partial derivatives into intervals of similar behavior.  T h e physical meaning of this threshold is demonstrated w i t h the  two-link manipulator. Thresholds of a constrained t w o - l i n k manipulator are easily visualized. Consider the ring portrayed i n Figure 2.2; this ring is the trajectory i n W-space rendered by rotating  CHAPTER  2. MANIPULATOR  25  BACKGROUND  the end-effector while holding ji constant. Mathematically stated Locus = (Xi(c j ),X (c,j )) i 2  2  2  |  X (c,j )  =  (Icos(e) + XcosO' + c)),  X (c,j )  =  (Lsin(c) + Lsin(c + j ) ) )  x  2  2  2  2  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 second 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 manipulator it has only one D O F . A complete qualitative model must aggregate the jointdependence property for each coordinate, and each joint parameter.  CHAPTER 2. MANIPULATOR  BACKGROUND  27  A n i n t r o d u c t i o n to the application of qualitative properties to robotics was provided i n this chapter. T h e next chapter returns to more general representational issues with a formal definition of property, state and state transition.  Joint-dependence will be  restated as a specific instance of the qualitative partial derivative.  Chapter 3 A Framework For Qualitative Representations T h e previous chapter used the potential motion of a manipulator to illustrate how qualitative properties related to characteristic functions, thresholds and partitions of W-space. T h i s chapter generalizes these relations and proposes a theoretical framework for describing physical systems w i t h qualitative properties. We begin by defining a property as consisting of a function and a partition on the image of this function. T h i s definition is substantiated by showing that it accommodates a l l previously cited properties; additionally, the extensibility of this formalism is illustrated through the introduction of a new property type, the qualitative partial derivative. B u i l d i n g 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.1  3.  A FRAMEWORK  P r o p e r t y  FOR QUALITATIVE  REPRESENTATIONS  29  restated  Qualitative properties are a m e d i u m 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 t h a n one function. T h e characteristic functions of simple and complex properties can be either general or systemspecific. 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. T h e 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. T h e value of the characteristic function and the partition reflect the property and its qualitative values. Therefore, an example of a property is an n - a r y scalar function /  on p-space (p-space C 3£ ) : n  p-space  - i - SJ  (3-1)  and its associated p a r t i t i o n B on SJ. B y the definition of partitions [31], the blocks of B,  denoted Bi are m u t u a l l y disjoint and their union covers SJ. Formally stated,  BiHBj  =  0  \jBi t=i  =  SJ.  V i ^ j  (3.2) (3.3)  CHAPTER  3.  A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  30  E a c h block Bi is a subinterval of 3t- whose boundary values are the property thresholds T.  Thus E q u a t i o n 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 pspace, and a p a r t i t i o n on 3 t . T h i s type of property is referred to as complex. Formally, m  a complex property is a vector-valued function /  =  (/i,..., f) m  and a partition B on  •ft™ wherein 7  p-space  - A 3ft  p-space where the blocks,  (3.4)  m  [jBi  (3.5)  are a cross-product of one block Bij from the range of each  Symbolically, Bi  =  Bij x  ... x  B  mk  z  where  =  U  \B\  — z  iJ  B  and each Bij is a (closed, open, or half-open) subinterval of the range 5^, of j  y  This  formalism does not require that the Bij are distinct. Loosely speaking, the partitions "break up" a range into blocks which exhibit similar behavior. E a c h block corresponds to one qualitative value of the property. These qualitative values are described w i t h 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 w i t h one relation. For example, a simple property defined w i t h the sign-invariant partition {(—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)  Rel (x)  : f(x)  G [0]  Rel (x)  : f{x)  G (0,oo)  2  3  where x G p-space and denotes { ( - c o , 0 ) , [0], (0, oo)} B ,B , X  2  andf?  3  respectively.  For example the complex property defined by the characteristic function /  = (/i, / ) , 2  whose associated partition 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 / ( x ) G ( - c o , 0 )  Rel (x)  :  /i( x) G (-oo,0) A / ( x ) G [0]  Rel (x)  :  /i( x) G (-oo,0) A / ( x ) G (0,oo)  ReU(x)  :  fi »  Rel (x)  •• fi »  Rel (x)  •• fi [x) G[0] A / ( x ) G (oo,0)  Relj(x)  •• fi  Rels(x)  :  2  3  5  6  2  2  2  G [0] A / ( x ) G (-co,0) 2  G [0] A f (x) G [0] 2  2  Rel$(x) •  (0,oo) A / ( x ) G (-oo,0) 2  fi [x) G(0,oo) A / ( x ) G [0] 2  fi '< ) x  e  (0,oo) A / ( x ) G (oo,0) 2  CHAPTER 3. A FRAMEWORK FOR QUALITATIVE  REPRESENTATIONS  32  (3.6)  T h e difference between a quantitative and a qualitative description is that a quantitative description maps an element of the domain of a function to a numeric value while a qualitative description maps element of the domain to a set of qualitative values. T h e diagram i n Figure 3.1 illustrates this contrast.  QV  = qualitative value  *  QV,»  Figure 3.1: A property is composed of a function and a partition.  T h e concept of characteristic functions and partitions subsumes a wide variety of properties as demonstrated by the following examples.  CHAPTER  REPRESENTATIONS  33  The proposed structure of properties is very flexible. For example slope-sign,  joint-  3.2  3. A FRAMEWORK  E x a m p l e  FOR QUALITATIVE  properties  dependence, a n d fluid-flow fit the specifications of simple properties, a n d are readily cast i n the proposed property framework; the associated characteristic functions and partitions are shown i n Figure 3.2. T h e fact that slope-sign fits this paradigm serves to illustrate that univariate properties accord w i t h the property prototype.  PRorrm  QUAUTATTVE  CHARACTERISTIC rniiA-nnv  F-WAI-T  VAI nr<  slope-sign  INCREASING DECREASING STATIC  jointdependence  MI MD S  fluid-flow  LAMINAR  x =9t  P  ,  V  ,  D  "  1  TWttr.tum nt  f(x)  jl l_ijn 3 91  T^SmONAL  1  =  9  1  dxj/djk  P'VD/n  2000.3000  F i g u r e 3.2: Properties, partitions, a n d characteristic functions The maxima,  image of a function f(x)  is commonly classified using the qualitative values  minima or ordinary point. T h i s property, which we will refer to i n this thesis as  The relations associated with slope-sign are equivalent to the relations { M , M _ , M o } defined by Kuipers[21] and, {/ OCQ_ x,f OCQ x,f OCQ X} proposed by Forbus [16]. 1  +  0  +  CHAPTER  3. A FRAMEWORK  point-type, is  FOR QUALITATIVE  REPRESENTATIONS  34  an example of a general complex property. The characteristic functions of  this property are thefirstand second derivatives f'(x) and f"{x). Points are classified (with the exception of endpoints) byfirstevaluating f'(x).  A non-zero value implies  that x is an ordinary point. Classifying the remaining points requires evaluating the second derivative. If the value of f"(x) is positive, then x is a local minimum, a negative value indicates a maximum whilst a zero value is undefined. These qualitative values correspond to a partition of 9ft into the followingfiveblocks: 2  Ordinary  -.B^  B  2  = ((-oo,0),3t)  f (x) ^ 0  = ((0,oo),»)  Minima  :B  3  =  ([0],(0,co))  Maxima  :B  A  =  ([0], (-oo, 0))  =  ([0],[0])  Undefined :B  5  f'(x) = 0, f"(x) > 0  f'(x) = 0 f"(x) < 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.2.1  3. A FRAMEWORK  FOR QUALITATIVE  36  REPRESENTATIONS  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 ) is simultaneously n  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 qualitative 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-increasingj .(MY),  monotonically-decreasingf .(MI)),  x  respectively.  x  The function / is monotonically-increasing  and  staticf (S) tXi  in its dependence on Xj at a  fixed set of parameter values, ( x . . . , x ), if a differential increase to x,- causes the value 1 ?  n  of / to increase. Monotonically-decreasing and static are similarly defined. The corresponding characteristic function for the partial derivative of / with respect  CHAPTER  to  Xi  3.  A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  37  is df,  ,  T h e associated p a r t i t i o n of 3? is the three intervals {(—oo, 0)[0](0, oo)}. T h e qualitative values i n conjunction w i t h the associated relations for x € p-space are enumerated below.  Monotonically-decreasingj .(x)  :  x  Static f, ( ) x  Xi  Monotonically-increasingf .(x) x  df  < 0  (3-7)  '•  = 0  (3-8)  df : ^—  > 0.  (3-9)  Monotonic-dependence is a general property and is applicable to many physical systems.  T h e property joint-displacement, defined i n Section 2.4, is a special case of  monotonic-dependence.  A p p l y i n g monotonic-dependence to the position of the e n d -  effector results i n the properties monotonic-dependence  and joint-dependence  having the  identical physical interpretation.  Example: The Two—link Manipulator M o n o t o n i c dependence can be used to describe the possible ways a coordinate of the end-effector changes value. T h i s motion is governed by the dependence between the scalar field Xi  (Definition 2.1) and its joint parameters. A s defined in E q u a t i o n 2.2, the  Xi coordinate of the end-effector is determined by the function  Xi(juj ) 2  = -Lcos(ji)  +  Lcos(j +j ) 1  2  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 X  2  on j . The 2  monotonic-dependence property applied to j\ uses the partial derivative given in Equation 2.4 and reads Vja,J6 € C-space  Monotonically-decreasing ^(j ,jb) Xl  a  Staticxijiijajb) Monotonically-increasingx^^daJk) The dependence of Xi on j  2  '• {—Lsin(j ) — Lsin(j +jb))  < 0(3.10)  • {-Lsin(j )  =0(3.11)  a  a  - Lsin(j +j ))  a  a  b  : ( — Lsin(j ) — Lsin(j +jb)) a  a  > 0.(3.12)  is defined likewise. These relations are equivalent to joint-  dependence that is, if monotonically-increasing  Xl  ^ 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 characteristic 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 : Thresholds:  MI, S, M D 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 w i t h 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 , . T h i s quantization is the foundation of a qualitative model, the subject of the remainder of this chapter.  3.3  T h e  Qualitative  State  A qualitative model aggregates the properties of a system into a unified state-space description. T h i s description portrays the behavior of the system as a sequence of states and state transitions.  T h e purpose of transforming a set of properties into a state-  space m o d e l 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.  T h e requirements of qualitative states are explained i n this  section; the following section refines this definition to incorporate the state transitions. A qualitative  model ( Q M ) is a state-space graph  QM  where S is a set of vertices transition from S ments of each Ds  a  t  (S,T,D,L)  (3.13)  T is a set of edges Tj,  where T ,4 indicates a possible a  to Sb\ and D is a set of Ds such that each Ds t  {  C p-space and the ele-  are invariant w i t h regard to qualitative values of the properties. Using  Relj k to represent the k t  =  th  qualitative value of the j  th  property, invariance is formalized  CHAPTER  3. A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  41  as Vpi,p  2  6 D,  ReljM  s  =>  Rel {p ). jk  2  £ is a set of labels L 5 . containing the Relj, associated w i t h the qualitative values that k  are valid on Dsi- T h e definition of a function ensures that any element x of p-space is associated w i t h one and only one qualitative value per property. M o r e formally,  V z V j 3!  Rel (x). jtk  R is a set of relations, Rels^ which are invariant on each D 5 . . We assert that the set D is a partition on p-space. T h i s follows from the observation that a property a n d its qualitative value additionally induce a complementary partition on p-space, hereafter called a pullback partition. W e w i l l begin by demonstrating that a property induces a pullback partition and then show that an aggregation of these properties additionally induces a pullback partition.  3.3.1  The Pullback Partition  A property leads to an equivalence relation on p-space. T h i s claim is substantiated by showing that pulling the blocks Bi into p-space decomposes this space into a partition of the type depicted i n Figure 3.5 . T h e equivalence relation associated with this property states  Vpi,P2 G p-space  (f( ) Pl  e Bj  A f(p ) € Bj) 2  P  l  = p  2  (3.14)  CHAPTER  3. A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  p-space  image  42  (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 B  C 3?  x  under / is the set of all elements for  which / evaluates to a member of the set B\. Formally stated, f~\B )  =  1  {x : /(*)  €  B .)  (3.15)  x  From the definition of function, we can assert two identities regarding the inverse. Given two subsets of B , B x  2  C 3ft , n  i-\B  x  r*(Bx  U B) 2  =  n -Ra) =  / ^ ( B i ) U f- (B )  (3.16)  r\B )  (3.17)  1  2  x  n r\B ) 2  CHAPTER  3. A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  43  Figure 3.6: The pullback partition. Identity 3.16 leads to the corollary B  x  n B  2  = 0 => r  1  ^ ) n f~\B ) 2  = 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)  =  f~ (B  U...U5i)  1  1  (3.18)  CHAPTER  3. A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  44  (3.19) =  {x € p-space \Rel{(x)}  Statement 3.20 shows that elements of the sets f~ (Bi) l  qualitative equivalence.  (3.20)  accord w i t h the definition of  B y the definition of function, the sets /  _ 1  ( B , ) are mutually  disjoint. If the sets were not mutually exclusive then 3 x s.t. f(x)  = a, A f(x)  which contradicts the definition of function.  —b A  a^ b  Hence, qualitative equivalence induces a  partition on p-space. A qualitative equivalence relation founded on a single property is not sufficiently comprehensive to meet the requirements for a qualitative model. A qualitative model must aggregate several properties into one unified description. T h e necessity for aggregation is clearly justified i n reference to the qualitative gradient and Jacobian.  Recall, from  Section 2.1, that a scalar field is simultaneously dependent on the values of a l l its parameters. These dependencies are contained i n the gradient as a set of first order partial derivatives. Recasting the gradient i n a qualitative framework involves representing the monotonic dependence classifications for every independent parameter. T h e necessity of aggregation is made even more emphatic i n reference to the derivative of a vector field. T h e p a r t i a l derivative is represented by a Jacobian matrix. T h e qualitative Jacobian requires mxn  monotonic dependence relations i f m is the order of the vector field, a n d n is  the number of independent parameters. In the next section we w i l l show that the notion of qualitative equivalence extends to composite characteristic functions and conjunctions  CHAPTER 3. A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  45  of partitions o n p-space.  3.3.2  Property Compositions  A n aggregation of properties induces a pullback partition o n p-space. Let $ symbolize the compound function composed of the characteristic equations / , . For a system described w i t h m properties,  T h e 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 R . m  However, from the definition of cross-product, we know that if P, denotes a partition on Ri then P  x  x P  2  =  {(B B ),...,(B ,B )} lu  21  ln  assuming the cardinahties of B\ and B  2  ( m - n blocks)  2m  are m a n d n respectively. Thus, R{ can be  rewritten as Ri =  \jBij. j  Therefore, equation 3.3.2 is restated as p-space  [jBu j  x . . . x \jB j  mj  (3.21)  letting Bi  =  \jB 3  xj  x...x\jB 3  m j  (3.22)  CHAPTER  3.  A FRAMEWORK  FOR QUALITATIVE  REPRESENTATIONS  —• \JB{  p-space  46  (3.23)  These equalities, i n addition to the definition of inverse, lead to the following partition of  p-space  p-space  =  ^-\R ) m  =  $- (\jBi)  (Identity 3.23)  l  t  = U* (£.) _1  t  We argue that these blocks are exactly the Z>5  t  \JD ,  =  S  \j9-\Bi)  i  (3.24)  »  To show that the elements of the Z)s, are invariant w i t h 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  T h i s is accomplished by decomposing the Ds  {  for a specific  index i:  D, s  = (A,...,/m)- ^,-) 1  =  (/l)  =  {x£  • • • / m )  _  1  5  ( - B i l  ?  • • •  5  Bim)  p-space \ x € f^{Bn)  A . . . A a: 6 f-\B )} im  (3.25)  E q u a t i o n 3.32 substantiates the c l a i m that the pullback partitions assoiciated with $ are property invariant; each / ~ ( 5 , ) 1  J  property.  corresponds to one qualitative value of the  jh l  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 i n the next section.  3.4  State Transition  T h e time behavior of a system described using qualitative properties is given as a sequence of Rs  r  These relations portray how the qualitative behavior of a system changes as a  continuous sequence of points i n p-space. These changes are encapsulated i n the qualitative model as a path through its vertices, where T,j are the possible changes between the Ri. T h i s section demonstrates that i n order to accurately portray state transitions, the elements of Ds< must be connected. A simple example using the sign invariant partition clarifies this necessity. T h e graph of / is depicted i n Figure 3.7 T h e elements of the pullback partitions are  f~ (Bi)  =  {x \ x < a A a < x < b}  f- (B )  =  { i | i = a A x = b}  f-\Bz)  =  {x | x > b}  1  1  2  O f these sets / ( 7 3 ) a n d / ( / 3 ) are connected and f~ (B ) - 1  - 1  1  1  3  2  is disconnected.  This  presents difficulty i n describing the time behavior. T h e possible state transitions vary depending upon the components of / ( i ? 2 ) . - 1  f~ (B ) l  2  and /  _ 1  A direct transition is possible between  ( B ) only for the case x = a. 3  Thus i n 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~ (B) but the connected components of these sets. In the above example we x  distinguish the states where x = a, and x = b  X  Bz o <—B  •H—R 1  B 1  2  —B  > 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 pspace.  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 modeling 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 alence Space.  Equiv-  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.  T h i s notion is then extended to the aggregation of properties resulting in  Qualitative Equivalence Space ( Q E S ) . Qualitative gradients and Jacobians are used to illustrate Q E S , followed w i t h an actual model using the kinematics of the two-link manipulator. T h i s chapter concludes w i t h a discussion of current algorithms that are suited to the computational needs of the qualitative model.  4.1  Property Reformulation  T h i s section rephrases properties first as functional inequalities and second connected geometric regions in  4.1.1  p-space.  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 $ ( i ? ) . T h i s section utilizes the - 1  t  Bi are subintervals of Image(f) to rephrase qualitative equivalence  restriction that the  as inequality invariance. Recall that p , p x  can  2  G p-space are qualitatively equivalent if the same qualitative value  be used to describe the behavior of a physical system under these conditions, stated  specifically  f{pi,p ) € B . 2  {  CHAPTER 4. QUALITATIVE EQUIVALENCE SPACE  51  Restricting the Bi to intervals permits the associated equivalence classes to be reformulated 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  =  B  = [T \.  t  (Ti,T ) i+l  t  T h i s 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 partition and the simple characteristic function f(x) given i n E q u a t i o n 3.6 is rewritten as:  Rek(x) : f{x) < 0 Rel (x) : f(x) = 0 2  Rel (x) : f{x) > 0 3  where x € p-space. T h e relations associated w i t h the qualitative values of complex properties can also be constructed from conjunctions of inequalities. For example the the relations i n Equation 3.7 associated w i t h the complex property whose function and partitions are / and {(—oo, 0), [0], (0, o o ) } , are rewritten as: 2  =  (fi,f ), 2  CHAPTER  4.  QUALITATIVE  EQUIVALENCE  SPACE  52  0 A / (x) < 0  Reli(x)  :  fi(x) <  Rel (x)  :  fi(x) < 0 A f ( x)  Rel3(x)  :  / i ( x< ) 0 A f [x) > 0  Rel (x)  : /iW=  Rel (x)  :  fi(x)  =  0 A f [x)  Rel (x)  :  fi(x)  =  0 A  Rel (x)  :  Mx) > 0 A f x) < 0  2  4  5  6  7  Relg(x) : Relc,(x) •  2  2  =  0  2  0 A  f [x) < 0 2  2  =  0  f x) > 0 2  2  fx(x) > 0 A f x) 2  0  Mx) > 0 A f x) > 0. 2  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-\B ) x  =  {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:  /.•  <  T  iJ  /.  <  Tij  fi  =  Tij  CHAPTER 4. Q UALITATTVE EQ UIVALENCE SPACE  fi  >  fi > Where < , >  53  >,i  T  T. u  i m p l y that a block contains its delimiting thresholds.  In Section 3.5 we established the need to distinguish connected components of the equivalence classes. T h e restriction that characteristic functions must be continuous can be used to demonstrate that these components have an isomorphic geometrical description. T h e geometry of connected components is the topic of the next section.  4.1.2  Geometric restatement  T h i s section demonstrates that these connected pullback partitions are regions i n p-space generated from p l o t t i n g 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. T h e ideas of this section are strongly dependent upon the continuity of the characteristic functions.  Preliminary Definitions T h i s section begins w i t h 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 i n F i g u r e 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  Figure 4.1: Graph of / ( x i , i 2 )  54  CHAPTER  4. QUALITATIVE  The function f(xi,x ) 2  EQUIVALENCE  55  SPACE  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 x , x x  2  plane. Figure 4.2 portrays the cross-sections corresponding to the level sets:  f(x ,x )  = Ti  f(x x )  =  T  f(xi,x )  =  T  1  u  2  2  3  (4.2)  2  3  Figure 4.3, illustrates the projections associated with  Ti,T . 2  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 , T ], (T , T 3 ) , ( T 3 , 0 0 ) } 2  2  then this partition contains the same elements enclosed within cross sections shown in Figure 4.4; both are subsets of Image(f) defined as:  B  x  =  {x\x<  T}  B  2  =  {x I Tx < x < T }  x  2  B  3  =  {x I T < x < T }  B  4  =  {x\x>  2  3  T} 3  (4.3)  CHAPTER  4.  QUALITATTVE  EQUTVALENCE  SPACE  Figure 4.2: Cross-sections associated w i t h X i , T , X 3 2  CHAPTER  4. QUALITATTVE  EQUTVALENCE  SPACE  Figure 4.3: The projections associated with the cross-section Xi and  CHAPTER 4.  QUALITATIVE  EQUIVALENCE SPACE  F i g u r e 4.4: Continuous surfaces can be equated to the partition B .  CHAPTER  4.  QUALITATTVE  EQ UTVALENCE  SPACE  5 9  Projecting these cross-sections vertically onto the x , x - p l a n e partitions p-space into x  2  connected regions, called the contour m a p . A region R is topologically connected if V xj,x  2  G R there exists a continuous path P ( x ) such that every x,- £ R. In simpler t  terms this means a curve can be drawn connecting the two points which does not cross a level set. We now informally argue that i f a contour m a p 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 / ( f ? ) . - 1  To illustrate, consider the block B defined i n E q u a t i o n 4.3; the associated pullback 2  partition is f-\B ) 2  W e w i l l show that f~ (B )  = { ( x , x ) I T >f{x x )<T 1  2  x  u  2  2  }.  is the subset oi p-space delimited by the connected components  1  2  of the level sets / ( x i , x ) 2  = T\ and / ( x i , x )  = T . T h e level sets 2  2  /(Xi,x ) 2  =  T  i =  i?  1,4  are shown i n F i g u r e 4.5; this is called the contour map. T h e level set corresponding to T  2  has two connected components. If our conjecture is valid, the subset of p-space contained between the level sets / ( x ) = T\ a n d / ( x ) = T is a subset of f~ (B\); 1  2  these delimiters satisfy the inequalities  T  t  < f{xi) < T  2  If this condition is inconsistent then  3 x,- £ p-space s.t. x,- $  /^(Bi)  a l l x - between t  CHAPTER 4.  QUALITATIVE EQUIVALENCE  SPACE  Figure 4.5: The contour map for / ( x i , x ) and 2  Ti,T ,T . 2  3  CHAPTER  4. QUALITATPVE  EQ UPVALENCE  SPACE  61  or i n other words, 3 Xi 6 p-space s.t. f(xi) < Ti A /(x,-) < T . 2  T h e following argument shows that no x - between the level sets / ( x ) = 2\ and / ( x ) = T t  2  satisfies either of these inequalities. Consider the threshold T and let S\,S ,S3 2  2  be the three equivalence classes defined  as  51 =  {x \ f(x) < T }  5 5  2  2  =  {x\ f(x) = T )  3  =  { x | f(x) > T }  2  2  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 S by the curve / ( x ) = T \ any path connecting a member of Si to S3 2  2  must traverse through a point x £ S3. T h i s assertion derives from the intermediate value theorem which guarantees that if a function / is continuous over a surface that contains the points (f(xi) < f(x )) 2  (/(xi)  /(xj),  a n d / ( x ) where 2  then there exists at least one value x , for c satisfying the inequalities  < c < f(x )) 2  such that f(xi) = c. Informally, this theorem ensures that a  function cannot "leap" values. W e know that VXJ G Si Ax E S k  f{ j) X  < T < f(x ) 2  k  3  62  CHAPTER 4. Q UALITATTVE EQUTVALENCE SPACE  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  S. 2  In general we can assert that if p-space is decomposed using level sets w i t h 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 / . A p p l y i n g this assertion to  and the contour graph portrayed i n Figure 4.5, we  conclude that a l l points w i t h i n the shaded regions are less then T , but greater then T i . 2  Note that the far right region also satisfies this set of inequalities. B y default, all shaded areas are are less then B . 2  Thus these two sets represent the connected components of  T h e next section generalizes these ideas to properties.  T h e geometry of properties. Properties and their associated partitions are easily couched i n the framework of level sets and contour maps.  T h i s translation is straightforward a n d simply requires using  thresholds for the constants of the levelsets. In E q u a t i o n 4.1 the equivalence classes /  _ 1  ( B ) were redefined as the subsets of p1  space satisfying a conjunction of inequalities. T h e connected components of inequalities were geometrically demonstrated to be connected regions of the type depicted i n Figure 4.5. T h u s , if the T,- are used for the constants of the level sets, the connected components of the equivalence classes / ~ ( B ) are the subsets of p-space contained i n the regions a  obtained by decomposing p-space w i t h the fi(x)  = T{j. T h e t e r m critical curve is used  CHAPTER  4.  Q UALITATTVE  EQ UTVALENCE  to denote these special level sets.  63  SPACE  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 j  th  property value of the i  property, the  th  equivalence classes associated with the $ ( i ? ) are -1  f  {x 6 p-space \ Relij(x)  A ... A  Rel k(x)} nt  where k denotes the index of one qualitative value associated with the n  th  property. By  CHAPTER 4. Q UALITATTVE EQ UTVALENCE SPACE  64  Definition 4.1 this formula can be written as a conjunction of functional inequalities. T h e geometry o f these equivalence classes can be viewed as a n intersection of contour graphs. T h e next section demonstrates that the qualitative representation is isomorphic to a decomposition of p-space w i t h critical curves.  4.2.2  Geometric Restatement: QES  Earlier we showed that the pullback partitions  are the regions delimited by the  critical curves fi = T , j . T h i s section shows that the intersection of these critical curves corresponds to the connected pullback partitions  (where 3> =  (/i,...  ,f )). m  T h i s correspondence is substantiated by showing that every critical point of / , 6 (fii • • • i fm) is  critical point of $ and every critical point of $ is a critical point for  a  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 critical point associated with /,• if fi(x) is a boundary point of one or more Bij,  3i,j f (x) EBij t  A (\im (fi(x) + e) $ Bij V l i m ( / ( i ) + ^ Q  (  t  ) ;  ))  (4.4)  T h e elements w i t h i n a domain of a state are qualitatively equivalent. T h i s requires that only one qualitative value from each property can be valid on Z) . T h i s is formulated as 4X  x ED  Si  -* Relij{x) V . . . V Rel (x), ini  where rii denotes the total number of qualitative values assoicated w i t h the i h property. l  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 D i are subsets of p-space where a s  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 <J> (i?) is determineed by whether -1  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 decomposition 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 partial 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  66  SPACE  eral ideas are introduced first followed by an actual example using the manipulator kinematics. In Section 2.3, the gradient of a scalar field / , ( x i , . . . , x ) was defined as n  1  dx  n  T h e qualitative analog of the gradient uses the qualitative partial derivative, monotonicdependence. For a scalar field on n variables, the qualitative gradient requires aggregating n monotonic-dependence properties, one for each independent parameter. T h e characteristic function of the qualitative partial derivative has the form,  and the partitions  are all sign-invariant. T h e composite model is thus  and the associated p a r t i t i o n 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. mapping from a subset of p-space to { M I , M D , S }  n  Thus each Dsi is a  , where n represents the number of  independent parameters. T h e qualitative Jacobian for a vector field a similar form. T h e Jacobian is the collection 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: T h e qualitative gradients of a bivariate scalar field.  CHAPTER  4. Q UALITATTVE  EQ UTVALENCE  68  SPACE  where each row i is the gradient associated w i t h fi r  3xi dfm  dfm  -  3x„  8x\  thus  $ = (—(x ,...,x )..., 1  For a vector field /  df dx n  (xi,...,  *»))  = (/i, / ) of two variables the label set of each D i is 2  s  L 1  n  e{MI,MD,S} . 4  ai  W i t h i n each DJ the signs of all the partial derivativs are sign-invariant T h e next section demonstrates the qualitative gradient, Jacobian, and associated Q E S  model for the robotic manipulator.  4.3.1  Example: The Robotic Manipulator  T h e kinematic relations of the two-link robotic manipulator can be described i n qualitative form by a decomposition of C-space w i t h the critical curves 2  T h e multivariate coordinate functions Xi(ji,...  j ) are transformations from C-space n  to workspace. T h e first partial derivative |^»- (k = 1,..., m) give the rates of change of Xi measured i n the direction of positive jk.  dX i dn  =  -L  sin(ji) - L sin(ji +  (4.5)  j) 2  It 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} . 1  4  2  Recall from Section 2.1, that C-space is the cross product of the joint parameters  CHAPTER  4.  QUALITATIVE  EQUIVALENCE  dX  =  69  SPACE  Ls\n(ji+j )  (4.6)  2  dX  - r r ^ = LcosO'O + XcosO'! + j )  (4.7)  2  ^  (4.8)  = LcosCji+ia)  T h e associated decompositions of p-space are depicted in Figure 4.7 E a c h decomposition is generated from plotting the critical curves  OJk  In these diagrams the shaded regions correspond to MI, solid lines S, and the white regions MD. T h e aggregation of the partial derivatives given i n Equations 4.5, 4.6, 4.7 and 4.8 are the gradients V X ^ j i , ^ )  and VX (ji,j ) 2  2  respectively. T h e associated decompositions  of C-space corresponding to the qualitative description of these is depicted i n Figure 4.8. E a c h pattern represents a different sign combination. T h e J a c o b i a n aggregates the elements of the gradients, VX (ji, x  j ) a n d V A " i ( j i , j ) the 2  2  resultant qualitative equivalence space is shown i n 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 i n a concise framework has several advantages. W e have demonstrated that this framework eased the extension of qualitative 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: T h e 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 o f t h e t w o - l i n k m a n i p u l a t o r .  CHAPTER  4.  QUALITATTVE  of geometric problems.  EQ UTVALENCE  73  SPACE  In particular, for those systems whose characteristic functions  have p o l y n o m i a l form, the existence of a desirable qualitative state can be reformulated as a decision p r o b l e m i n the theory of the reals[5]. T h e next section describes this family of problems.  4.4  Computation andQ E S  T h e previous section redefined state domains as connected subsets of some 3£ that satisfy n  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 i n the theory of the reals and the D { as semi-algebraic sets. 3  G i v e n a formula as a boolean combination of polynomial inequalities, a semi-algebraic set i n R is a set of variable values for which a formula is true. [5] [20] A formula is defined n  as a logical construction of atomic formula where an atomic formula has the form  fi  xo  where  < € {<,<,=,>,>} and each /,• is a p o l y n o m i a l in n real variables. If the $ is composed of polynomials of this type then, i n principle, algorithms based on algebraic cell decomposition can used to generate the connected qualitatively equivalent D i, and the existence of a transition s  Tij can be proved by computing cell adjacency [34] Several algorithms have been developed, particularly i n 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 K o z a n provide a cell decomposition which has the adjacency information necessary to construct the connected components of $ . We w i l l use the notation of Yaps formalism to show the relation between constructing algebraic-varieties and the Ds  r  G i v e n a set E of polynomials w i t h rational coefficients i n d variables a sign assignment maps a : E —• —1,0,+1. E a c h sign assignment sigma represents an equivalence class  X  =  a  {xe$ \ d  sign({p{x)) = a{p(x)),  p G E}  called the sign classes of a. T h e consistent sign classes are the non-empty sets. Yap's algorithm finds the connected sign classes of a given set of polynomials and provides full adjacency of these classes. O u r domain is easily translated into this framework given $ = / i , . . . , /  n  then  £ = {9i I 9i = fi ~ T  id  V i , j = 1 . . . n,}  where n,- denotes the the total number of thresholds associated w i t h fi. T h e connected pullback partitions can be generated by utilizing adjacency information to union the resulting sign classes. Unfortunately these algorithms are double-exponential i n the number of variables just i n the case of polynomial functions. C e l l decompositions for analytic functions are  CHAPTER  4.  QUALITATIVE EQUIVALENCE SPACE  75  even more challenging. However, if thresholds are time-invariant, the time complexity of these algorithms is not a hindrance.  Chapter 5 Comparisons and Usage  T h e 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 critical curves of properties. This chapter uses the geometry of state domains to demonstrate that current qualitative frameworks are limited to either properties whose critical curves are parallel with the axes of p-space, or properties whose critical curves are reduced to a restricted class of bivariate functions. A l s o , the utility of qualitative partial derivatives and the advantages of a mathematically precise representational  framework  are demonstrated w i t h a hypothetical control scenario involving the robotic manipulator.  5.1  Q E S A n d Existing Representations  Currently, the types of reasoning performed by existing qualitative representations divides into two branches:  dynamics and kinematics. D y n a m i c systems model how the  behavior of a system changes over prolonged periods of time. In the manipulator do-  76  CHAPTER  5.  COMPARISONS  AND  77  USAGE  m a i n , dynamics would model the path an end-effector follows i n response to a series of joint actuations. K i n e m a t i c s 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. A l t h o u g h qualitative representations used by existing dynamic and kinematic systems are general enough to make the qualitative distinctions needed for their specific applications. T h e y are unable to meet the representational demands of general multivariate properties. T h i s section explains the source of these representational shortcoming.  5.1.1  Qualitative Dynamics and multivariate properties  T h e fundamental l i m i t a t i o n of current representations used to model dynamics is that they solely support properties whose critical curves are parallel to the basis vector. For critical curves associated w i t h the characteristic function f(x\,...  ,x ) these are n  (5.1)  c where x,- 6  {x  1 ?  . . . , Zn}-  If critical curves of this type are plotted i n p-space, the shape of the D i are restricted s  to hypercubes. F i g u r e 5.1 shows how this l i m i t a t i o n constrains Q E S i n the case of a two dimensional p-space. T h i s geometric l i m i t a t i o n is too restrictive to model the shape of the general critical curve for multivariate properties. T h e value of the characteristic function for a multivariate property / ( x i , . . . , x ) is dependent on each x . T h i s dependence is mathematically n  t  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 multivariate. To date, the representational framework described in Equation 5.1 has been a sufficient basis for qualitatively modeling dynamic because the characteristic equations of existing 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 ) is viewed as a univariate funcn  tion of time under the constraints X i ( i ) , . . . ,x (t). Substituting these constraints into / n  CHAPTER 5.  COMPARISONS AND USAGE  79  leads to a new univariate of time  To fully appreciate the corresponding reduction i n 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),...,j (t)) n  corresponding to a constrained set of joint values, ji(t). This set is alternatively viewed as a continuous path i n C-space, this alternative view is illustrated in Figure 5.2. Analytically the time derivative of Xi relative to a joint k is given by the chain rule as  dXj dj . dj dt  .  k  [  )  k  where ^j*- denotes the rate of change of joint k w i t h respect to time. T h i s model reduces the partial derivatives associated w i t h monotonic-dependence from functions of j , to a function of t. T h e  are known as a function of time, hence  using substitution again, the partial derivatives can be determined as functions of time,  ^i  { m  ...  OJk  j n {  t))^^l(t). OJk  T h e 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 partials (See Figure 5.3). Evaluations of  C-space.  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 i n F i g u r e 2.3 is fixed while that of link two varies as a function of the joint parameter of the first link. 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.  T h e first half of this section w i l l demonstrate that existing qualitative kinematic formalisms complement the qualitative framework proposed i n this thesis. T h e second half of this section explains why existing kinematic frameworks cannot encompass  the  representational needs of free-axis mechanisms. Qualitative kinematic systems describe the possible displacements of the components of a kinematic chain relative to other components i n the kinematic chain. T h e qualitative 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]. T h i s observation is summarized as "Force i n a fixed-axis mechanism is transmitted through contact and the net force is determined by summing the i n d i v i d u a l forces of each contacting pair". Joskowicz has extended Realeaux's proposition to kinematics, proving that the m o t i o n of any component i n a kinematic chain can be separated into the pairwise motions between contacting components. If two components i and A; i n a kinematic chain are i n contact, Joskowicz asserts djk  (jijk)-  T h e dependence of component i on j is a function of the joint parameters of the contacting  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 w i t h 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. T h e 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. T h i s 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 applicability functions classifys the connectivity of two parts as contact, no-contact and overlap. Faltings algorithm is an algebraic decomposition of the type discussed i n Section 4.4.  T h e decompositions induced by Faltings algorithm can be  further refined to distinguish if the dependence between two components is MI, MD, or S. D e t e r m i n i n g this dependence is the topic of [25]. T h e m o t i o n of a free-axes components, such as the such as the end-effector  can-  not be described using the pairwise component models. T h e dependence between the components i n a fixed-axes kinematic chain cannot be described i n a pairwise parameter space. T h e 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 link can change despite the fact  CHAPTER  5.  COMPARISONS  AND  84  USAGE  that the value of the joint parameter of the link d i d not vary. M o d e l i n g the kinematics of free-axes mechanisms, requires functions on the full c-space.  5.2  Reasoning and Control  T h i s section presents a simplified control scenario which demonstrates the potential use of the qualitative Jacobian and illustrates the merits of a formal definition of qualitative 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) i n W-space. In simpler terms, answering the question, " H o w can we articulate the joints to cause the end-effector to move towards a point p i n 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.  T h i s 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  sign(AXi)  =  OXsign(-^)sign(Aji).  In theory, the monotonic-dependence relations i n conjunction w i t h the desired sign of the differential translations could be used to select appropriate Aji. *A 0 value of a differential translation is possible if the dependency relation is static  In a control  CHAPTER 5. COMPARISONS AND USAGE  85  scenario, the A j , are the control choices, the A X , are the objectives, and the monotonicdependence relations are the constraints. T h e relations MD, MI, S provide the information needed to determine the resulting direction of translation of X , given the sign of Ajk- For example, i f the dependence relation between a coordinate Xi and a joint j is MDik, we know a positive value of Aj zero valued Vj  k  k  implies A A", w i l l be negative. Positive and  k  result i n positive and zero differentials, respectively. Similar reasoning  applies to the dependency relation MI. In this case the same Aj  k  will result i n a A X ,  that is opposite i n 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 critical curves the monotonic-dependence changes value, i m p l y i n g that the same sign of Aj  k  w i l l no longer render the same sign of AXi.  T h e total displacement of the end-effector is a composition of the differential displacements incurred b y actuating each joint. T h i s net composition is called the total differential. T h e differential displacements are locally linear and thus for a n - D O F manipulator whose workspace is a subset of 9 t , the time derivative coordinates are, m  dX dj dj dt x  dt  dX,m dt  x  + ...+  x  dX dj  m  n  d  H  dt  +... +  dX  m  dj  dj  n  n  dt  dX  dj  m  n  djn dt '  and the t o t a l differential is  AX  dX i X  dji  Adj + ...+ x  dX, dj  m Adj,  n  n  CHAPTER 5. COMPARISONS AND USAGE  AX  m  =  ^Adj  1  +  86  ...+  ^Adj . n  T h e 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 coordinate 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 equations. Reasoning systems for choosing consistent solutions of this type can be found in [22] and [10]. T h e u t i l i t y of qualitative partial derivatives is better demonstrated i n 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 obstacles must be avoided. B o t h elbow orientation and obstacle zones can be integrated as additional properties i n Q E S . In the case of the elbow, the relevant qualitative values are elbow-up, elbow-down, a n d straight-arm. Obstacle contact additionally fits the mathem a t i c a l framework of properties, algorithms by [29] a n d [13] partition C-space according to obstacle a n d free zones. A n additional qualitative property that could be beneficial to computation is classify degenerate a n d nondegenerate configurations. Degeneracies occur when a manipulator loses a degree of freedom.  These degeneracies can be determined  by examining the eigenvalues. T h e 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  satisfy thes objective.  87  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 characteristics into a unified representation.  Chapter 6 Conclusion and Future Work For a newcomer the existing qualitative modeling frameworks can be a bit perplexing. T w o 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 Faltings [14], Joskowicz [19] and Forbus [16] were not applicable to the manipulator either. T h e sources of these inapplicabilities was not readily apparent. However, identifying this source was p i v o t a l to the extensions of qualitative representations.  T h e lessons gleaned  from investigating this inability are contained i n this thesis. Despite the differences of existing formulations, closer examination reveals several mathematical commonalities. T h i s thesis has attempted to provide for the theoretical underpinnings of these commonalities i n hopes to ease the application of qualitative reasoning to new domains such as manipulator control. T o close this thesis, results are summarized, and open representational issues are outlined.  89  CHAPTER  6.1  6.  CONCLUSION  AND FUTURE  WORK  90  Summary  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 D i and L i denoting the state domain and label. Each L i is a set of relations associated s  a  a  with qualitative values. For a system defined with n properties,  D i —* Reh x . . . x Rel . a  n  This thesis demonstrated that: 1. The D i are connected equivalence classes in 3£ satisfying a conjunction of inequaln  a  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. L i is the set of relations Relij valid on the D i. A relation is a member of L i if a  s  s  Vx € Dai  x e f-\Bij)  -*  ReUj e L . 3i  3. The maximal set of possible state transitions T i is isomorphic to the adjacencies s  of the D i. Symbolically s  TT~crJ7i -> sj e T i <> j. si  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 descriptions. 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  Future Work  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 / (J3) are contained between the critical curves. This theorem relies -1  i  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. Composing 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. C u r v e s 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. T i m e - v a r y i n g 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", M I T Press, Cambridge 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 Supplementum 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 Mechanics," M I T A l Lab TR-419, January 1978. [12] J . Denavit, R.S. Hartenberg: "A Kinematic Notation for Lower-Pair Mechanisms 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", M I T 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 Kinematics," 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", Proceedings 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", Proceedings of 13th Conference on Industrial Robots, 1983. [24] D.McCloy and M.Harris: "Robotics A n Introduction", Open University Press, New York, 1986. [25] Paul Nielson: "A Qualitative Approach to Rigid Body Mechanics," Ph.D. thesis, 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. R A 3, N O . 3, June 1987. [30] Franz Reuleaux: "The Kinematics of Machinery", Dover Publications, Inc., New York, 1876. [31] Steven Roman "Discrete Mathematics" Saunders College Publishing Philidelphia, P A 19105 1896. [32] Elisha Sacks: "Qualitative Mathematical Reasoning", Proceedings of IJCAI85, 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] A l 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, McGrawHill book company, 1964.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051955/manifest

Comment

Related Items