s
.
w
c
v
u
n

‘09., new;

u...-

7 xi... ‘

... u. i

‘ . yiily

‘ , . . . . . .2... r. .55.: ”26:51.:

3:? f...“ i..I..., )..}f,....-. (1. «3‘ F E 5. . l ,
.3 ..._ pinata :h. k»: J..,3...£\E%a.—.&Lui)4 agtmfl . 1: . E... , _ ‘ .1. 1...‘ . I 4 a: m”... fa
:.V 517.... 5 ‘ . . . .‘ t; .

‘ ‘7 .
1:2.

 

“flu

1i);

«duh-"u.

 

3 * LIB TE {:JiIIVERSITY
. v: IGAN STA
,: 3’ ‘ Ersg‘limsmc. MICH 48324404"

This is to certify that the
dissertation entitled

Design and VLSI implementation of Perceptive Controller for
Robotic Systems

presented by
Yu Sun

has been accepted towards fulfillment
of the requirements for the

Ph. D. degree in Electrical and Computer
EmeerirLcLDepartment

 

 

Major Professor’s Signature

9/12/0 CL

Date

MSU is an Affirmative Action/Equal Opportunity Institution

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/ClRC/Date0ue.p65-p.15

 

DESIGN AND VLSI IMPLEMENTATION OF PERCEPTIVE
CONTROLLER FOR ROBOTIC SYSTEMS

By
Yu Sun

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Electrical and Computer Engineering

2004

ABSTRACT

Design and VLSI implementation of Perceptive Controller for Robotic Systems
By
Yu Sun

Intuitively, human intelligence largely depends on the perception from interaction
with the environment and the object. Similarly, robotic systems can sense the dy-
namic changes of the environment and the object states during the task execution.
This dissertation is aimed at developing approaches for modeling, analyzing and de-
signing robotic control systems based on the robotic perception, i.e., a perceptive
frame.

In the perceptive frame, the model of a task can be learned by the robot based
on the perception. In this dissertation, a model identification method for unknown
parameters of a nonholonomic cart has been developed. Using interactions between
a mobile manipulator and the cart, sensory information is accrued to estimate the
model parameters of the cart. Since the raw data is contaminated by noise that cannot
be modeled statistically, a wavelet based Least Square Method(LSM) is proposed to
estimate these parameters for the cart. Experimental results verify that the estimation
accuracy can be significantly improved by the use of the proposed lease square method.

For the control issues in the perceptive frame, an perceptive hybrid system ap-
proach for the motion planning and control of mobile robot systems is proposed. The
ability to deal with unexpected events is one of the essential aspects of robot intel-
ligence. Robotic systems can respond to environmental information obtained from
sensors by making task decisions. According to the task decisions, the system is
able to modify the original planned path and control the robot to execute the task
autonomously. Perceptive model with single perceptive reference can deal with un-

expected events only at the continuous level. It allows the perceptive reference to

be blocked and resumed by a class of unexpected events, including obstacles. The
perceptive hybrid system model has three layers, one continuous layer, two discrete
layers. Corresponding to the three layers, one continuous perceptive reference and
two discrete perceptive references. The discrete layers enable the robot system to
make decisions and modify original path plans. The properties of the system model,
including linearity, continuity, stability in switching, and some dynamical properties
of unexpected events have been discussed in the hybrid linguistic framework. The
evolution of the hybrid perceptive references cannot be stopped by blocking the con-
tinuous perceptive reference. The properties have been verified by experiments.

For system implementation, a VLSI implementation oriented controller design for
robotic system is proposed. For the robotic control systems in perceptive frame, the
hybrid formal model is used for both the controller design and hardware description.
The model can describe the high level behavior of the robotic system by a structural
style architecture. The high level structure of the controller model guarantees the syn-
thesizability of the control system. Therefore, the controller model can be mapped
to VLSI implementation directly. A Cadence/Testbuilder system is used to simulate
the hybrid controller design with a dynamics model. The HDL / C hybrid simulation
results have verified that the hybrid system framework can be used for VLSI imple-
mentation, and the integrated system is synthesizable. It gives an efficient approach

for hardware implementation of controllers for robotic systems.

to my family

iv

ACKNOWLEDGEMENTS

Foremost, I would like to acknowledge all the invaluable help from my advisor, Dr.
Ning Xi, without whom this would not have been possible. This dissertation comes
from numerous discussions in his office, from his keen insight knowledge, from his
guidance to a fruitful research area, and his perseverance and support. Not only the
knowledge I learnt here, but also the research experience and friendship I gained here
will be beneficial to the rest of my life.

I would like to thank all my committee members, Dr. Fathi Salam, Dr. Robert
Schlueter and Dr. Baisheng Yan. In addition to their invaluable time they spend on
the committee meeting, their insightful comments and suggestions will enhance the
technical soundness of this dissertation.

I am grateful to my friends and colleagues from Robotics and Automation Lab.
The discussions with Dr. Jindong Tan, Dr. Weihua Sheng, Dr. Jizhong Xiao, Amit
Goradia, Dr. Imad Elhajj, Dr. Heping Chen, and Guangyong Li substantially con-
tributed to my work and broaden my knowledge.

I dedicate this work to my family for their continuous emotional support: to my
father and mother, for believing in me, to my sister-in—law, for everything she’s done
and finally to my brother, who set the standard for me, shared all my success and
failures and stood by me through everything. Without their love and support, I would

not have reached this point.

TABLE OF CONTENTS

LIST OF TABLES ...............................
LIST OF FIGURES ..............................

INTRODUCTION

1. 1 Motivation .................................
1.2 Literature Review .............................
1.3 Outline of the dissertation ........................

PRELIMINARIES AND NOTATIONS

2.1 Wavelet Ttansform ............................
2.1.1 Fourier TYansform .........................
2.1.2 Wavelet Tiansform and Short-Time Fourier Transform . . . .
2.1.3 Discrete Wavelet Transform ...................

2.2 Automata Theory .............................

2.3 Metric Space and Ordered Set ......................
2.3.1 Metric Space ...........................
2.3.2 Ordered Set ............................

TASK MODEL IN PERCEPTIVE FRAME

3.1 Introduction ................................

3.2 Interactive On-Line Model Learning ...................
3.2.1 Problem Formulation ......................
3.2.2 State Estimation .........................
3.2.3 Wavelet Based Model Identification(WBMI) ..........

3.3 Convergence of Estimation ........................

LINGUISTIC APPROACH FOR ROBOTIC SYSTEM CONTROL IN PER-
CEPTIVE FRAME
4.1 Introduction ................................
4.2 Hybrid Perceptive Reference Model for Control of Robotic System . .
4.2.1 Languages and Automata ....................
4.2.2 Hierarchical Task Execution Architecture ............
4.2.3 Reference Generation .......................
4.3 Perceptive Control for Mobile Manipulation and Tele-Operation . . .
4.3.1 Hybrid Languages .........................
4. 3. 2 Task Execution ..........................
4.4 Description for Language-Based Hybrid Perceptive Reference
4.4.1 Hybrid Perceptive Reference Space of Robotic Manipulation
System ...............................
4.4.2 Hybrid Metric Space .......................
4.4.3 Independent Evolution ......................
4.5 Hybrid State Space Model for Robotic Manipulations .........

vi

37
37
39
4O
44
47
50
50
51
52

52
53
54
55

5 ANALYSIS OF CONTROL SYSTEM IN PERCEPTIVE FRAME 56

5.1 Introduction ................................ 56
5.2 Evolving of Perceptive Reference .................... 56
5.3 Stability of Perceptive Control System ................. 60
5.3.1 Input-State Stability of Hybrid Perceptive Control ....... 62
5.3.2 Continuity of input-output mapping ............... 64
5.3.3 Stability conditions for switched systems ............ 64

5.4 Modeling of Unexpected Event ...................... 65
5.4.1 Unexpected Events(UE) in Robotic Manipulations ....... 66
5.4.2 Unexpected Event Processing in Perceptive Frame ....... 66
5.4.3 Unexpected Event Processing: An Example .......... 67

6 EXPERIMENTAL RESULTS 70
6.1 Experimental System Setup ....................... 70
6.1.1 Hardware Structure ........................ 70
6.1.2 Software Structure ........................ 70
6.1.3 Robot Controller and Task Modeling .............. 73

6.2 Experimental Results for Online Model Learning ............ 73

6.3 Experimental Results for Hybrid Linguistic Control in Perceptive Frame 81

7 PERCEPTIVE CONTROL SYSTEM DESIGN AND VLSI IMPLEMENTA-

TION 89

7.1 Real-time System in Perceptive Frame ................. 89

7.1.1 Input-ReferenceOutput Mapping in the Perceptive Ptame . . 89
7.1.2 Perceptive Reference Based Language Description Regarding

Real-Time Control System Design ................ 90

7.1.3 Finite Automata Approach for Input-Reference—Output Mapping 90

7.2 VLSI Implementation-Oriented Controller Design ........... 91

7.2.1 Abstractions of real-time perceptive controller ......... 91

7.2.2 Synthesizability of Perceptive Controller ............ 95

7.3 Hardware-Software Co—design and Hybrid Simulation ......... 98

7.3.1 Hardware-Software Co—design in Perceptive Frame ....... 98

7.3.2 Hybrid Simulation ........................ 102

7.3.3 Simulation results ......................... 105

8 CONCLUSIONS AND FUTURE WORK 115

8.1 Conclusions ................................ 115

8.2 Suggestions for Future Research ..................... 117

BIBLIOGRAPHY ............................... 119

vii

LIST OF TABLES

6.1 The Results of Mass Estimation ...................... 76
6.2 Comparison of the Length Estimation Results .............. 80

viii

1.1

2.1
2.2

3.1
3.2

3.3
3.4

4.1
4.2
4.3
4.4
4.5

5.1

6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
6.10
6.11
6.12
6.13
6.14
6.15
6.16
6.17
6.18
6.19
6.20
6.21
6.22
6.23

7.1
7.2

LIST OF FIGURES

Hierarchical Scheduling, Planning and Control Scheme ........ 6
The multilevel Discrete Wavelet Transform. .............. 15
An Example of Finite Automata. .................... 17
The mobile manipulator and a nonholonomic cart ............ 20
The associated coordinate frames of the mobile manipulator and a

nonholonomic cart. ............................ 21
Laser range data ............................. 28
The block diagram of WBMI algorithm. ................ 30
Perceptive Control ............................ 38
An Perceptive reference-based Framework for Robotic Systems. . . . 40
The Upper Automaton of the Action Level Reference automaton. . . 48
An Embedded Automaton of the Action Level Reference automaton. 48
An Example of the Task Level Reference Automaton. ......... 49
Unexpected Event Processing in the Task Level Reference. ...... 68
The Experimental System ........................ 71
The Software Structure of the Experimental System .......... 72
The mass estimation, for m=45 Kg .................... 74
The mass estimation, for m=55 Kg .................... 75
The mass estimation, for m=30 Kg .................... 75
The length estimate and variance P at 9th levels for L=1.31m. ...... 76
The length estimate and variance P at 10th levels for L=1.31m ....... 77
The length estimate and variance P at 11th levels for L=1.31m ....... 77
The length estimate and variance P at 12th levels for L=1.31m ....... 78
The length estimate and variance P at 9th levels for L=0.93m. ...... 78
The length estimate and variance P at 10th levels for L=0.93m ....... 79
The length estimate and variance P at 11th levels for L=0.93m ....... 79
The length estimate and variance P at 12th levels for L=0.93m ....... 80
The results of é and lé-QI for L=0.93m. ................. 81
The results of (2' and [:11] for L=1.31m. ................. 82
The results of é and IéLf-l for L=1.46m. ................. 83
The moving trajectory in the experiment ................. 84
The moving reference in the experiment. ................ 85
The actions triggered by the action level reference ............ 86
The phantom joystick tele—operation. .................. 86
Unexpected Events in Phantom Manipulation along x-axis ...... 87
Unexpected Events in Phantom Manipulation along y-axis ...... 87
Unexpected Events in Phantom Manipulation along z—axis ...... 88
Abstract of the structure. ........................ 91
Structure of the Implementation .................... 93

7.3
7.4
7.5
7.6
7.7
7.8
7.9
7.10
7.11

7.12
7.13
7.14
7.15
7.16
7.17
7.18
7.19
7.20

7.21

Block Diagram of the Implementation Procedure. ........... 94

Partitionings for Hardware/ Software Codesign. ............ 99
Parse Trees for Implementation Oriented Language. ......... 100
The Scheme of the Hybrid Simulation System ................ 103
Arithmetic Operations ............................ 104
Schematic Description of Action Planner. ................. 106
Schematic Description of Action Reference. ................ 107
Simulation results. ............................. 108
The Motion Trajectory in the Experiment: (a) x-y plot (b)continuous ref-

erence w.r.t time ............................... 109
Joint Level Control — Step Response: (a) position (b) velocity ....... 110
Joint Level Control — Step Response: (c) position ((1) velocity ....... 110
Joint Level Control — Step Response: (e) position (f) velocity ....... 111
Joint Level Force Control Signal at Step Response: (g) Joint 1 (h) Joint 2 111
Joint Level Force Control Signal at Step Response: Joint 3 . ....... 112
Joint Level Control Step Response: (a) position (b) velocity ........ 112
Joint Level Control Step Response: (0) position ((1) velocity ........ 113
Joint Level Force Control Step Response: (e) position (f) velocity ..... 113
Joint Level Control at Step Response: (g) Position of Joint 2 (h) Velocity

of Joint 2 .................................. 114
Joint Level Control Signal at Step Response (i) : Joint 2 .......... 114

CHAPTER 1
INTRODUCTION

1 .1 Motivation

The intelligence of robotic systems has been a longstanding focus of attention for
control engineers. The robotic technology has increasingly wide application areas in
a variety of environment, ranging from assembly tasks in manufacturing automation,
underwater manipulations and home care services to space research. The environment
in which the tasks are performed is varies widely. Furthermore, the environment and
the task could be unstructured and dynamically changing. It requires the robotic
systems to have human-like intelligence, i.e., process and respond to the sensed infor-
mation relating to the task and environment.

Perceptive frame control is motivated by the demand for increased levels of intel-
ligence of mobile robotic systems to deal with more complex tasks in an environment
with increasing uncertainty. While the limited prior knowledge cannot provide the
arguments rich enough to describe and execute the tasks. An obvious solution is to
utilize perception on the control tasks and environment.

Perception can be expressed by events, both continuous and discrete, and com-
posed by sensors. The human operator or planner, in this respect, thinks and plans
in terms of discrete events. The traditional time-based control system design causes
the inconvenience in improving the intelligence of the systems. As a low level trig-
ger in the system, the time reference is an independent variable, it is not related to
perception from sensors. Therefore, there are two naturally different types of refer-
ences existing in the systems simultaneously, this fact may increases complexity in
intelligence design and execution.

A unified perceptive reference frame is required for describing and utilizing the task

or environmental perception. The objective of creating such a perceptive reference

is to build a triggering mechanism, expressing all the perceptive events, however,
different from the time-based reference. Compared to the traditional time-based
systems, the systems in perceptive frame can be driven by a perceptive reference, and
described as the functions of perceptive reference, instead of the functions of time.

In task model learning, one of the challenges is the changing unstructured en-
vironment. The intelligent robotic systems have to face more complex tasks in a
dynamical environment. The methods used for planning tasks for a static environ-
ment or assuming omniscient knowledge of the environment cannot be applied to
dynamic environment. The specifications of real—time control systems require the
control strategy to be able to “on-line” capture and process perceptive information.

The nature of the perceptive reference indicates that the interactions with the
physical plant, through sensors and actuators, is analog, i.e. continuous. It also
exhibits performance of the abstracted discrete references working at higher level to
give the system more intelligence and flexibility. Discrete abstractions make it easier
to manage the complexity of the system. Discrete models are easier to compute
with, as all computers and algorithms are essentially discrete. In particular, It is
worth noting that discrete abstractions make it easy to introduce the linguistic and
qualitative information in the controller design.

The perceptive frame should be built to provide the information the control system
need for characterizing the environment-control system interaction. It requires one to
find a method to process hybrid references and task/ action commands. The control
methods in perceptive frame incorporate both continuous and discrete dynamics.
Design and analysis of such a hybrid system is particularly challenging.

A survey of the ongoing research results in the context of the control methods in

perceptive frame is given in the following section.

1 .2 Literature Review

Task model learning, hybrid system modeling, and control and system design are the
topics of this dissertation. Previous work related to these topics in the literature is
reviewed.

Model Learning

In control system design, modeling the control objects is the foundation of high
performance controllers. In most cases, the model is unknown before the task is
performed. To learn the model, therefore, is essential. Generally, real-time systems
use the sensors to measure the environment and the objects. The model learning task
is particularly difficult when real-time control systems run in a noisy and changing
environment, The measurements from the sensors may be contaminated by the non-
stationary noise, i.e. it is changing randomly and depends on the environmental
factors. The factors may include wind, vibration, friction and so on.

The most frequently used parameter identification methods are the Least Square
Method (LMS) and the Kalman filter method Both have recursive algorithms for
on-line estimation.

The Kalman filter [23] is used for parameter estimation. Generally, if a linear
model or a linearized model of a dynamical system can be obtained, the system noise
and observation noise are also known. The Kalman filter can estimate the states of the
dynamic system through the observations regarding the system outputs. However,
the estimation results of the Kalman filter are significantly affected by the system
model and the noise models. Least Square Method can be applied to identify the
static parameters in absence of accurate linear dynamic models.

There is rich literature on parameter estimation for robot manipulators. Zhuang
and Roth [68] proposed a parameter identification method of robot manipulators. In
this work, the Least Square Method is used to estimate the kinematic parameters

based on a linear solution for the unknown kinematic parameters. To identify the

parameters in the dynamic model of the robot manipulator [35], a least square esti-
mator is applied to identify the parameters of the linearized model. It is easy to see
that LSM has been widely applied in model identification as well as in the field of
robotics.

To achieve the objective of real-time online estimation, the Recursive Least Square
Method(RLSM) has been developed to save computation resources and increase op-
eration velocities for real time processing [30]. For identification, measurement noise
is the most important problem. There are two basic approaches to processing a
noisy signal. First, the noise can be described by its statistical properties, i.e. in
time domain; second, a signal with noise can be analyzed by its frequency-domain
properties.

Many algorithms of LSM are used to deal with noisy signals to improve estima-
tion accuracy, but they require the knowledge of the additive noise signal. Durbin
algorithm and Levinson-Wiener algorithm [22] require the noise to be a stationary
signal with known auto—correlation coefficients. Each LMS based identification al-
gorithm corresponds to a specific model of noise [31]. Iserman and Baur developed
a Two Step Process Least Square Identification with correlation analysis [46]. But,
for on-line estimation, especially in an unstructured environment, relation analysis
results and statistical knowledge cannot be obtained. In this case, estimation results
obtained by the traditional Least Square Method are very large( Table 2 in section
4). The properties of LSM in the frequency domain have also been studied. A spec-
tral analysis algorithm based on least-square fitting was developed for fundamental
frequency estimation in [14]. This algorithm operates by minimizing the square error
of fitting a normal sinusoid to a harmonic signal segment. The result can be used
only for fitting a signal by a monofrequent sinusoid.

Perceptive Frame Control

A continuous perceptive planning and control approach [60] has been applied to

the path planning and control for a single manipulator by Xi, Tarn and Bejczy. The
basic idea of the perceptive planning and control theory is to introduce the concept
of a motion reference 3, a parameter that is directly relevant to the measured sen-
sory outputs and the task. Instead of time, the control input is parameterized by
the motion reference. Since the action reference is a function of the real time mea—
surement, the values of the desired vehicle states are functions of the measured data.
This creates a mechanism to adjust or modify the plan based on the measurements.
Thus, the planning becomes a closed loop real-time process. The planner generates
the desired values of the system, according to the on—line computed action reference
parameter s. The perceptive approach guarantees the stability of the robot system
in presence of unexpected events.

More results about the perceptive coordination of multiple manipulators were
presented in [61]. Song, Tarn, and Xi [49] [50] [56] [64] [65] developed an perceptive
scheme for the integration of task scheduling, action planning and control in robotic
manufacturing systems, as shown in Figure 1.1. An approach by using Max-Plus
Algebra model and perceptive planning and control scheme was proposed to provide
an advanced mechanism to integrate manufacturing systems, so that task scheduling,
which usually deals with continuous dynamics, can be treated in a unified analytical
model. The interactions between discrete event systems and continuous dynamics
are achieved so that the manufacturing systems are allowed to intelligently cope with
unexpected system faults and uncertainties during the tasks. However the robot
system cannot avoid the block from unexpected events, for instance, unexpected
obstacles,

Hybrid System Modeling and Analysis

Hybrid system has been extensively investigated recently and a variety of hybrid
system models and frameworks have been proposed[3] [4] [7][10] [24] [57] [59].

Rajeev Alur, Costas Courcoubetis, Thomas A. Henzinger, and Pei-Hsin Ho [2]

Task

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 ] A
] Process Scheduling ]
Logic Command -
(0‘8.th) ] Task Scheduling
E Action Scheduling j
- t x
: V :
E Path Planning 5
Numerical Command [ Action Planning
(Continuous) :
E Trajectory Planning E
........... X. i
: ' f
E fi Control System E
, ' l Real-time Automatic
Time-based Work Station Control
Execution l :
l — Sensory Information E
v v

 

 

 

Figure 1.1: Hierarchical Scheduling, Planning and Control Scheme

proposed the concept of hybrid automata, as a model and specification language
for hybrid systems. Hybrid automata can be viewed as a generalization of timed
automata, in which the behavior of variables is governed in each state by a set of
differential equations. The classification of the structures on hybrid automata based
on a extended version can be found in [25] and [26].

For stability issues, multiple Lyapunov functions were introduced for hybrid and
switched piecewise continuous systems. Branicky [5] [6] proposed the multiple Lya-
punov Function for switched and hybrid systems. Ye, Michel and Hou in [29] [40] [67]
extended Branicky’s result, and developed a general approach that can be applied to

different types of systems that exhibit some kind of hybrid behavior.

In the research on hybrid automata’s dynamical properties, the necessary and
sufficient conditions for hybrid automata to have existence and uniqueness of execu-
tion were developed based on the nonblocking and the deterministic properties[38].
The dynamical properties, which include the continuity, invariance, and issues related
to Lyapunov stability methods, were investigated in [36] [37] by John Lygeros, Karl
Henrik Johansson, Slobodan N. Simic, Jun Zhang and Shankar Sastry. As a hybrid
system approach, hybrid automata theory has a serial of analysis and design meth-
ods. However, the switching conditions of the hybrid automata are fixed constraints,
not flexible enough to describe the hybrid dynamics under the language-based input
control.

Language and Linguistic Control

The application of languages, in this dissertation, is to solve the motion control
problems in real-time systems. In the field of Artificial Intelligence (AI), the research
on languages has been an attractive issue. AI is concerned with concepts and methods
of symbolic inference by computer and symbolic knowledge representation for use in
making inferences based on the use of languages. However, the sybolic languages
only reflect actions and operations at the discrete levels of the intelligent systems
[43]. In literature, Linguistic approaches are proposed to cope with discrete variables
of hybrid systems and applied to the motion planning and control of mobile robots.
The linguistic expressions can carry the control information for performing discrete
and continuous operations on the physical systems.

The main problem in motion control is simultaneously achieving adequate speed
and expressiveness. In order to solve the motion control problem, Brockett [8] defined
the concept of an interpretive language and described a three-part solution to the
problem of general motion control. It involves a motion description language together
with an interpreter mechanism and an applications program. The language is, to a

large extent, device independent and thus capable of describing the tasks in a wide

variety of systems. A more detailed construction criterion for the formal language is
then present in [11].

Based on the idea of the interpretive language, Brockett [9] extends the concepts
of the lattice language from the analysis of the robotic system motion. In [10], motion
description language for kinetic state machines, which are the continuous analog of
finite automata, is abstracted. The motion description language can support interac-
tions between continuous and discrete aspects of a control system.

Furthermore, Manikonda at al. [39] defined atoms in the language alphabet that
describes motion behaviors. The motion description language programs are composed
by concatenating interrupt-driven “atoms”. 'Ifansitions between atoms are triggered
by changes in the environment or in the state of the robot. A library of atoms imple-
ments simple position and velocity-controlled movements as well as sensing operations
involving the sonar, Infra-Red range finder and laser range finder. The functions of
the language are improved to deal with multiple interruptions. In Egerstedt’s re-
search, by using motion description language of Brockett’s hybrid model [16], the
interaction between the continuous and the discrete parts can be given a meaningful
control theoretic interpretation using reinforcement learning. An instruction com-
plexity problem of avoiding multiple obstacles is analyzed. The results explain the
way for choosing the motion alphabet such that the necessary instructions can be
minimized when instructing a robot to navigate in cluttered environments populated
by polygonal obstacles. By considering feedback in the finite automata, the instruc-
tion complexity of “free-running” automata was formulated in [16]. Free running
finite automata can be stated as a finite state machine that reads an input and then
makes transitions repeatedly, using the same input value, until a particular output
condition is realized. The analysis shows that the length of the shortest description
can be reduced by the feedback specification.

From the above review, it can be seen that Hybrid control schemes have been dis-

cussed exhaustively in the literature. However, most investigations of hybrid systems
address the time-based descriptions, which is a special class of perception referenced
systems. In other words, both the continuous part and the discrete part of the sys-
tems use time as the reference, little of them consider the hybrid system issues in
perceptive frame. It is inconvenient, from the point of view of human intelligence. It
is desirable to develop a perceptive control framework to unify the perception factors
in hybrid system approach.

Because of the nature of the perception, the perceptive reference can be abstracted
as symbolic inputs, linguistic expressions. The perceptive control approach, proposed
in this dissertation, is inspired by the linguistic approaches discussed in [9][10][16].

We model the motion planning and control of the robotic systems by a hybrid
system model based on perceptive motion reference. The perceptive motion reference
hybrid model enables both the continuous part and the discrete part of the system
to deal with unexpected events. This discrete part of the system ”supervises” the
robot system based on environmental sensor information such that the system can
avoid unexpected obstacles by modifying original path plans. The discrete part and
the continuous part are integrated by the perceptive motion reference.

Implementation-Oriented Perceptive Controller Design

Nowadays, there has been growing interest on implementation of digital systems
with language description. For RTL level description, the typical implementation—
oriented programming languages , for example, VHDL and Verilog have had an
enormous impact on digital systems design methodology promoting a hierarchical
top—down design process similar to the design of programs using high-level program-
ming languages such as Pascal or C++ [47]. It has helped to establish new design
methodology, taking the designers away from low level details such as transistors
and logic gates to a much higher abstract level of the system description, just as

high-level programming language take them away from the details of CPU. Unlike

other programming languages, VHDL and Verilog HDL provide the mechanisms to
describe concurrent events being of crucial importance for the description of behavior
of hardware.

The abstraction of the real time control system indicates that parallel execution
is an important feature for system design. The high level programming language, for
example, C++, Pascal, and JAVA can implement the parallel execution only with
system calls [45]. The language does not evolve the parallel processing mechanism
in its semantic description. Other than these programming languages, VHDL and
Verilog take concurrency into consideration [44]. Its semantics enables the designers
to synchronize the processes in a complex system at RTL level. However, there is a
little literature about the VLSI implementation for real time control system design,
especially, there is no such a method for direct hardware design of real time controller

from the description at the behavioral level.

The real challenge in perceptive control is to develop a systematic approach for design,
analysis and implementation of hybrid robotic controller in a perceptive framework.
The first technical difficulty is perception acquiring and processing, the perception is
normally obtained from noisy sensory measurements. Signal processing and parame-
ter identification will result in precise perceptive information for the purpose of control
and planning. The second technical difficulty is perceptive control modeling and ana-
lyzing. The controller should be built on a perceptive framework, which provides the
non-time based reference, and guarantees stability and other dynamical properties
for dealing with unexpected events. The third difficulty is to create a mechanism to
map the high level controller design in the perceptive frame to hardware, i.e., VLSI

implementation without knowing the details of the circuit design.

10

1.3 Outline of the dissertation

The scope of this dissertation is to investigate new perceptive control methods for
robot systems. The material of the dissertation is arranged in eight chapters.

Chapter 2 describes the mathematical tools for the perceptive signal and the
perceptive frame model, Wavelet 'Ifansform and automata theory are introduced.
Wavelet Transform theory is applied to non-stationary signals from a noisy environ-
ment. There is no prior information about the noise, i.e. containing non-modeled
time-variant noise. The automata-formal language theory results in an efficient
method to state the evolution behaviors of the discrete variables in physical systems.

Task model learning method in the perceptive frame is discussed in Chapter 3. In
order to solve the model identification problem with unknown noise in an unknown
environment, a wavelet based online model learning algorithm is developed. Using
this algorithm, the characteristics of the unknown, non—stationary noise are ignored.

The objective of Chapter 4 is to develop a hybrid system approach for the planning
and control of robotic manipulation in the perceptive frame. In this chapter, linguistic
method is applied to system modeling. The robotic control systems are described in
hybrid language-based perceptive frame.

The system analysis of the hybrid approach is given in Chapter 5. In the perceptive
frame the evolving property, stability and complexity are considered with linguistic
and hierarchical architecture.

Chapter 6 describes the experimental system, the experimental results for verifying
both model learning and linguistic control approach are discussed.

Chapter 7 presents the discussion on the real-time system design and and VLSI im-
plementation issues including synthesizability of the perceptive controller, hardware—
software co-design and hybrid simulation for system verification.

Chapter 8 concludes this dissertation and suggests future work.

11

CHAPTER 2
PRELIMINARIES AND NOTATION S

In this chapter, we cover the preliminaries and notations related to the model learning
and the hybrid control method in the perceptive frame. The mathematical tools,

including Wavelet Transform, automata theory, are introduced.

2. 1 Wavelet Transform

The wavelet transform is a tool that cuts up data or functions or operators into
different frequency components, and then studies each component with a resolution
matched to its scale. This multiresolution concept is applied to wavelet transform.
The wavelet transform has been successfully applied to non-stationary signals for
analysis and has provided an alternative to the Windowed Fourier 'Ifansform.

The Fourier Transform, with its wide range of applications has its limitations. For
example, this transformation cannot be applied to non-stationary signals that have
time varying or spatial varying characteristics. Although the modified version of the
Fourier Transform, referred to as Short-Time Fourier Transform(STFT) can resolve
some of the problems associate with non-stationary signals, it does not address all
the problems.

In this section, Discrete Wavelet Transform(DWT) is briefly introduced as the

preliminary of the raw signal processing in on-line model identification.

2.1.1 Fourier Transform

The essence of the Fourier transform of a waveform is to decompose the waveform
into a sum of sinusoids of different frequencies. In other words, the Fourier transform
analyzes the “frequency contents” of a signal. The Fourier Transform identifies or

distinguishes the different frequency sinusoids, and their respective amplitudes, which

12

combine to form an arbitrary waveform. The Fourier Transform is a frequency domain

representation of a function.

2.1.2 Wavelet Transform and Short- Time Fourier Transform

The Short-Time Fourier Transform (STF T) replaces the Fourier transform’s sinu-
soidal wave by the product of a sinusoid and a single analysis window which is localized
in time. The STFT has a constant time frequency resolution. This resolution can be
changed by rescaling the window. It is a complete, stable, redundant representation
of the signal.

The ST FT takes two arguments: time and frequency. It has a constant time fre-

quency resolution. This resolution can be changed by rescaling the window.

Wavelet Transform is different from STFT.

The continuous wavelet transform is defined by

 

 

CWTra s) = ~11: = 1 fauwt " 7))dt (21)
ms!) 8

As seen in the above equation, the transformed signal is a function of two variables,
7 and s , the translation and scale parameters, respectively. 1/1(t) is the transforming
function, and it is called the mother wavelet . The term mother wavelet gets its name
due to two important properties of the wavelet analysis as explained below:

The term wavelet means a small wave. The smallness refers to the condition that
this (window) function is of finite length ( compactly supported). The wave refers
to the condition that this function is oscillatory. The term “mother” implies that
the functions with different region of support that are used in the transformation
process are derived from one main function, or the mother wavelet. In other words,

the mother wavelet is a prototype for generating the other window functions.

13

The term “translation” is used in the same sense as it was used in the STF T;
it is related to the location of the window, as the window is shifted through the
signal. This term, obviously, corresponds to the time information in the transform
domain. However, we do not have a frequency parameter, as we had before for the
STFT. Instead, we have scale parameter which is defined as ( f requency)‘1. The term

frequency is reserved for the STFT.

2.1.3 Discrete Wavelet Transform

Wavelet Transform (WT) is a technique for analyzing signals. It was deve10ped
as an alternative to STFT to overcome problems related to its frequency and time
resolution properties. More specifically, unlike the STFT that provides uniform time
resolution for all frequencies the Discrete Wavelet Transform(DWT) provides high
time resolution and low frequency resolution for high frequencies and high frequency
resolution and low time resolution for low frequencies.

The DWT is a special case of the WT that provides a compact representation of
a signal in time and frequency that can be computed efficiently. It can be explained
as a subband coding.

The time—domain signal is passed from various highpass and low pass filters, which
filters out either high frequency or low frequency portions of the signal. This pro-
cedure is repeated, every time some portion of the signal corresponding to some
frequencies being removed from the signal.

The Continuous Wavelet Transform (CWT) is a correlation between a wavelet
at different scales and the signal with the scale (or the frequency) being used as a
measure of similarity. The continuous wavelet transform is computed by changing
the scale of the analysis window, shifting the window in time, multiplying by the
signal, and integrating over all times. In the discrete case, filters of different cutoff

frequencies are used to analyze the signal at different scales. The signal is passed

14

x[|n] i=0 ~ 1|:
1 ' i
sin] h[n]

f=1tl2~1t % f=0~1t12

[is

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Level 1 h
DM‘ coefi‘iciaus g[n] [ll]
arm-.1112 f=°~ll4
W; i i
DWT coefficients g[n] . hill]
r=n18~w4 f=0 4’3
Level 3
DWT coeflt'cients . . .

Figure 2.1: The multilevel Discrete Wavelet Transform.

through a series of high pass filters to analyze the high frequencies, and it is passed
through a series of low pass filters to analyze the low frequencies. The subbanding
procedure is shown in Figure 2.1.

In discrete signals, the Nyquist rate corresponds to 71 rad/s in the discrete fre-
quency domain. After passing the signal through a half band lowpass filter, half of
the samples can be eliminated according to the Nyquists rule, since the signal now
has a highest frequency of 1r/ 2 radians instead of 7r radians. Simply discarding every
other sample will subsample the signal by two, and the signal will then have half the

number of points. The scale of the signal is now doubled. Note that the lowpass fil-

15

tering removes the high frequency information, but leaves the scale unchanged. Only
the subsampling process changes the scale. Resolution, on the other hand, is related
to the amount of information in the signal, and therefore, it is affected by the filtering
operations. Half band lowpass filtering removes half of the frequencies, which can be
interpreted as losing half of the information. Therefore, the resolution is halved after
the filtering operation.

Next section will discuss Automata Theory used for perceptive control.

2.2 Automata Theory

Automata theory is the key technology in hybrid system modeling and system analy-
sis. It provides a mathematical tool to describe the properties of the system in a
discrete fashion. Finite Automata and formal languages are useful models for many
important kinds of hardware and software. First we introduce some basic concepts
about finite automata and formal languages.

A symbol is the abstract entity of automata theory. Examples are letters and
digits.

An alphabet is a finite, nonempty set of symbols. Conventionally, we use the
symbol 2 for an alphabet. Common alphabets include:
1. E = 0, 1, the binary alphabet.
2. E = a, b, ..., z, the set of all lower-case letters.
3. The set of all ASCII characters.

A string (or word) is a finite sequence of symbols chosen from some alphabet.
The empty string, denoted e, is the string consisting of zero symbols.

Concatenation of strings: Let :r and y be strings. Then my denotes the concate-
nation of x and y, that is, the string formed by making a copy of :1: and following it
by a copy of y.

A set of strings all of which are chosen from some 2*, where Z is a particular

16

%
Start

Figure 2.2: An Example of Finite Automata.

alphabet, is called a language.

If 2 is an alphabet, and L g 2*, then L is a language over 2. Notice that a
language over 2 need not include strings with all the symbols of 2, so once L is a
language over 2, it is a language over any alphabet that is a superset of 2.

A finite automaton(FA) is a system (Q, E, 6, go, M) where Q is a finite set of states,
2 is , , go 6 Q is the initial state, M C Q is the accepting states.

A finite automaton , M is a “tuple”, (Q, E, A, qo, F), where:

—Q is a finite set of states

—2 is a set of input symbols, an alphabet, call the input alphabet

—A C Q x E —> Q is a set of the transition mappings Q x E into Q.

—F Q Q is a set of final states.

2* set of string of finite length of elements of 2. Define string of length 0 to be e.

M accepts a string 3 E 2*, with [s] = n, if there exists a sequence of states q E Q",
with |q| = n +1 such that:

-q[0] = (10 —For i = 0,1,...n,(q[i],s[i],q[i+1]) E A —q[n +1] 6 F.

The language accepted by M, L(M) is the set of all string 5 accepted by M.

Two automata, M1 and M2, are equivalent if L(M1)=L(M2).

An example of finite automata, automaton M is shown in Fig. 2.2. The state
set consists of A and B . A is the starting state, B is the final state. The alphabet
of the input symbols includes “0,1,and%”. The arrows in the figure denoote the

state transition. For automaton M, “0%” and “%1” are the words in the language

17

accepted by M.

2.3 Metric Space and Ordered Set

2.3.1 Metric Space

A metric space can be defined as a set S with a global distance function (the metric g)
which, for every two points x, y in S, gives the distance between them as a nonnegative
real number g(x,y). A metric space must also satisfy

1. g(z, y) = 0 if and only if :1: = y,

2- 906.11) = g(yw),

3. The triangle inequality g(a", y) + g(y, z) 2 g(x, 2).

2.3.2 Ordered Set

A totally ordered set(or “linearly ordered set”) is a set plus a relation on the set
(called a total order) that satisfies the conditions for a partial order plus an additional
condition known as the comparability condition. A relation is a total order on a set
S (“S totally orders S”) if the following properties hold.

1. Reflexivity: a S a for all a E S.

2. Antisymrnetry: a S b and b g a implies a = b.

3. ’Il'ansitivity: a S b and b S c implies a S c.

4. Comparability (trichotomy law): For any a, b E S, either a g b or b S a .

The first three are the axioms of a partial order, while addition of the trichotomy
law defines a total order. {3, S} is called ordered space or totally ordered space, if S

is an ordered set or a totally ordered set.

18

CHAPTER 3
TASK MODEL IN PERCEPTIVE FRAME

3.1 Introduction

A manipulator mounted on a mobile platform can significantly increase the workspace
of the manipulation and its application flexibility. The applications of mobile ma-
nipulation range from manufacturing automation to search and rescue operations.
A task such as a mobile manipulator pushing a passive nonholonomic cart can be
commonly seen in manufacturing or other applications as shown in Fig.3.1.

The planning and control of the mobile manipulator and nonholonomic cart system
is based on the mathematic model of the system. Some parameters of the model, in-
cluding the mass of the cart and its kinematic length, are needed in the controller[54].
The kinematic length of a cart is defined on the horizontal plane as the distance be-
tween the axis of the front fixed wheels and the handle.

A nonholonomic cart can travel along its central line and perform turning move-
ment about point C; in this case, the mobile manipulator applies a force and a torque
on the handle at point A, as shown in Fig.3.2. The line between A and C is defined
as the kinematic length of the cart, [AC I, while the cart makes an isolated turning
movement. As a parameter, the kinematic length |AC| of the cart can be identified
by the linear velocity of point A and the angular velocity of line AC.

In cart-pushing, positions of the cart can be measured directly by multiple sen-
sors. To obtain other kinematic parameters, such as linear and angular velocity of
the object, numerical differentiation of the position data is used. This causes high
frequency noises which are unknown in different environments. The unknown noise

of the signal will cause large estimation errors. Experimental results have shown that

19

 

Figure 3.1: The mobile manipulator and a nonholonomic cart.

the estimation error can be as high as 90%. Therefore, the above Least square al-
gorithms canot be used, and eliminating the effect of noise on model identification
becomes essential.

This chapter presents a method for solving the problem of parameter identification
for a nonholonomic cart modeling where the sensing signals are very noisy and the
statistic model of the noise is unknown. When analyzing the properties of the raw
signal in frequency domain, the noise signal and the true signal have quite different
frequency spectra. In order to reduce the noise, a method to separate the noise signal
and the true signal from the raw signal is used to process them in the frequency
domain. A raw signal can be decomposed into several new signals with different
bandwidths. These new signals are used to estimate the parameters; the best estimate
is obtained by minimizing the estimation residual in the least square sense.

Based on this approach, combined with digital subbanding technique [1], a Wavelet
Based Model Identification Method is proposed. The estimation convergence of the
proposed model is proven theoretically and verified by experimentation. The exper-
imental results show that the estimation accuracy is greatly improved without prior

statistical knowledge of the noise.

20

 

 

L
7

 

Figure 3.2: The associated coordinate frames of the mobile manipulator and a non-
holonomic cart.

3.2 Interactive On—Line Model Learning

In this section, the task model learning problem is described.

3.2.1 Problem Formulation

A mobile manipulator usually consists of a mobile platform and a robot arm. Fig.
3.2 shows the coordinate frames associated with both the mobile platform and the

manipulator. They include:

0 World Frame 2: XOY frame is Inertial Frame;

0 Mobile Frame 2M: X M M 1’“ frame is a frame attached on the mobile ma-

nipulator;

0 Mobile Frame EA: X CAYCframe is a frame attached on the nonholonomic

cart.

21

The nonholonomic cart shown in Fig. 3.2 is a passive object. Assuming that the
force applied to the cart can be decomposed into f1 and f2, the dynamic model of

the nonholonomic cart in frame 2 can be represented by

513C 2 —sin9c + icosdc
ch mcf

37.. = ——cos€c+ —1—sin6C (3,1)
fmc c

9'. = _2
1c

where rmyc and BC are the configuration of the cart, mC and 16 are the mass and
inertia of the cart. A is a Lagrange multiplier and BC is the cart orientation.

As shown in Fig. 3.2, The input forces applied to the cart, f1 and f2, correspond
to the desired output force of the end-effector, f3, ff. In other words, the mobile
manipulator controls the cart to achieve certain tasks by its output force. Therefore,
manipulating the cart requires motion planning and control of the mobile manipulator
based on the decoupled model [54], and the motion and force planning of the cart
based on its dynamic model (3.1). An integrated task planning that combines both
is desired.

The control input f2 can then simply be designed [54] as
[C . .
f2 = EM) — k0(6c - (15)) (3.2)

Therefore the nonholonomic cart is largely characterized by L and the mass of the
cart me. The objective of task model learning is to identify the two parameters.

The point A in Fig. 3.2 on the cart is the point on which the mobile manipulator
force and torque are applied, C is the intersection between the rotation axis of the
front wheels and the central line of the cart. VA is the velocity of point A in frame
2. 66,0", are the orientations of the cart and the mobile manipulator in frame 2,

respectively. a is the orientation of the cart in frame 2,; .

22

It is known that L and mC are two very important parameters in order to obtain
the control input. While a mobile manipulator starts to manipulate an unknown cart.
It is important to on-line identify L and mc through the initial interaction with the
cart. For simplification, the cart can be described as a segment of the central line of
the cart. The line starts from its intersection with the rotation axis of front wheels
(point C) and ended at the point(Point A) handled by the gripper. The length of the
line is L. The turning movement of the object can be isolated to study its properties.

The geometric relationship between the angles is:

do = a + 6",. (3.3)

The on-board sensors in mobile manipulator include a Laser Range Finder, En-
coders, and a Force / Torque Sensor. They can provide real-time sensory measurement
of position of the mobile base and the end-effector, orientation of the cart, force and
acceleration applied on the end-effector.

Based on the mobile manipulator sensor readings, the position of A can be de-

scribed as:

xa cosflm —sin0m pz mm
= + . (3.4)
ya sinflm cosOm py ym

The derivatives of the above equations are:

9'. = a + 6;... (3.5)

23

115,, cosdm —sin6m p}, aim . —sin6m —c036m 1),,

= + + 0m
ya sinflm cosflm p'y gm cosdm —sin9m p,
(3.6)
We define:
35a
VA _ 1 (37)
31a

then 123,, = 1b,, - sinflC — ya - c0366.
According to the characteristics of a nonholonomic cart, the turning movement of
the cart can be isolated as an independent motion. The movement can be described

as

Equation (3.8) is the fundamental equation for identifying the parameter L.

To estimate the mass of the cart, the dynamics of the cart along XC can be

described by the following equation:

a1 = i — g. (3.9)
me me

Where In is the mass of the cart, a1 is acceleration on Xe axis, f1 and F f is the input

force and the friction on XC axis, respectively. a1 and f1 can be measured by the Jr3

24

force/ torque sensor. Rewrite it in vector form

T
_1_
0.1 = fl ' mc . (3.10)
_1 5!.

Based on (3.10), the mass of the cart can be identified by measurements of a1 and
f1.

To estimate the kinematics length of a nonholonomic cart, positions, orientations,
linear velocities and angular velocities of the cart are needed. The first two can be
obtained by mobile manipulator sensor readings and previous work on orientation
finding [54]. To find the velocity signals, a numerical differentiation method is used
to obtain the derivative of position and orientation information. For a time domain

signal, Z (t), this procedure can be expressed by the following equation,

Z(t) - Z(t — t’)

2m:- ,_,,

,t—t’ = At > 0. (3.11)

 

Where At is the sampling time.

The orientation signal is very noisy due to the sensor measurement error. The
noise involved in the orientation signal is significantly amplified after numerical differ-
entiation, and it cannot be easily statistically modeled. The unmodeled noise causes

a large estimation error in parameter identification.

3. 2. 2 State Estimation

Sensor Fusion: The mobile platform is equipped with a laser range finder. Figure
3.2 shows a configuration of the cart in the moving frame of the mobile platform. The
laser sensor provides a polar range map of its environment in the form of (a, r), where

a is a angle from [—7r / 2, 7r / 2] which is discretized into 360 units. The range sensor

25

provides a ranging resolution of 50mm. Figure 3.3 (a) shows the raw data from the
laser sensor. Obviously the measurement of the cart is mixed with the environment
surround it. Only a chunk of the data is useful and the rest should be filtered out. A
sliding window, to = {011, 012} is defined. The data for 0 ¢ 112 are discarded. To obtain
the size of w, the encoder information of the mobile manipulator should be fused with
the laser data. Since the cart is hold by the end effector, the approximate position of
23,, y,, as shown in Figure 3.2, can be obtained. Based on arr, y, and the covariance of
the measurement r, which is known, the sliding window size can be estimated. The
filtered data by the sliding window is shown in Figure 3.3(b).

In this applications, the cart position and orientation (me, ya, 96) are the parameters
to be estimated [55]. Assuming the relative motion between the cart the robot is slow,
the cart position and orientation can be estimated by the standard Extended Kalman
Filter(EKF) technique[32] or least square method. The cart dynamics are described

by vector function:

x, = F(XC, f) +15 (3-12)

where f is the control input of the cart, which can be measured by the force torque
sensor equipped on the end-effector of the mobile manipulator.
X0 = {2:6, :‘rc, yo, yo, 0c, dc}. 5 is random vector with zero mean and covariance matrix
03. Considering the output vector as Z (t) = {a,r}T, as shown in Figure 3.2, the

output function is described as:

Z(t) = C(Xc) + C (3-13)

where C is a random vector with zero mean and covariance matrix 0,. It is worth

noting that nonholonomic constraint should be considered in (3.12) and the measure-

26

ment ((1, r) should be transformed into the moving frame. By applying the standard
EKF technique to (3.12) and (3.13), an estimate of the cart state variables Xe for Xe
can be obtained. The dotted line in Figure 3.3 (b) shows an estimation of the cart
configuration in the mobile frame Eb. It is worthy noting that both the force/ torque
sensor information and the laser range finder information are used in the estimation

of the cart configuration.

3.2.3 Wavelet Based Model Identification(WBMI)

The on—line parameter estimation problem can be described by a recursive Least
Square Method.

Given a linear observation equation

nzmx+a an)

Y, is an observation vector at time instance r, H. is an observation matrix at time

instance r. X. is an estimated parameter vector. v. is the measurement noise.
Corresponding to the estimation equations developed in section 2, for estimation

of L, Y, is the measurement sequence of ij, H. is the measurement sequence of dc,

X. is the parameter L; for estimation of the mass, Y. is the measurement sequence of
T

the acceleration a1, H. is the sequence of the vector of
—1
The'parameter estimation task can be solved by Least Square Method[30].

The equations of the recursive least square method are:

X. = X._, + K.(Y. - 113.-.), (3.15)

K. = P._1H.[1+H,'.P._1H.]‘1, (3.16)

27

(mm)
640

600
580
560
540

520

 

 

 

 

 

 

 

 

 

 

x 10 (a) Flaw data
: l] i Z l .
,,,,,, ’
1 l] i .w
WEM’W .r”; . 1
2 -1.5 1 -o.5 o 0.5 1 1.5 2(rad)
620»----:- 3 3
‘ ' [ __________
05 -o.4 03 -o.2 -o.1 o 0.1 0.2 0.3(rad)

500

Figure 3.3: Laser range data

28

P. = P._1—P._1K.. (3.17)

To obtain the best estimation of the kinematic length of the cart, we have to find
the proper bandwidth, which causes the minimum estimation error. It is known that
in the frequency domain the true signal is at low frequencies, the major parts of the
noise are at high frequencies. Hence, the measured signal and the true signal have
closer spectra at low frequencies than at high frequencies. Furthermore, to extract
the proper low frequency part from measured signals will improve the estimation
accuracy.

Daubechies Discrete Wavelet Transform(DWT) [15] is applied to decompose and
reconstruct the raw signal in different bandwidth. In this dissertation, a raw signal will
be sequentially passed through a series of Daubechies filters with imposed response
hp(n) for wavelets with P vanishing moments.

To subband a signal, Discrete Wavelet Transform is used, each level of filtering
can halve the bandwidth of the signal as shown in Fig 2.1.

As a result, the raw signal is preprocessed to have the desired low frequency
components. The multiresolution approach from discrete wavelet analysis will be
used to decompose the raw signal into several signals with different bandwidths. This
algorithm makes the signal in this case, the raw angular velocity signal passes through
several lowpass filters, in each level it passes the filter, the bandwidth of the signal
would be halved, then the lower frequency component can be obtained level by level.

The algorithm can be described as the following procedures:

(a) Filtering: Passing the signal through a low pass Daubechies filter with band-
width which is lower half bandwidth of the signal in the last level. Subsampling

the signal by factor 2, then reconstructing the signal in this level;

(b) Estimating: Using the RLSM to process the linear velocity signal and the

angular velocity signal obtained from the step (a) to estimate the kinematic

29

 

Raw Signal
1
Filtering
1
Estimating

i
Calculating Residual

,_ N
e is Increasing?

Yes
Comparing Residuals

i
Estimation Results

1
End

 

 

 

‘

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

 

 

 

 

 

Figure 3.4: The block diagram of WBMI algorithm.

30

length of the cart.

(0) Calculating: Calculating the expectation of the length estimates and the resid-

ual.
(d) Returning: Returning to (a), until it can be ensured that the é is increasing.

(e) Comparing: Comparing the residual in each level, take the estimate of length
in a level, which has the minimum residual over all the levels, as the most

accurate estimate.

The block diagram of the algorithm is shown in Figure 3.4.

3.3 Convergence of Estimation

The least square of estimation residual can be described by

e = [0739(1) — v(t)]2dt (3.13)

and other relationships can be defined as follows:

v(t) = L . We), (3.19)
11(1) = L . was), (3.20)
L=AL+L an)

own) = and) + Aw(t), (3.22)
Ema) = Fm...) + Ma). (3.23)

L is the true value of the length, L is the estimate of the length in least square

sense. v(t) is the true value of the linear velocity, 21(1) is the estimate of the linear

31

velocity, wT(t) is the true value of dc, wM(t) is the measurements of dc and Aw(t) are
measurement additive noise signal of dc, respectively. FwT(w), AF(w) and FwM(w)
are their corresponding Fourier Transforms.

Considering the problem as a minimizing problem, the estimation error can be
minimized by finding the minimum value of the estimation residual e in least square
sense. The estimation residual is in terms of the frequency domain form AF (w) of the
error signal Aw(t). Hence, the problem is turned into describing the relation between
the é and AF(w).

The following lemma provides a conclusion that functions with a certain form are
increasing functions of a variable. Based on the lemma, a theorem can be developed
to prove that e is a function of (%)2 which has the same form as in the lemma. Thus,

the estimation error decreases, as the residual decreases.

Lemma : Let Q : (-—00, +00) and

 

 

_ fonM(w >A F( )3... -
X ‘( slam )va )’ (3'24)
é=§;(/QIAF(w)|2dw— [Q IF...<w )lzdw X) (3.25)

If FwT(w) is orthogonal to AF(w), then e is a strictly increasing function of X.

Proof : AF(to) is orthogonal to FwT(to), i.e.

f0 FwT(w)AF(w)dw = o. (3.26)

32

Simplifying the integrals

[a FwM(w)AF(w)dw = L(Fwanaranar‘am: [a [AF(to)|2dw,

(Inform (Imam + /Q (more.

can move out some terms in X, it is clear that X is a real function as

 

 

_ ammonia) 2
X ‘(13(1F..(w>r+IAvadw) '
It implies
2 _ )0? 2
LIAF(w)|dw—1_fi/QIFW(LU)I dw. (3.27)

e can be expressed in terms of X

('01
ll

£74], IAF(w)|2dw — f. IF... (3)123... - X)

= %(/Q|AF(w)|2dw—X-fflleT(w)|2dw-X-LIAFWWW)

 

 

 

L2 .0? 2
= 5;;(1— m1 _ fl -fQ|Fw(w)l d...
: L2 f9 [er(w)l2dw\/Y
271' '
Let f(X) = 6?, then
f’(X) = LU" lFW<w>|2dw > 0. (3.28)

47rx/X

Hence, given f9 [FwT(w)|2d(.o, f (X ) is an increasing function of X.

Finally, e is an increasing function of X. If e = O, X = 0.

The lemma provides a foundation to prove (Q‘L—l’)2 will reach a minimum value

33

when the estimation residual é takes a minimum value.

Theorem : Given AF : to —> C, C is a complex space. When é takes a

minimum value, (9511)2 also takes a minimum value.

Proof : Consider the continuous case:

62' = [0732(1) — v(t)]?‘dt = form)? — 2v(t)v(t) + v(t)2]dt.

Given 9 : (—00, +00), according to Parserval’s Equation [41],

é: ,1, / (IF( )1 —2F.(w>m+la<w)r)dw.

From (3.20) and linear properties of Fourier Transform, it can be easily seen that

é= ,1, / (1121a... (w )1 _22F,,,(..)—F,.(t))n.+.2.17.r (anew. (3.29)

e is a function of L, then based on the least square criterion the following equation

in terms of L must satisfy

66—:: :i/(L2IFWM (w )l2 _£me(w)Fv(W))d‘-U=O.

The above equation implies that the solution of L can be expressed as

[$13]me (“0'2 — Panama. = 0.

34

Using (3.19) yields

 

 

L __ f9 FwMFv(w)d‘-U _ Lfrz FwMFwT(w)dw

‘ fa IF...<w)I2dw ‘ fa IF...(w)I2dw (3'30)

Let L" = L, substituting (3.21),(3.23)into (3.30) for removing the terms of the linear

velocity yields

L+ALZIQ<IFW (w )I?— We )AF(w >>dw
L 13mm >I2dw

 

(3.31)

There exists the relation between the estimation error (9%) in the time domain

and the measurement error in the frequency domain AF (to),

£9 _ _fn FwM(w)AF(w)dw
L — fa leM(w)|2dw

 

(3.32)

Note X is defined in the beginning of the section, then X = (ALLY

Substituting (3.30) into (3.29) yields

 

é=§L%(‘ffnlp.A(F§.2li.+ +/< ((le. 3)] —IF...Iw>I2+2F...<w>AF<w>)dw)I3.33)
We define:

Ac: /0T(Aw(t))2dt= [0T[wM(t)2—2wM(t)wT(t)+wT(t)2]dt.

Applying Parserval’s Equation to the error signal Aw yields

falAszdw= / (I w)u)|2+|FwM( )l —2F..Iw>“F..“Iw))w.

35

 

= forward» + f, IF...<w>I2dw — 2 f0 Fw..(w)(FwM(w) — Manda».

Therefore,
(manor — Iamrm = [QIIAFW~2F...Iw>_AF(w>>dw. (3.34)

Substituting (3.7),(3.16) into (3.15) e can be given in terms of X

é = 5411mm - X - f. Iamrctw). (3.35)

It can be easily seen that e has the same form as in the lemma, then 6 is an

increasing function of X, for different AF, when (9' takes a minimum value, (93102 also

takes a minimun value. Since the minimum value of e is equal to 0, the (AL—LY will
approach 0 as well. The residual of the estimation is convergence and the estimation

error goes to 0.

36

CHAPTER 4
LINGUISTIC APPROACH FOR ROBOTIC SYSTEM
CONTROL IN PERCEPTIVE FRAME

4. 1 Introduction

In recent years, there has been increasing interest in robot intelligence. As applica-
tions are becoming more and more complicated, robot systems need to have a certain
amount of autonomy. One of the most important aspects of autonomous systems is
the ability to deal with unexpected events in a changing environment. The robot
processes environmental information obtained from onboard sensors, and responds to
the information by changing the original path planning and control schemes. Based
on the perceptive-based approach [60], a hybrid perceptive reference model is pro—
posed, which enables the mobile robot system to autonomously respond to unexpected
events.

A continuous perceptive planning and control approach [60] has been applied to
the path planning and control for a single manipulator, and multiple manipulators
coordination [61]. Song et al. [49] developed an perceptive scheme for integration of
task scheduling, action planning and control in robotic manufacturing systems. The
basic idea of the perceptive planning and control theory is to introduce the concept of a
motion reference 3, a parameter that is directly relevant to measured sensory outputs
and the task. Instead of time, the control input is parameterized by the motion
reference. since the action reference is a function of the real time measurement, the
values of the desired vehicle states are functions of the measured data. This creates
a mechanism to adjust or modify the plan based on the measurements. Thus, the

planning becomes a closed loop real-time process. The planner generates the desired

37

values of the system, according to the on-line computed action reference parameter s.
Figure 4.1 indicates the perceptive control in comparison with the traditional control
concepts.

The perceptive frame approach guarantees stability of the robot system in presence
of unexpected events. However the robot system cannot avoid the obstacle based on
the environmental sensor information. The hybrid perceptive reference model has
three layers, one continuous layer, and two discrete layers. The continuous layer
guarantees the system stability in the presence of unexpected events based on the
perceptive approach. The discrete layers enable the robot system to make decisions

and modify original path plans.

]d(t)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t t (t)

Planner yd(_) 60 Controller Robot y e
(a) Traditional control id“)

yd(s) e(s) , y(t) -

Planner Controller Robot

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Motion Reference

 

 

 

 

 

(b) Perceptive control

Figure 4.1: Perceptive Control

Linguistic / automata approach is the method applying the mathematical tools, for-
mal languages and automata theory, to describe the dynamics of the control system
at discrete levels. Hybrid control system behaviors, thus, can be discussed by hybrid
automata, exhibiting both continuous and discrete evolutions. Brockett abstracted

the concepts of the lattice language based on the analysis of the robot motion[9].

38

A motion description language for kinetic state machines, which are the continuous
analog of finite automata, is proposed in [10]. Furthermore, Manikonda at al. [39]
defined atoms in the language alphabet that describes motion behaviors. The func-
tions of the language are improved to deal with multiple interruptions. In Egerstedt’s
research, a complexity problem of a multiple obstacle avoidance is analyzed by using
motion description language of Brockett’s hybrid model [16]. However, both the con-
tinuous part and the discrete part of the system use time as the reference. In this
chapter, we model the motion planning and control of the mobile robot system by a
hybrid system model based on perceptive motion reference. The perceptive motion
reference hybrid model enables both the continuous part and the discrete part of the
system deal with unexpected events. This discrete part of the system ”supervise” the
robot system based on environmental sensor information such that the system can
avoid unexpected obstacles by modifying original path plans. The discrete part and

the continuous part are integrated by the perceptive motion reference.

4.2 Hybrid Perceptive Reference Model for Control of

Robotic System

A hybrid automaton based model, as shown in Figure 4.2, is developed for robot
system to process both continuous and discrete information, and to give the discrete
levels more intelligence. The system is composed of two major parts, a hierarchical
command execution chain including task scheduler, action planner and motion plan-
ner, a hybrid perceptive reference chain including task level reference, action level
reference and motion reference. The task scheduler, action planner, motion planner,
task level reference and action level reference are modeled by hybrid languages and / or
hybrid automata. The motion reference 3 is a continuous variable which is computed

based on the configuration sensors on the robot system. The concept of hybrid per-

39

ceptive reference is proposed to model a top-down decision making system under the

circumstance of unexpected events. The decision making mechanisms involved in this

model can effectively use the sensory information for higher level decision making.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Command
l
_, Task Level
Reference 1
L” > Task Scheduler
RT v
Action Level [11;
Reference
Action Planner
Lg, ' r
H
Motion 111
Reference ’ Motion Planner
4
[X(s),Y(s). XIs),Y'(s)
Low Level Controller o—
Plant
1 Configuration Sensor
L Environmental Sensor

 

 

 

 

Figure 4.2: An Perceptive reference-based Framework for Robotic Systems.

4.2.1 Languages and Automata

Several concepts for the hybrid system model in perceptive frame are introduced to

discuss hierarchical architecture of the system.

40

An Action Set consists of all the action primitives the robot can execute, for
example, moving a robot, picking up/ placing a part, open a gripper, and so on. The
action set can be denoted as A = {A1,A2...A,,1} where A,,i = 1,2, ...n1 are action
primitives.

A Task set is a set of all the task primitives for a robot system, each of which
may include a few actions. The task set can be denoted as T = {T1, T 2...T "2}, where
T,,i = 1, 2, ...n2 are task primitives. Usually, a task consists of several actions. For
example, the task “ pick up” consists of the actions that include “Go To” and “Close
gripper”.

An Action Reference Set is a subset of the action set. The set can be written
in the form of RAction = {ra1,raz, ...ran3}, where ra,,i = 1, 2, ...n3 are the references
which govern the evolution of corresponding tasks.

The Task Reference Set is a subset of the task set and related to motions. It can
be described as RT“), = {rt1,rt2, ...rm4}, where rt,,i = 1,2, ...n4 are the references
which govern the evolution of corresponding tasks.

The Motion Reference 3 is a continuous reference chosen for lower level path
planning and control. For example, the distance the robot traveled, can be chosen as
the motion reference. Examples of design and analysis of the mobile robot motion
planning and control based on the continuous motion reference can be seen in [60].

The formal languages L ,4, LT, L M and L RT can be built by the alphabets EA, ET, ERA,
and 237‘ that are generated by the discrete variable sets A, T, RAction, RTask, respec-
tively.

The relationships are shown as follows [28]:

ERA = RAction (4-1)

41

2,. = A (4.3)

2T = T (4.4)
LA Q 3:1 (4.5)
LT Q 2T (4-6)

L... g 2),, (4.7)

LRT _C_ 2hr (4-8)

Definition (Hybrid Language). A hybrid language is generated from an orig-
inal alphabet 2, consisting of discrete atoms, and numbers N E R". A word in the
hybrid language can be described as an atom in the alphabet followed by numbers.
The alphabet of the hybrid language is an extended alphabet of a formal language.
A hybrid language is defined as the set of all the strings over the extended alphabet
Z” . In other words, a hybrid language is the concatenation of the elements lying in
the product set of the original alphabet and the Euclidean spaces. A hybrid language
derived from the extended alphabet 2” is denoted L” .

For example, if the alphabet of the hybrid language is the task set T, then the
word in a hybrid language L? can be “T 1 (:13, y)” meaning “going to the point(x,y)”.
The alphabet gives the qualitative description, the numeric part is the quantization
of the linguistic expressions.

Definition (perceptive Automaton). Perceptive automaton can be defined as

a tuple
Me : (Q12123161Q017710)' (49)

where Q is the set of the discrete states of the automaton and )3 is the discrete
control input set. ER is the discrete perceptive reference set. Q0 is a set of starting
states and 6 is the evolutions of states. 17 is the output function. 0 is output, it can

be a vector.

42

Due to the perceptive specification, the following properties describe the state
transitions and the output action trigged by the control command input and the

reference inputs.

q,- = 60130)). (4.10)

0k = 77011.01.) (4-11)

where q.,qj E Q,O)c 6 0,0216 2,0). 6 ER.

The perceptive automaton improves the diversity of the input signals. Corre-
sponding different inputs the automaton can have different responses including state
switching and command issuing. The perceptive automaton is based on discrete
perceptive reference. In order to combine the continuous perceptive reference and
the discrete perceptive reference mentioned above, a hybrid automaton is capable of
bridging the two kinds of variables. Based on [17] [36], a hybrid automaton can be
defined as follows.

Definition (Hybrid Automaton). A hybrid automaton is considered to be a
tuple

M” = (0.x, 23,6, Qo,n,0), (4.12)

where Q is the set of discrete variables, X is the set of continuous variables, 2
is the alphabet of the discrete input, Q0 is a set of starting states, 7) is the output
function and 0 is the output. 0 can be a vector space.

The state transition function and the output function can be described as

0k = 77(qi,0'i,X) (4.14)

43

Definition (Hierarchical Automaton). A hierarchical automaton is an au-
tomaton consisting of several nodes, some of which are other automata. The first
automaton is an upper automaton, the other automata denoting the nodes of the
upper automaton are called embedded automata. Then this architecture can be de-
scribed as a tuple, Mh = (Q0, 62314. Eu. 2314.60.6214, Quo. Q2140. 0),

EU is the input set for the upper automaton, 25M is the input set of embedded
automaton, QU is a set of the states( the nodes of the upper automaton), QEM is a
set of the states of the automata embedded into nodes of QU, Quo is the set of the
starting states of QU, QEMo is the set of the starting states of QEM. 6g and (SEM
describe the transition functions of QU and Q EM, respectively.

perceptive Automaton, hybrid Automaton, and hierarchical Automaton describe
three basic properties of automata based on which the hybrid system framework are
developed. The automata in the framework are thought of as the combinations of the

above three basic prototypes.

4.2.2 Hierarchical Task Erecution Architecture

As shown in Figure 4.2, task execution for a typical mobile robot system is imple-
mented as a Schedule-Plan-Control Architecture. The hierarchical task execution
architecture includes three parts: a task scheduler, an action planner, and a motion

planner. These three parts are modeled using automata.

Task Scheduler

The task scheduler sequentially generates tasks according to the commands and dis-
crete task level references. It is an automaton based on perceptive reference with

hybrid variables.
MTaskSch = (Q1251, 2%1X161Q02n10’1’ask50h)’

where the unexpected event input and task level reference input are in the language

44

LfiT, and L? , respectively. The inputs from the Task Level Reference automaton
trigger the task output in the hybrid language L¥. Logically, it chooses the higher

priority task from the inputs, e.g. obstacle avoidance.

Action planner

The action planner is placed between the task scheduler and the motion planner in
the architecture. The function of the planner is to generate a sequence of actions
according to the task input from the task level. According to the definitions given
above, the action planner is modeled as a hybrid perceptive automaton which can be
described as a tuple,

MActPlan = (Qt2’5””EgA’X761Q01n10ACtPlan)-

It has the perceptive reference inputs in the hybrid language L]: A and the task

inputs in a hybrid language L5! denoted as:

[ActPlanl : L5"! (4.15)

[ActPlan2 = Lit. (4-15)

The output OACtplan is in the language L5,”.

The continuous variables in set X carried out by hybrid language inputs give the
automaton continuous evolutions and can also be used to generate the outputs in the
hybrid language.

The Action Planner has the transition function and the output functions as follows

chtPIanj = 6((1ActPlania 03'), 03' E 23? (4-17)

OActPlank : ”(chtPlania 0k), 0k E 2131.4 (418)

The output can be a vector including several actions triggered by the perceptive

45

reference. The perceptive reference input triggers the output, and the task inputs

cause the state transition of the automaton.

Motion planner

Generally, the motion planner is a mechanism to generate the continuous trajectory
of the designed motion, based on the action sequence from the action planner. The
motion planner in Fig. 4.2 is an automaton that is perceptive reference triggered and
involves hybrid variables. We describe it as a tuple

MMotPIan = (Q12§181X151Q017710M0tPlan)

The continuous reference input 3 is the only variable of the continuous output
function. Another input of the automaton is in the hybrid language L}: from the
alphabet Eff . According to the discrete part of the language input 0 in Lg, the au-
tomaton switches to the appropriate node. Each node of the automaton is a dynamic
system (or a controller) which can issue the planned continuous trajectory for the
lower level controller.

Therefore, the state transition functions and the output functions are:

qMotPlanj : 6(qMotPlaniaaj)10j E 2A (419)

OMotPlank = ”(QMotPIam’, 8) (420)

It can be seen that the state transition and output are triggered separately by
two different inputs. For motion actions, the output to the robot controller can be a
vector in the form of OMotplank = [X (s), Y(s), X (s), 17(3)]T for generating a complete

motion trajectory.

46

4.2.3 Reference Generation

Three references are used in the framework, namely the continuous motion reference,
the discrete action level reference, and the discrete task level reference.

The system has configuration sensors and environmental sensors. According to
the architecture shown above, the environmental sensory measurements are used by
the higher levels for discrete perceptive reference generation, and the motion reference
can be issued based on the configuration sensor measurements.

In this subsection, the automata designed for reference generation are described.

Action level reference

The Action Level Reference automaton has a hierarchical embedded structure consist-
ing of the upper automaton and the embedded automata that are nodes of the upper
automaton. 4.4 This automaton receives the inputs from the task level reference
automaton and the environmental sensors.

The upper automaton and the embedded automata respond to the task inputs
and sensor inputs respectively.

The upper automaton has an architecture as shown in Figure 4.4. Each task input

can change the states of the automaton which can be described as:

Qi : 6(qj20i)1j 74 ian E 2;! (4.21)

In this case, each node of the upper automaton can be thought of as an automaton
embedded in the node. The embedded automata, corresponding to different nodes in
the upper automaton, may be different in state transitions and output generations.
Figure 4.4 shows the architecture of an embedded automaton.

The states and the outputs can be changed based on environmental sensor mea-

surements, i.e. Environmental Conditions(EnvCon), as shown in Figure 4.4.

47

 

Figure 4.3: The Upper Automaton of the Action Level Reference automaton.

Envgonmental
con monl

Envi _o.r1mental
con mon2

Figure 4.4: An Embedded Automaton of the Action Level Reference automaton.

The properties of such an embedded automaton can be described as

0,). = 17(q,j, EnvCon)c = TRUE),j 75 k (4.22)

Qik = 5(qij, ETI’UCOTLk = TRUE),j 75 k (4.23)

Where 0,, is the output to the motion reference automaton and the task scheduler,

which resets the motion reference and triggers the next action.

48

Task level reference

The Task Level Reference can be generated by automaton whose state transitions
and output are triggered by the change of the environment. For example, Figure 4.5
shows how the automaton works while a mobile robot is approaching an unexpected
obstacle. The automaton operates by issuing a proper command response to the

unexpected event.

 

Figure 4.5: An Example of the Task Level Reference Automaton.

The transition function and the output function of the automaton are:

0,- = 17(q1 20,-) = A0(.),o,- E 235! (4.24)

o,- = 77(q2 : o.) = 02,0,- 6 E? (4.25)

Where A0 denotes Obstacle Avoidance, d is the distance between the mobile
robot and its nearest obstacle; and do is the minimum safe distance between them.
The outputs in language LfiT go to Task Scheduler and the Action Level Reference
automaton, respectively.

The robot controller design based on a continuous motion reference is referred to

[60]. Essentially, the nonlinear feedback control law is given by [60] as

49

1' ..—.. D(q)J,,—1[Yd(s) + K,é(s) + K pe(s) (4.26)

-—Jhril + C(44) + 0(a)

The dynamics of the robotic system with continuous perceptive reference is described

as

du)
_=2 4.27
d8 a ( _ )
do
—= 4.28
d3 u ( )

4.3 Perceptive Control for Mobile Manipulation and

Tele-Operation

A typical application of the proposed model is the execution of a scheduling-planning-
control task in mobile manipulation. The task is to pick up an object and transport
it to a desired destination with a mobile manipulator. In the route of transporting
the object, an unexpected obstacle occurs. In order to complete the task, the mobile
manipulator will execute an obstacle avoidance task. The mobile manipulator will

then resume its original task and reach the destination.

4.3.1 Hybrid Languages

According to definition 6, the hybrid language can be composed of an extended alpha-
bet. Each word contains the primitive discrete atom followed by the values of continu-
ous variables. The task set can be defined as T = {T1, T2}. T1 means “transporting”,
T2 means “avoiding an obstacle.” As defined above, the action set is A = {A1, A2},

where A1 means “following a straight line,” and A2 denotes “going through an are.”

50

To build the hybrid languages for the task set and action set, some continuous vari-
ables can be added to describe the atoms. In the extended task set, T1(m1, n1)(m2, n2)
denotes “transporting an object from point(m1,n1) to point(m2,n2).” T 2(m,n, l0)
denotes “to avoid an obstacle at(m, n) at the distance l0.” In the extended action
set, the A1(m,n,l) denotes “following a straight line with directional cosine (m,n) and
length l.” The A2(m,n,r) denotes “go through an are centered at (m, n) with length

r.” A3 and A4 denote “close the gripper” and “open the gripper”, respectively.

4.3. 2 Task Execution

Task Scheduler: The output of the task scheduler is T1(m1, n1)(m2, n2) until the
obstacle has been detected.

Action Planner: Based on the input T1(m1, n1)(m2, n2), the transition and the
output of the action planner are qu1 = (q0,T1) and OAPI = g(qu1,reset) = A1.
When the planner has the action reference input A1 meaning that the A1 action is
finished, the output action triggered by A1 is a vector 0 A p1 = g(qA p1, A1) = [A2, A3]T.
The output triggered by action reference A11 is another action 0,4121 = 17(qA p2, A11) 2
A4. The directional cosines and the length between A1 and All can be found with
the parameters in T 1 geometrically.

Motion Planner: The inputs A1(m1,n1, l1), A11(m11,n11, l11) E Eff cause the
states transition of the motion planner. qMotpzanl = 6(qo, A1), qMotpzanu = 6(q0, A11).
The states denote different trajectories, ex., straight line path and are path. Corre-
sponding to the continuous perceptive reference input, 3, the distance the robot trav-
eled, the continuous trajectory outputs can be described by the following equations:

for a straight line path

at = mV(s) (4.29)

y = Tit/(3) (4.30)

51

for a circular Path(an arc)

:1; = m + TC08(S/T) (4.31)
y = n + rsin(s/r) (4.32)
2 = —%V(s) (4.33)

4 = $148) (434)

In this case, the trajectory is made up of two pieces of straight lines A1 and All.
Action Level Reference: The nodes of the upper automaton denote differ-
ent paths, namely two segments of straight lines managed by the same procedure.
The state transition is qu = 5AR(qARo, T1(m1,n1)(m2, n2)). The output function
and state transition of embedded automaton M ARI can be described as 0,4311 2
g(qARm,L 2 l1) and (1.41211 = 6A31(qA310,L 2 II), respectively. L is the length the

robot traveled since the new action started.

4.4 Description for Language-Based Hybrid Perceptive
Reference
In order to study the properties of the proposed model, the hierarchical architecture
is considered as an integrated system. to describe the robotic manipulation system

in the perceptive frame, Hybrid Perceptive Reference space is introduced in this

dissertation.

4.4.1 Hybrid Perceptive Reference Space of Robotic Manipulation

System

Considering the traditional time based systems, the reference has two significant

features. First, it is a variable in a metric space. Second, it evolves itself forward

52

during the operation of the system.

The system illustrated in Figure 4.2, the hybrid system model, can be described
with perceptive references and states, which can be expressed in a hybrid fashion.
A hybrid perceptive trajectory is a finite or infinite sequence of reference interval
e = {STmSARJ-SK}, where SK 6 [0, 85,] = Ismsrni E 2%,SARJ- E 2%,. Although
the first two parts of e = {STRiSARJ-SK} have the continuous components, these
components are stationary. The perceptive references at the task level and the action

level can be still thought of as the discrete parts. The item sK is a continuous variable.

4.4.2 Hybrid Metric Space

For the discrete topology, the hybrid metric can be generated in the following fashion:
d(STRt1SARj1. STRz'ZSARfl) = 2 if STRil ¢ STRi2.
d(3TRiisARj1, STRiZSARfl) = 1 if STRilSAle = STRiZSARfl, SAle 7f 341132
For the continuous item sK, the metric is d(sK,-, SKj) =|| 3K,- —- sKJ- I]
Claim: the product space STR x S ,4); x S can be generated by the matric:
dD(STRt15ARj15K1, STRi2SARj2SK2) = d(STRiISARj11 STRiZSARj2)+ II 3K2 — SKj II-
Proof:
(1) “d” can satisfy the metric symmetric axiom ;
(2) dD(STRiSARjSK, STRz'SARjSK) =

d(STRiSARj1‘STRiSARj)+ I] 3K - six I] =0;

(3) It satisfies the triangle inequality.
For the discrete parts:
Let dD(1,2) denote dD(STR,-ISARJ-1, STRizsARjQ),
dD(2, 3) denote dD(STRi25.4Rj2, STR1’3SARj3)a
and dD(1,3) denote dD(STR,-13ARJ-1, STRi3SARj3).
If dD(1,2) = 2, dD(2,3) = 2. Then dD(1,3) g 2, dD(1,3) S dD(1,2) + dD(2,3) = 4;

53

Ide(1,2)=1,dD(2,3)= 2. Then (100,3) = 2, dD(1,3) S dD(1,2) + dD(2,3) — 3;
Ide(1,2)= 1,dD(2,3)=1. Then dD(1,3) S 1, dD(1,3) S dD(1,2) + dD(2,3)
)

If dD(1,2) = 0, dD(2,3 = 1. Then dD(1,3) = 1, dD(1,3) g dD(1,2) + dD(2,3) = 1;
If (100,2) = 0, dD(2, 3) = 0. Then dD(1,3) = 0, (100,3) 5 (100,2) '1' dD(2,3) = 0;

For the continuous parts, the triangle inequality can be satisfied. Thus, d is a metric.

4.4.3 Independent Evolution

The perceptive reference is working as a “clock” or a “driver ”, to trigger the planning
and control activities. The triggering reference should evolve independently along a
chain, an evolving chain, which plays the role of the time in the traditional time-based
systems.

The “time” can be described as an ordered set. There exists a subset of the
partially ordered set which is a totally ordered set.

We define the binary relation “j”, for perceptive reference value a and b, we say
a j b if the time at which event a happens precedes to the time at which b happens.
It can be proven that the perceptive reference trajectory is ordered by the binary
relation “j”.

In an execution of a given task, the continuous reference 3 is a monotonic increasing
function of time. Then the continuous part of the reference is ordered. Based on the
sensor information and the task level linguistic input, the output of task level reference
is ordered by the task sequence.

From the model of the action level reference q, = 6(Qj, 0,), it can be seen that the
output of this level follows the order of the order of the state transitions on the upper
automaton.

It means that if STE“ j Sum, then STmSARJ-SKJ- -< STmSAmSK, for any i and

Given a, b E {STRiSARj SK}, the reflexivity and antisymmetry can be satisfied.

54

The transitivity can be stated by the ordering characteristics of the three level
references. Finally, for any a, b E {STRiSARJ-SK}, satisfy the relation a j b or b j a.

A perceptive reference trajectory is {STRi S A Rj S K}, a totally ordered set with the
binary relation j.

Therefore, the perceptive reference can evolve independently over time.

4.5 Hybrid State Space Model for Robotic Manipulations

We denote the state of the integrated system in a hybrid way:

Let X h = {qTquMX} be a hybrid state, where (17 is the state of task scheduler,
qA is the state of action planner, qM is the state of motion planner. qT,qT, and qT are
discrete variables, X is the continuous state of the low level control system. Similar

to the perceptive reference description, the metric of the state space can be defined by

dD(qT1qA1qM1,qT2qA2qM1) = 3 if cm # cm,
dD(qT1inqM1, qT2qA2qM1) = 2 if QTi = 9T2, 9A1 7'é QA2
dD(QT1qAIQMlaQT2QAZQM1) = 1 if(1T1CIA1 = (IT2QA2, (11m 7‘5 41142

d((IHlaQH2) = dD(QT1QA1QM1aQT2QA2QMI)+ ll X1 — X2 H

We denote the hybrid system as dXh/ds" = f (X h,u(sh)). Therefore, the entire

system can be described in the hybrid space.

55

CHAPTER 5
ANALYSIS OF CONTROL SYSTEM IN PERCEPTIVE
FRAME

5. 1 Introduction

The proposed control method is described in the perceptive frame. The nature of the
hybrid perceptive reference ensures the control model has the specifications from both
the hybrid systems and the evolution of the perceptive references. Hybrid systems
have been extensively investigated in the past. One of the limitations in the literature
is that most of the discussions are time-based. On the other hand, it is desirable to
develop the analysis methods for the dynamical properties of the hybrid switched
system with hybrid perceptive reference and states.

Based on the description of the references and hybrid states of the integrated
system. In this chapter, the analysis issues will be focusing on the evolution property
of the perceptive references, stability in hybrid space, and instruction complexity

during the unexpected event processing.

5.2 Evolving of Perceptive Reference

Any non-time reference is generated by the observation of the environment or the
system states, which are independent from time. For instance, the distance the mobile
robot traveled can be chosen as the motion reference. The evolution of the reference
can stopped by the obstacle that blocks the motion of the system until the block is
released. Thus, evolving is crucial for perceptive reference.

The system illustrated in Figure 4.2, the hybrid system model, can be described
with perceptive references and states, which can be expressed in a hybrid fashion.

A hybrid perceptive reference trajectory is a finite or infinite sequence of reference

56

interval e = {STmSARJ-Sij},,j, where 5,,- = [0, 30-], STE,- E 2%, SARJ- E 2%,. We
denote 3" as the value of the hybrid reference, i.e. 8" E e. Furthermore, an execution
of a hybrid perceptive automaton describes a collection x = {e,qM,x}, where e is
a hybrid perceptive reference trajectory, qM is a map from STRiSARj to Q, and 2:
maps the continuous reference 3 to the continuous state space. We define L, is the
minimum value of the sum of the distance, i.e., L, = ESQ-j. An execution is minimum
if L, = min{ES,-j}.

A hybrid system is called deterministic if the system has a unique minimum exe-
cution.

To simplify the problem, we impose the following standing assumption.

Assumption: For given initial states (qO, 3:0) and inputs, the minimum execution
in the perceptive frame is unique for a given hybrid system, i.e., the execution is
deterministic. Furthermore, the execution continuously depends on the initial state
and inputs.

The system in the perceptive frame is driven by the evolution of the perceptive
references. The hybrid perceptive references are introduced to keep the system evolv-
ing.

A discrete transition of the hybrid perceptive references occurs when an unex-
pected event blocks the evolution of the references. Such an event can occur at any
state (qb, 201,) corresponding to the perceptive reference eb = {STRbSARbSb}. It could
lead the system to another state from which the execution has unique solution to the
final state and the evolution of the perceptive references cannot be blocked by the
unexpected event again.

This fact is stated more formally in theorem (Evolving) in the section of proposed
work.

One of the major advantages of the use of linguistic control in perceptive frame

is that the perceptive control method can modify the preplanned trajectory in the

57

presence of unexpected events. Generally, in the time-referenced systems, replanning
the path is required as the system is blocked by unexpected events, it causes extra
computation complexity in this respect. The control systems in perceptive frame
are driven by perceptive references, in other words, for robotic systems, the path
and control command generated according to the perceptive reference, once the path
planning is accomplished, the desired path is triggered by the events in the perceptive
references(X = P(s"). It gives the system a large flexibility in planning and control.
When the unexpected events block the evolution of the perceptive reference, the
system can switch to avoid the blocks and eventually come back to the predefined
perceptive reference, then resume the preplanned path without replanning.

Definition (Reference complexity): given a perceptive control system, and a lin-
guistic description, the reference complexity of a given task T is given by the minimum
length word STRISARl, STRISARQ...STRiSARju., it is denoted as C(T). Moreover, the
reference complexity can represent how many discrete switches the system should
make when the system start from an initial state to a destination state.

This can be described based on the architecture shown in Figure 4.2. The state

transition function and the output function for the action planner are:

chthanj = 6(QActPlaniaaj)aaj E 2? (5'1)
OActPlank = ”(QActhamt, 0k),0k E 2:21,; (5-2)

The state transition functions for the motion planner

QMotPlanj = 6(QMotPlaniaaj)aU j E EA (5-3)

Intuitively, if the states are different in the task level, the system needs to switch
and plan a new task for example, if the states will switch at the action level, it does

not cause the transition on task level. then complexity could be reduced without the

58

task level scheduling.

Assume that for a given task, the average of the minimum length of the word is N.
There exist N unknown static obstacles on the preplanned trajectory. The unexpected
events make the mobile robot switch the discrete state to avoid the current segment
of the preplanned execution. The instruction complexity is N + M >1: b, if the system
replans the path every time, the total instruction complexity is N + (N — 1) + (N —
2)...+, the order of the complexity is N 2.

The proposed method is capable of dealing with unexpected events, which can
block the perceptive reference. It is essential to describe and prove this proposition
theoretically.

Proposition (Evolving): Given any state ((111,135) 6 X0 = {e, q,:r}, on an
execution of the hybrid automaton, there exists a discrete transition to qt 6 Q,
the system has a unique minimum execution xm = {e,q,x} to the final state, and
(qbaxb) ¢ Xm = {641,33}-

Roughly speaking, the proposition explains that since both the initial state and
the final state are placed in the defined reachable domain, the system has a unique
solution. The continuous dependence on initial conditions guarantees that the hybrid
system cannot reach the state blocking the evolution of the continuous perceptive
reference.

To investigate the ability of the proposed perceptive control model to reduce the
complexity during the unexpected events is one of the future research issues. As
the environment becomes increasingly complex, in particular, the dynamic obstacles
may occur on the trajectory of the robot. The dynamic obstacles may block the
mobile robot at any point with any possible velocities. It causes the extra instruction
complexity in the perceptive frame. The perceptive frame control takes advantage of
the sensor information which contains the knowledge of environmental changes.

In order to reduce the complexity, two approaches are considered. First, the

59

hierarchical architecture shows that if the perceptive reference of the system can
conduct discrete transition on the lower level, the complexity can be reduced, because
the transition on task level usually consists of several low level actions. Second, the
complexity is largely depending on the event-triggering architecture. The perceptive
reference has rich information about the current state of the system and environmental
changes. How to employ the perceptive information in a complicated environment

with multiple obstacles or dynamical obstacles, therefore, is crucial.

5.3 Stability of Perceptive Control System

As a dynamical system, the robotic manipulation system has to be stable. For mobile
manipulation systems, the controller can run in different types, motion control of
the mobile base or motion control of the robot arm, and autonomous control or
teleoperation control. The segments in different types of control form the whole
control procedure.

Lyapunov stability plays an important role in the control system analysis and
design. In [63] [60], for continuous perceptive systems, it has been proven that if a
system is asymptotically stable with time t as its motion reference base, and if the
new motion reference 3 is a (monotone increasing) non-decreasing function of time t,
then the system is (asymptotically) stable with respect to the new motion reference
base 3. The time-based Lyapunov function V(t), then can be described as V(S), i.e.,
the Lyapunov function for motion reference based system.

For the hybrid model, an execution is a sequence of segments described by the
perceptive reference trajectory and the corresponding hybrid states.

For the system dx/ds = f (:23), we say that V(s) is a candidate Lyapunov function
if V(s) is a continuous positive definite function ( about the origin 0) with continuous
partial derivatives. Note this assumes V(O) = 0.

Considering switched hybrid systems, the systems operate in a hybrid metric

6O

space. The stability property of such systems could be described in the hybrid state
space of the perceptive frame. Therefore, multiple Lyapunov function can be used to
discuss the stability issue.

Given a dynamical system in the perceptive frame, if there exist Lyapunov func-
tions V1(sh), V2(sh)... with hybrid perceptive references, corresponding to the hy-
brid perceptive reference trajectory and different segments of executions, for a given
strictly increasing sequence of STRiSARj (discrete reference values), denoted by I =
STRiSARj in the perceptive reference, we say that V is a Lyapunov-like function for
function f and execution X = {e, q, 12:}, if
1. dV(:1:(s"))/ds S 0
2. V is a monotonically non-increasing on ordered set I.

Theorem (Lyapunov Stability): Suppose we have candidate Lyapunov func-
tions V,,i = 1...N, and vector field dx/ds = f,-(:c) with f,(0) = 0, Let E be the set of
all switching sequences associated with the system. If for each s" E E we have for all
i, V,- is Lyapunov—like for f,. Then the system is stable in the sense of Lyapunov.

Proof: Given a strictly increasing sequence of STR,SAR,-, we denote the time at
which the reference happen as T(STRbSARb). Because the perceptive reference is an
ordered set by relation j, i.e., T(82) 5. 7(33), for any 32 j 35;. Based on the stability
theorem in [60], the corresponding time based functions have the identical monotony.
From [6], for the case if N = 2, or N > 2, we always can pick a small neighborhood
of the origin with p from that the trajectory will stay in B (7'), which is the minimum
ball around the origin over all the possible Lyapunov functions.

When the system has only one vector field dX/ds" = f (X ), for any given seg-
ment of execution x = {e, q, :r}, the continuous reference evolves in the interval[0, 3]
due to the discrete transitions of the discrete perceptive references. The system is
still stable since Lyapunov—like functions keep the monotony properties under these

circumstances. The strictly increasing sequence of STRiSARj still exists. Hence the

61

Lyapunov stability can not be changed by switch of the references. The multiple
Lyapunov-like functions provide a convenient way for analyzing the state stability of

the switched systems and the further discussion on input-state stability.

5. 3.1 Input-State Stability of Hybrid Perceptive Control

The given hybrid control model can be thought of as a forced control system. Hence,
the input-state stability is required, in particular, for the hybrid switched systems.
One of the future research issues is to study the input-state stability on the hybrid
control model. Switched control inputs on the low level controller of the given system
model can be thought of as piecewise continuous and bounded function of sh.
Definition The system above is said to be locally input-to-state stable if there
exist a class KL function B, 191 and k2 such that for any initial state x(sg) with
H x(sg ”S In and any input u(s") with supshtsg ll u(sh) ||< k2, i.e., for any bounded

signal. The execution on the system exists and satisfies

ll X(8") IIS fi(|| 03(83) ||,do(h‘,83)) + v(sup ll u(S) II) (5.4)

It is said to be input-to-state stable if the above inequality is satisfied for any initial
state and any bounded input u(s")

Based on the definition, we will discuss the input-to—state stability of the system
with the hybrid perceptive reference, when the corresponding time based system have
input—to—state stable for the given conditions on the time-based input.

The input-to—state stability can give an approach to analyze the system stability.
In particular, the hybrid systems have to deal with the control signal with different
switched segments due to and different control types including teleoperation and au-

tonomous control. different control inputs require the input-to-state stability. Control

62

signal can be tracked. input-to—state stability can guarantee that the control signal
can be tracked by the hybrid system in the perceptive frame.

Theorem 1 (Stability): Suppose we have candidate Lyapunov functions V,,i =
1...N, and vector field dx/ds = f,(x) with f,(0) == 0, Let E be the set of all switching
sequences associated with the system. If for each sh E E we have for all i, V} is
Lyapunov-like for fi. Then the system is stable in the sense of Lyapunov.

Proof: Given a strictly increasing sequence of STRiSAI-Zj, we denote the time at
which the reference happen as 7(STRbSARb). Since the perceptive reference is an
ordered set by relation 5, i.e., 7(82) S 7(83), for any 32 j 3?. Based on the stability
theorem for continuous perceptive system, the corresponding time based functions
have the identical monotony. According to [5] for the case if N = 2, or N > 2, we
always can pick a small neighborhood of the origin with p from that the trajectory
will stay in B (r), which is the minimum ball around the origin over all the possible
Lyapunov functions.

Theorem 2(Exponential Stability): Suppose we have candidate Lyapunov
functions V,,i = 1...N, and vector field dx/ds = f,(x) with f,(0) = 0, Let E be the set
of all switching sequences associated with the system. In the perceptive fmme, if for
each sh E E we have for all i, V,- is Lyapunov-like for f,. Then the system is exponen-
tialy stable in the sense of Lyapunov. If There exist constants ag, fig,'7g, g = 1, ...,l,

such that:

-- V33 6 QOQUI a? II) S V903) S [39(ll a? ll) (5-5)
—— Vx E Q,

for switching from q to r.

Proof: Since the perceptive reference can be introduced in to the hybrid system.

63

The Lyapunov function V, has the reference segment, which evolves from 0, after
discrete transitions. Then in the given case, V,.(x) S Vr(x(t1))/(—7r/fir(3)), Since

Vx E Egr, V,.(x) S Vg(x) for switching from g to r.

ll $(t) HS 56“” || 22(3") ll - (5-7)

N = 6(8 — 3") (5.8)

h

Where perceptive reference 3 is a discrete transition. Therefore the system is expo-

nentially stable in sense of Lyapunov.

5. 3.2 Continuity of input-output mapping

The offset on the continuous variables of the task level linguistic inputs. For the tasks,
which have the same discrete task but different continuous variables, i.e., two task
controls in the same task subspace, if the continuous parts approximate sufficiently,
then the states of the system are sufficiently close to each other.

It can be formally described by followings:

For a given task subspace T,, the mapping L is referred to as a continuous mapping,
if there always exists an e, for given 6 such that H AA ||< 6, when II AT ||< 6. The
intuitive meaning is that both the task and the action will evolve continuously. The
norm || AA H is referred to as the sum of all the action offset. I.e., || AA II: 23 || AA,- ||.
Thus, the input and output of the task controller in the linear space T and A are

continuous dependent.

5. 3.3 Stability conditions for switched systems

The stability conditions include two parts. First, the switching between the task

subspace with different dimension is stable under certain conditions of Lyapunov

64

functions. Second, the continuous variable of the task input do not spoil the stability,
if for a given value, the system is stable.

Assumption: The input and the output of the task controllers in linear space are
continuous dependent.

Claim 3: If the vector fields corresponding to the switching task T1 and T2 in
Q1 and (22 are exponentially stable. Then given any continous part T1 and T2, the
switching tasks will be stable.

Proof: The control input of the low level controller is generated by linear mappings
L : T— > A and L’ : A— > (2, so the mapping L(L’) follows lipschitz condition, such
that H L(L’)($) - L(L’)(y) _<_ l H x - 31 II-

For the conditions of the theorem 2 still hold, for a close loop controller, we have:
Vx E (2i, 6Vi(x)/Bs = 8Vi(x)/0x . f(x,s), (5.9)

Then, from different vectors T in the same task subspace, Au is defined as the pertu-
bation the controller caused by the offset of the vector T1 and T2. Substitute linear

mappings L : T— > A and L’ : A— > 9 and lipschitz coefficiant l.

H e(t) HS 1/15 - (6“) ll 16(8?) || - (5-10)

M = —5(s — s?)/l (5.11)
The system is stable in sense of Lyapunov during the task switches.

5.4 Modeling of Unexpected Event

The ability to deal with unexpected events is crucial for a perceptive control system.

Q represents the set of the vector fields, (q1,...,q,,), for a m—dimensional space, at

65

least it has m m—dimensional orthogonal vector fileds. f1...fm. Therefore, for any 2
points x1 and x2, the system can start from x1, x2 within finite time of switches over
the vector fields.

In task execution, the continuous reference 3 should satisfies: L ,5 (q,x) > 0, it

guarantees that the continuous reference is an increasing function of the time t.

5.4.1 Unexpected Events(UE) in Robotic Manipulations

Unexpected events in robotic manipulations can be described as follows:
For a given e = {STRiSARjSK}, Where SK 6 [Sk,3;¢l,STRi E 259,5.433- E 221/1.
and an execution of a hybrid perceptive automaton x = {e, g, x}, A unexpected event

happends, when the following two condition hold:

ds/dt IS = O,S = s: E (3623?), (5.12)

5: 3‘ STRI, SARJ- (5-13)

Furthermore, an unexpected event represents a convex region U A that is an open
set of states, in which the above conditions hold, the boundary is a scalar function
w(x) = 0, and w(x) > 0 for x E U ,4, when UE happen, using “Lie Derivative”, we
have wa(x) > 0,w(x) = 0.

It is a local blocking event of Task T if we can find a subset of the trajectory

X1 = {st.q.$}, where 3t = (82.8?) 9! UA-

5.4.2 Unexpected Event Processing in Perceptive Frame

For hybrid automata, the unexpected events can be described as a disturbance for a
system. The system is desired to be able to return to the designed trajectory after

the disturbance. Or, the unexpected events can be treated as a task executed before

66

finishing the current task. The new task is to switch out of the blocking state then
return to and resume the previous task. For the given model, the unexpected event
will affect the states, causes a discrete state transition. A new vector field will be
applied on the continuous states of the system. which is an orthogonal vector field
to the old one, < f,(x) - fi+1(x) >= 0, then it can satisfy the following conditions:
Lf,+,w(x) < 0, Lf, +1S(q, x) > O, the former makes the system leave domain UA
from the boundary w(x) = 0, the latter guarantees the evolution of the continuous
reference.

The following theorem shows the existence of the solution at unexpected events
in the perceptive frame.

Theorem 4: if the unexpected event eu is a local blocking event, there exists
another finite automaton and with the same alphabet, corresponding to the new au-
tomaton, the automaton can go back to the original task trajectory X = {e,q,x}.

The following is the sketch of the proof of the Theorem 4. Since the given UE is
a local blocking event, B — U A is a path connected domain. There exists a sequence
of vectors connecting xeu and x8, 3 = sretum 6 st, which is l1...l,,, p is a finite number.
Since the vectors can be described as the trajectory in the given orthogonal vector
fields though a linear mapping M, then the trajectory can be decomposed as a finite
number of the connected segments in the switching vector fields. We denote the
segments with the action level alphabet, as wl...wm, m is a finite number.

Based on the sequence of the segments, a new automaton can be built for UE
processing and switching back to the original task. The string of the corresponding

automaton is wl...wm, which is embedded in the string of original task execution.

5.4.3 Unexpected Event Processing: An Example

In Mobile Manipulation, after an unexpected obstacle is detected, the task reference

generates the event of obstacle T2(mo,no, lo), the output of the task scheduler is

67

T 2(mo, no, lo). It causes a discrete switch over discrete variables, an obstacle avoidance
on the task execution to switch and resume the evolution of the continuous perceptive
reference. When the effect of the unexpected event is removed, the robot will resume
the previous task to reach the destination. The perceptive reference will never be
blocked.

Action Planner: The transition function and the output function are qu2 =
5((IAP1, T2(mo, 710)) and 0.4132 = ”(4.4102, reset) = A2(ma2, ”:12, 7112), respectively.

Motion Planner: The motion planner receives the action A2(mag, n02, rug) from
the action planner, the outputs can be described by equations(3.30) (3.33).

Action Level Reference: This automaton has a state transition on the upper
automaton due to the unexpected event and returns to the previous state after the
process of the unexpected event. The triggered procedure is the same as in the task

execution process.

A0_finish-

    

W

Figure 5.1: Unexpected Event Processing in the Task Level Reference.

The transition function and the output function are qu2 = 6(qu1,T2(mo,no))
and 0,4122 = 17(qu2, reset) = A2(mag, nag, Tag), respectively.

The motion planner receives the action A2(mag, nag, rag) from the action planner,
the outputs can be described by equations(3.22)-(3.25).

This automaton has a state transition on the upper automaton due to the unex-
pected event and returns to the previous state after processing the unexpected event.
The triggered procedure is the same as in the task execution process.

In real time tele—operated systems, it is important to synchronize the command

68

from the operator to the arm controller. The time delay of the communication be-
tween the Operator and controller will significantly affect the control performance. If
the controller cannot receive the next position or velocity command before it finishes
executing the current one. It has to st0p or just keep going on the current velocity,
the former reduces the smoothness of execution while the later causes large control
errors. In the hybrid perceptive frame model, the delayed command is thought of as
an unexpected event on action level, that can prevent the discrete perceptive reference
from evolving.

The routing for the unexpected event is to switch to another action which decel-
erates the motion to make the trajectory smooth until the next control command is
received then switch back to the previous state and the path plan is modified. As the

result, the hybrid perceptive reference cannot be blocked.

69

CHAPTER 6
EXPERIMENTAL RESULTS

6.1 Experimental System Setup

The experimental system, as shown in Figure 6.1, is an integrated control system.
The hardware structure and the software structure of the system will be introduced

in this chapter.

6.1.1 Hardware Structure

The robot controller is a computer control system. The mobile manipulator has two
PCs for the Puma 560 control and the mobile robot. Both PCs in the mobile manipu-
lator are communicating with the workstation or PC whose interface can have humans
involved into the control process. Human intervention is involved through joystick
controller. Two kinds of force-feedback joysticks are employed in the experimental
system: the MicroSoft(MS) joystick, which can send the human motion command in
velocities, and the Phantom joystick, which issues the motion command in positions.

The mobile manipulator has a laser range finder, which can measure the distance
of the object ahead with a uniformly distributed bundle of laser lights. The encoders

of the mobile manipulator can measure the position of gripper.

6.1.2 Software Structure

The control software of the experimental system consists of:

0 Robot Arm Control program: A program for controlling the Puma 560.

a Mobile Base Control program: This is designed for motion control of the

base and collection of sensor measurements.

70

 

 

 

 

 

 

 

 

 

 

 

    

 

 

 

Puma 560
Pentium (force/torque,
PC 1 accelerometer,
- A BDCOderv
s b -
53 U Mobile Robot
. (Laser R8089
Pentium Finder, sonar,
PC2 Infrared,
encoder,
actuator)
Nonholomomic
Cart
f
PC3 _
User Interface Phantom
Joystick
2
MS
Joystick

Figure 6.1: The Experimental System

0 Mobile Base Control Proxy: It is a program to receive the command from

the shared memory and send the commands to Mobile Base Controller in P02.

0 Online Model Learning software: Based on the measurements from the
laser range finder, the encoders and the force/ torque sensor, the parameters of

the model for the cart can be estimated.

71

0 Hybrid Linguistic Control program: This is the high level controller of the

experimental system, running in the perceptive frame.

0 Joystick Client User Interface: The interface software converts the mea-
surements of human operation on the joystick into motion control signals and

sends the control signals to a remote motion controller.

0 Joystick Control Server: This program is running in PCl and designed
to receive the commands from Joystick Client User Interface, then send the

commands to the shared memory in PCl

 

 

 

 

 

 

 

 

 

 

 

 

 

Robot Arm (Puma) Mobile Base
Control (PCI) Control (PC2)
Puma Arm Control Mobile Base Control
Sensing Seming
User Command Interface ‘l g l

 

 

 

   

_ _l_ _ _ Mobile Base Conn-01
Shared Pl Pm" (Pa) f

_ _ _ _ ‘— Hybrid Perceptive

 

Joystick Server
(PCl)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Control (PCl)
Sensing-Based Hybrid
, Perceptive Reference

Joystick Client Online Model
Interface (PC3) Leurmn' g (PC2) Linguistic Control

. in perceptive frame
Communication Filtering
Sensing Hurmn Estimation

Operation

Force feedback
Implementation

 

 

 

Figure 6.2: The Software Structure of the Experimental System

Figure 6.2 shows the modules in each program and the relations between the

control programs, based on the hardware structure shown in Fig. 6.1.

72

6.1.3 Robot Controller and Task Modeling

The mobile manipulator can be controlled remotely by an operator through the joy-
sticks or can run autonomously by a computer program.

In perceptive frame, the robot controller can be described as

T = D(q)J,,-1[1?d(s) + K.é(s) + er(s) (6.1)

41.4] + C(q, <2) + C(q)

The dynamics of the robot is described as

dw__

E _ 2a (6.2)
do

Where W 2 v2. As shown in Figure 6.1, the task model is a nonholonomic wheeled
cart. The cart has two omnidirectional wheels installed on the front of the cart, and
two rear wheels which are mono-directional. A flat board is installed on the back of
the cart. The laser range finder can detect the distances to the points on the board

based on which the orientation can be estimated.

6.2 Experimental Results for Online Model Learning

The proposed model learning method has been tested using a Mobile Manipulation
System consisting of a Nomadic XR4000 mobile robot, a puma560 robot arm attached
on the mobile robot. A nonholonomic cart is gripped by the end-effector of the robot
arm as shown in Fig.1. There are two PCs in the mobile platform, one uses Linux
as the operating system for the mobile robot control and the other uses a real time
operating system QNX for the control of the Puma560. The end-effector is equipped

with a Jr3 force/ torque sensor.

73

In order to identify the model of the cart, two types of interaction between mobile
manipulator and the cart are planned. First, the robot pushes the cart back and
forward without turning the cart. The sensory measurement of the acceleration and
the force applied to the cart can be recorded. Second, the cart was turned left and
right alternatively to obtain the sensory measurements of the position of the point A
and the orientation of the cart.

To estimate the mass of the cart, Recursive LSM is used. The measured accel-
eration signal and the measured signal of the pushing force have independent white
noise. Hence, the estimation should be unbiased. The estimate of the mass of the

cart can be obtained directly by LSM.

7O

 

 

 

 

 

 

o 5 1o . 15 2‘0 25
T1me(s)

Figure 6.3: The mass estimation, for m=45 Kg.

Fig.6.3 and Fig.6.4 indicate the mass estimation process. In the beginning, the
estimation is oscillating, however, a few seconds later, the estimation became stable.
The mass estimation results are listed in Table 6.1.

According to the proposed method, the algorithm filters the raw signal to have
different bandwidths. The experimental results are shown by the graphs below.

The figures(Fig.6.14, 6.15 and 6.16)indicate the e and the parameter estimation

74

 

100 M I 1 j I I
801- H . — .

604

 

 

mass(kg)

40~

 

 

 

 

 

 

5 10 , 15 20 25
T1me(s)

Figure 6.4: The mass estimation, for m=55 Kg.

 

70 m f f ' T

w
G
I

 

 

 

 

l l

 

0 5 10 Time(s) 15 20 25

Figure 6.5: The mass estimation, for m=30 Kg.

errors in different levels, in case of L=0.93m, 1.31m, and 1.46m, respectively.

The horizontal axes represent the index of the estimation level, the level here
means the estimation stage as shown in figure 6.14, 6.15 and 6.16. There is maximally
13 estimation stages in this estimation, therefore the index of the levels ranges from

1 to 13. The vertical axes of the figures represent the absolute value of relative

75

 

 

 

 

 

 

 

 

mass estimate error(kg) error(%)
45.0 49.1 4.1 9.1%
55.0 62.2 7.2 13.1%
30.0 26.8 3.2 10.7%

 

 

Table 6.1: The Results of Mass Estimation.

 

 

 

 

 

 

 

 

 

 

2 I I I I I
2 1.5 r-
(U
.E
‘65
[U 1 1-
E
‘6:
C
3
0.5 ~
0 L l l l l
0 5 10 15 20 25 30
Time
1 I T I I
0.8 ~ * ~
0.6 e -
a.
0.4 ~ ~ - . 1
0.2 ~ , J
o i 1 I 1
0 10 15 20 25 30
Time

Figure 6.6: The length estimate and variance P at 9th levels for L=1.31m.

estimation error, and the value of e.

Fig. 6.6, Fig. 6.7, Fig. 6.8, Fig. 6.9,Fig. 6.10, Fig. 6.11,Fig. 6.12, and Fig. 6.13
shows the estimation processes at 9th-12 levels for L=1.31m. The tends of variance
P at all the levels show that the estimations of the recursive least square method
is convergent. The figure at 10th level indicates a smooth curve of the estimation,
which results in the best estimate.

Fig. 6.14, 6.15 and 6.16 indicate that the estimation reaches the minimum léilil =
10.5%, 7.9% and 2.6% at level 11, 10 and 10, respectively. The figures also show
that after the estimation level at which the estimation error takes a minimum value,

the value of e' and the estimation errors are increasing, due to lacking of the high

76

 

Length Estimate
I

0.5-

 

 

 

 

0 5 10 15 20 25 30
Time

 

 

 

 

 

I I I I
0.8*- s
0.6i- - L
O.
0.4» -* J
0.2’-- ~
0 :7 l l l
0 5 10 15 20 25 30

Time

Figure 6.7: The length estimate and variance P at 10th levels for L=1.31m.

 

Length Estimate
_. in
T I

.0
0'!
I

 

 

 

 

0.8- ..

0.6 r

0.4-

o.2~~~

 

 

 

 

 

Figure 6.8: The length estimate and variance P at 11th levels for L=1.31m.

77

 

Length Estimate
_. bx
T I

.o
01
r

 

 

 

 

 

o.6~

 

0.4 r

 

 

o L L I l I
0 5 10 15 2O 25 30
Time

 

Figure 6.9: The length estimate and variance P at 12th levels for L=1.31m.

Length Estimate(m)

 

o 5 1o 15 20 25 30
Time (s)

Figure 6.10: The length estimate and variance P at 9th levels for L=0.93m.

78

Length Estimation (m)

Figure 6.11: The length estimate and variance P at 10th levels for L=0.93m.

Length Estimate(m)

Figure 6.12: The length estimate and variance P at 11th levels for L=0.93m.

d

 

 

.0
(D

 

.0
co

 

.0
\l

 

.0
O)

 

.0
at

 

.0
a

 

9
w

.0
to

 

 

.0
.5

 

 

 

 

 

 

 

 

O
0

L4

12

0.8 '

06

Q4

02

10

1s
Time(s)

20

25

30

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

/\/\ Avq (”a
,/
\fl—e
5 10 15 20 25
Time(s)

79

30

Length Estimate (m)
e to .w .e
-b 01 M 01 U 01 b 0'1 01

.0
tn

 

O

o 5 1o 15 20 25 30
Time(s)

Figure 6.13: The length estimate and variance P at 12th levels for L=0.93m.

 

 

 

 

 

 

 

 

 

Length LS WBMI
(m) L(m) error L(m) error
0.93 0.0290 -96% 1.0278 10.5%
1.14 0.1280 —89.3% 1.061 -7.0%
1.31 0.1213 -90.0% 1.415 7.9%
1.46 0.1577 -89% 1.50 2.6%

 

 

 

 

Table 6.2: Comparison of the Length Estimation Results.

frequency components of the true signal ( serious distortion )at the further levels of
low pass filtering.

The results from using the proposed method and traditional RLSM are compared
in Table 6.2.

To estimate the kinematic length of a cart, the estimates by WBMI Algorithm,
according to the proposed method, and the estimates by traditional LSM without

preprocessing the raw data are used in model identification.

80

 

 

 

 

 

 

 

 

§ 2. 11 -
011.5- .
C
.9
1g 11% is it it it it 1: s * ‘
fi0.5' * 11 I
(D it
o M l L I 1 * l
0 2 4 6 8 10 12 14
_, level
10X10 1 I I I 1 I
11 11:
as 11 11 at 11 11 11 t
8- * -
(D
6" 11 .
¥
1
4 l l l l I I
0 2 4 6 8 10 12 14

level

Figure 6.14: The results of e and |%| for L=0.93m.

6.3 Experimental Results for Hybrid Linguistic Control in

Perceptive Frame

The proposed perceptive control model has been tested using a Mobile Manipulator-
Phantom Joystick tele-operation System consisting of a Nomadic XR4000 mobile
robot, a puma560 robot arm mounted on the mobile robot and a phantom joystick
controller. as shown in Fig. 6.20. There are two PCs on the mobile platform for the
control of the mobile robot and the Puma, respectively. Another PC is driving the

Phantom joystick and communicating with the Puma controller through the Internet.

81

 

 

 

 

 

 

 

 

5
$1.5 * 4
C
21.9- 11? 11 at at 11 l
m f I 11 11 11
E
'5 0.5- * 1
G)
0 l l l_ l T * l
0 2 4 6 8 10 12 14
level
0.025 I I I I I l
{-
1t 11 11 it 1* 1‘ I
11
0.02- .
G) l 11 I f
0.015’ 1
0.01 l l l l T L
0 2 4 6 8 10 12 14
level

Figure 6.15: The results of e and |%| for L=1.31m.

The first task is designed as picking up an object followed by transporting it to
a destination autonomously, i.e., without tele—operation. An unexpected obstacle
blocks the mobile robot and prevents the continuous reference from evolving while
the robot is executing the transporting task. In this implementation, environmental
information is involved in the reference processing. The experimental results show
that the proposed model is able to keep the perceptive reference evolving and trigger
multiple events.

The experimental implementation is planned as a phase triggering multiple ac-

tions, a phase executing task, a phase modifying plan and a phase resuming task as

82

 

1.5 I I I I I I

 

 

 

 

 

 

 

11
r
If) 1i 1
C a t i 4 t i 1*
.9 1
1'6
1*
g 0.5- , .1 ~
(I)
0 111
0 1 1 1 1 i 1
0 2 4 6 8 10 12 14
level
0.016 I T j I ' ‘ 111
0.0141: 111 111 111 11 111 ,, * * ‘
0.0127 * .1
0)
0.01- -
0.008- * , -
111
0.006 I l l l l I
0 2 4 6 8 10 12 14
level

Figure 6.16: The results of e and l%| for L=1.46m.

mentioned in section 4.3.

As mentioned in the example, the experimental implementation is planned as a
combined process including a phase triggering multiple actions, a phase executing
task, a phase modifying plan and a phase resuming task.

Figure 7.11 shows the trajectory of the expirement result. The movement started
from P0(0.0, 0.0) and went straight to point P1(710.0,705.0), then picked up an
object at this point. In the way of transporting the object to P4(712.0, 2685.0), it
modified the designed trajectory and made an obstacle avoidance at P2(703.0, 865.0),

from there, it went through a segment of an arc with a length of 7r. From point

83

 

  
  

3000 . , , , T
2500- ..
E : i ;
£1500t“““ .. o .. _ .. . . .. _, _ -
>' 1 obstacle
1000~' _
500~' '“1

 

 

 

0 500 1000 1500 2000 2500 3000
X(mm)

Figure 6.17: The moving trajectory in the experiment.

P3(714.0, 2076) resumed the previously designed trajectory.

As designed, the action reference has triggered multiple events including next
moving path segment and the end-effector actions at the point P1 and the point
P4, the actions “close the gripper” at P1 and “open the gripper” at P4 are shown in
Figure 6.19.

The second task is designed on a Phantom Joystick-Puma560 arm joint tele-
operation to show unexpected event processing at the action level. As shown in
Figure6.20, a phantom joystick is used to control a Puma'560 robot arm through the
Internet. Phantom controller can measure and send out the position of the joystick

in the phantom work space with a fixed rate of 10 Hz. The Puma arm controller

84

 

 

 

 

 

 

 

 

 

 

 

4 1 1 1 1 1
0
‘c’
s 3 " 1
0
'2
t2- .— .
>
0
0
2
.‘s’ 1 ‘
U
0 l l I I l
0 10 20 30 40 50 60
4000 n 1 1 1 1
0 . . . .
o
5
33 3000 _ ............. . -1
9
E
g 2000 .. ................................................................................. .1
til
3
O
3
g 1000 _ .......................................................... -
c
O
0
0 1 1 1
0 10 20 30 40 50 60
time

Figure 6.18: The moving reference in the experiment.

receives the information as motion commands and maps it to the puma arm work
space. The control frequency of the arm controller is 500Hz. Therefore, the arm
runs 50 control cycles for one phantom command. The task is to implement position
tracking from Phantom space to Puma arm space in real-time. This experiment is
designed for processing the expected events caused by the time delay of the Internet
communication between the joystick and controller. If the phantom controller cannot
receive the next position command within 50 cycles of the current command, it is an
unexpected event which can block the discrete perceptive reference.

Figures 6.21 6.22 6.23 show the Phantom-Puma position tracking control result on

85

 

Figure 6.19: The actions triggered by the action level reference.

 

Figure 6.20: The phantom joystick tele-operation.

z axis. Fig A illustrates the trajectory from phantom position data. Fig.0 shows that
the Puma position tracking is smooth with unexpected event processing. As shown in
D, it can be found that the unexpected events (delayed commands) occurred during
the task execution. Corresponding to Fig D, Fig. B shows that the velocity control
signal is continuously evolving, i.e., the proposed hybrid reference cannot be blocked
at the occurrence of the unexpected events that may block the evolution of the single

discrete perceptive reference.

86

 

 

§
01

 

 

 

 

 

Phantom pos
8
Dessred Velo

 

 

c:
I
(’1

 

 

é
N

 

 

 

 

Puma Pos
8
delayed events

 

 

C)
o

C lime(s) D time(s)

Figure 6.21: Unexpected Events in Phantom Manipulation along x—axis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.100 5
m 2
3 9
550 .............. . ............................ 1!;
c I .-
16 j m
i 2 8
0 L -5
0 l A 2 3 0 l B 2 3
100 “2 Y
' ‘c' j
i i 3 é
“0 ~ i .
0 1 2 3
C lime(s) 0 time(s)

Figure 6.22: Unexpected Events in Phantom Manipulation along y-axis

87

 

 

so 1 a: 5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1‘1 2
‘1 §
5 1
i
11 o
-5
0 1 B 2 3
.032 : :
13 § 3 3
0- o : t
E l; :
'00 7 . ,,L
o 1 2 3
C 1116(8) D timels)

Figure 6.23: Unexpected Events in Phantom Manipulation along z-axis

88

CHAPTER 7
PERCEPTIVE CONTROL SYSTEM DESIGN AND VLSI
IMPLEMENTATION

Nowadays, real-time (or embedded) systems [12] have been attracting people’s atten-
tion. Roughly speaking, a real-time system is required to react to stimuli from the
environment (including the passage of physical time) within time intervals dictated
by the environment. In other words, real-time systems must respond to real-world
events. Naturally, this class of systems can be implemented in the perceptive frame.

The perceptive frame control method is aimed to solve the problems in Real-
Time Control System design. In this chapter, a real-time programming language is
proposed for designing real-time control systems. Two important mechanisms, event

triggering and sampling are discussed in this chapter.

7 .1 Real-time System in Perceptive Frame

7.1.1 Input-Reference-Output Mapping in the Perceptive Frame

The task description space can be formulated as U = {TTRiTA R,- Itk}i j k, a combination
of segment in the task space. Real-time control requires the system to respond to the
events from sensor measurements, whenever they happen. Thus, events are possible
at any point on the time axis.

The system can be thought of as a mapping: U x E —> Output, where the Output
is the set of real-time related actions, including event triggering and sampling.

As studied above, every hybrid perceptive reference trajectory {STRiSARJ-Iskhjk
is an ordered set with an order “j”. The trajectory is a combination of the ordered
closed intervals. Every hybrid perceptive reference trajectory can be mapped onto a

time interval linearly. This provides the feasibility of performing real-time operations

89

in the perceptive frame, i.e., based on the hybrid perceptive references.

7.1.2 Perceptive Reference Based Language Description Regarding

Real- Time Control System Design

To a large extent, there exist a variety of tasks and actions in real-time control
systems. The objective of the system design is to implement the tasks and the actions
in the perceptive frame with the architecture shown in Figure 4.2.

In order to solve the design problems efficiently, a real-time language is desirable to
describe the relation between the commands (high level and low level), the perceptive
references and the real-time related outputs. The introduction of the perceptive
references into the language enables the system to deal with both the continuous and

the discrete events.

7.1.3 Finite Automata Approach for Input-Reference-Cutput
Mapping
Automaton is a mathematical model to depict the logic behaviors of a system. In
the perceptive frame, the tasks and actions are required to be executed sequentially.
Hence all the discrete transitions can be modeled by finite automata. The task

information can be decomposed into different lower levels to be expressed based on

its semantic description.

0’: = 77((11101,X) (7-2)

90

7 .2 VLSI Implementation-Oriented Controller Design

7. 2.1 Abstractions of real-time perceptive controller

The control implementation can be represented at the different levels of abstraction:
entity abstraction, procedure abstraction, and hierarchy abstraction.

Abstraction of the controller entity

In the perceptive frame, the hybrid control systems are the combinations of control
primitives. Each control primitive can be treated as a control entity. A control entity
is a controller that can execute a control command at certain level. The control
entity has the specifications to describe the inputs, the outputs, and life time of the
entity. The lifetime of the entity in the perceptive frame is a segment of the perceptive
reference, it marked the starting point and the end point for the entity to be activated.
In the implementation, a task can be composed of several entities at lower level.

In the system shown in Figure 4.2, a control entity can be a controller for executing

f1

...... AulAnZ-nAn}

a task consisting of action entities.

f1 21

A11 Ann-A1111 A21 Ann-Azp

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 7.1: Abstract of the structure.

The control entity can be described as an object in pseudo-code.

Entity {
inputs,
outputs,
active period in perceptive frame,
entities at lower levels,

}

91

Abstraction of the logic control structure: 1. Sequential Structure.
The operations of the automata can show the logic control structure of the automata.
For a typical perceptive automaton, The transition function is a branch control struc-

ture in sense of logic.

Qj = 6(Qi10j)a5j E 2 (7.3)

The perceptive referenced output function has loop structure.

01: = 771611301) (74)

The figure 7.2 indicates the logic structure of an automaton, the basic sequen-
tial logic structures in the implementation are branches and loops, i.e., the selective
structure and the repetitive structure.

2. Parallel Structure.

Figure 4.2 shows that the reference generation and the task execution are working
concurrently. Furthermore, the automaton have multiple actions triggered by the
task, for example one task can trigger the actions performed by the mobile robot
and the robot arm at the same time. There are more than one process running in a
processor.

Abstraction of the Functional Hierarchy:

The Figure 4.2, it can be seen that the task scheduler, the action planning and
the motion planner are sequentially chained together. The input of one automaton is
output of the higher level automaton. Hierarchy.

In order to implement the design, the above abstractions discovered the structure
of the system in three aspects, i.e., the controller entities, the functional structure,

and the control structure. The design procedure is shown in Figure 7.3

92

 

HIGH LEVEL
AUTOMATA

 

 

 

 

    

Yes:
State transition

   
        
   
 

Yes:
State transition

  

Active in
Perceptive
reference?

 

CONTROLLER
ENTITY
(OUTPUT TO
LOWER LEVEL
AUTOMATA)

l

 

 

 

 

 

 

 

 

Figure 7.2: Structure of the Implementation

Event Triggering

Timing is crucial in any real-time system. It is required to have real-time con-
trol facilities, including specifying times at which actions are to be performed and
completed, and responding to situations where all the timing requirements cannot be
met. The time triggering plays a key role in real-time systems.

The unit step function:

0 t < to
1 t 2 to

is a simple example of time triggering.

93

 

Task Expression

17

Procedure Decomposition

I

Perceptive References
design

I

Branch and Loop
Control Structure Design

I

Procedure Description
in Perceptive Frame

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 7.3: Block Diagram of the Implementation Procedure.

In order to make the real-time system purely independent from time t, in the
perceptive frame, the perceptive reference replaces the time as the system reference.
Thus, the problem of event triggering is generally unavoidable in the real-time sys-
tems.

Sampling System One of the typical problems in real-time systems is sampling
data. Information carried by an analog signal can be represented in a digital form
by a sequence of its instantaneous values measured at discrete time instances. These
signal readings are usually considered as signal sample values and the process of taking
them is referred to as sampling. The instances at which the samples are obtained form
a stream of uniform events, which can be depicted graphically as a sampling point
process. Characteristic features of the sampled signals to a large extent depend on the
patterns of the point processes generated and used for sampling [48]. When sampling
is mentioned in the context of Digital Signal Processing(DSP), usually it is assumed
that the sampling considered is deterministic and periodic. The model of sampling

according to which signal samples are separated by time intervals with a constant

94

and known duration is the most popular one. This is readily comprehensible because
such a sampling approach appears to be the most natural and obvious, as shown in

the following equation

x[n] = xc(nT), —00 < n < 00 (7.6)

Where xC is a continuous-time signal, x[n] is a sequence of samples obtained from xc,
T is the sampling period and its reciprocal is the sampling frequency.

For a control method in the perceptive frame, time t is not used as the common
reference. It is desirable to design a sampling mechanism with the perceptive refer-
ences. Roughly speaking, the sampling in the perceptive frame can be explained as
a process to take a sequence of points of a continuous signal with the marks in the
perceptive references. The sampling period is not characterized by time, but percep-
tive reference. In other words, the density of the sampling on a signal depends on
the environmental sensing. If the sensor information changes rapidly, the signal is

sampled quite frequently. The sequence of the samples can be depicted as

h
n

x[n] = xc(s ), —00 < n < 00 (7.7)

where the sf, represents the instances of the hybrid perceptive reference at which the

samples are obtained.

7. 2.2 Synthesizability of Perceptive Controller

In general, the term ”synthesis” is referred to as the automated transformation of
RT level descriptions into gate level representations, or other more detailed descrip-
tions [70]. This transformation is mainly influenced by the set of basic cells that
are available in the target technology. While simple operations like comparisons and

either / or decisions are easily mapped to Boolean functions, more complex constructs

95

like mathematical operators are mapped to a tool specific macro cell library first, for
example, boolean network or finite state machine.

Functionally, the discrete controllers can be described as finite automata, which
are the devices to accept the strings in a formal language. For a finite automaton,
if we can find a set of Boolean Functions, or a Boolean Network, set Bf connected
to a finite state machine, consisting of flip—flop components, M (Q, I), Q is the state
set of the finite state machine, I is the input language. Then, the finite automaton is
synthesizable, tuple (B f, M (Q, I )) is an implementation of the finite automaton.

Theorem : Given that a finite automaton is synthesizable, there exists a tuple
(Bf, M (Q, 1)), which is an implementation of the finite automaton. Based on the
discrete transition of the finite automaton,

(1)Perceptive automaton is synthesizable.

(2)Hybrid automaton is synthesizable.

(3)Furthermore, the multiple automata system, shown in Figure 4.2, i.e., connected
by task/action description language and reference language, is synthesizable.

Proof:

(1)The perceptive automaton has two linguistic inputs, namely the task inputs formed
from E and the reference input formed from 23. The reference inputs change the
linguistic output 0, 0,, = g(qi, 0],), which can be described by Boolean logic equa-
tions. Comparing to the implementation (B f, M (Q, I )) for the fundamental finite
automaton, the Boolean function B f of perceptive automaton depends also on the
reference input I R, The B f(I R) is the Boolean function set for the new automaton.
(B,(IR), M (Q, 1)) is an implementation for the perceptive automaton. Me, therefore,
is synthesizable.

(2)The state transition function g, = 5((11,0j,X ),6j E E and the output function
0;, = g(qi, 0,, X) show the new features of the hybrid automaton. Hybrid automa-

ton has continuous variables, in digital systems, the variables can be discretized and

96

represented by fixed point number, or, for the sake of simplification, by integers N.
Those discretized variables are the operands for specific arithmetic Operation, i.e.,
for specific discrete state qi. In hybrid automaton, arithmetic operations can be per-
formed by Boolean logic operation added to the Boolean implementation B fh. Hence,
(th, M (Q, 1)) is an implementation of the hybrid automaton. The automaton is syn-
thesizable.

(3)The integrated system shown in figure 4.2 is a set of connected automata, which
are perceptive automata, or hybrid automata or both. According to the first and the
second items of the theorem, each automaton is synthesizable, i.e., each automaton
has a tuple (B f1, M,), i = 1...n as its implementation. The input and the output of the
single automaton can be treated as strings in the formal languages with discretized
valuables, they can be encoded with limited number of bits and expressed by Boolean
functions.

(a) For two automata connected by perceptive reference language L R. Automaton
1 has the output as automaton 2’s reference input. The implementations (Bf1,M1)
and (B ,2, M2) exist for two automata, respectively. The input L R effect only the logic
operation, no state transition. In order to involve the implementation of 1 to 2, we
substitute the tuple (B ,1, M 1) into 2, the implementation for combined automaton
is (312(3111M1))1M2)-

(b) For two automata connected by task language input LT. The automaton 1 has
the output as automaton 2’s task input. The task input effect only on the state
transition. Therefore, the implementation for 1 and 2 is (sz, M 2(Bf1,M1)). The
combined system is synthesizable.

For the sake of induction, it can be assumed that for N automata connected by the task
and reference inputs are synthesizable. Then an implementation tuple (B f“, Mn) can
be found. When we have N + 1th automaton, which is synthesized as (Bfn+1,Mn+1),

under the task inputs and the reference inputs, similar to (a) and (b), there exists an

97

implementation (Bf, M). The integrated system is synthesizableA

7 .3 Hardware-Software Co-design and Hybrid Simulation

7.3.1 Hardware-Software Co-design in Perceptive Frame

Hardware-Software Co-design has been attractive topic in realtime system design.
The hardware is the key part of the embedded system that can improve the real time
processing performance, the software can provide more flexible characteristics of the
high level task description. The perceptive frame makes the system more flexible
on software/ hardware design, because of its modularized architecture. Consider in
task execution, the system can have different partitioning as shown in figure 7.4. We
can build micro—instructions based one different partitions, the micro instructions are
implemented by hardware, and based on which, the software can be programed with

these instructions to utilize the hardware resource at the best.

Implementation Oriented Language(IOL)

The abstractions above show that the implementation of the real-time control system
can have a procedural description, a functional description, and an implementation-
oriented description. Based on the specific semantics, the programming language can
de designed with syntax. A convenient way to convert the system design to implemen-
tation is mapping the design to a hardware design language, for example, VHDL. In
Chapter 4, we have introduced the hybrid formal languages in the perceptive frame,
including Lg, Lg, L51”, and Ufa. The languages describe the tasks, the actions, the
task level reference, and the action level reference. A programming language can be
built based on the description languages.

RTL languages are widely used to express complex digital systems concepts. For

hybrid model in the perceptive frame, Figure 7.3 give the procedure for system design.

98

Commands

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Task Level
Reference TaSk SCthUler
Software
(1 Partitioning 1
Action Level , Har ware
Reference Action Planner
Software
Partitioning 2
1 Hardware
M060" 3 Motion Planner
Reference Software
Partitioning 3
Hardware
Controller
Plant
‘ Configuration Sensor
Environmental Sensor

 

 

 

 

 

Figure 7.4: Partitionings for Hardware/ Software Codesign.

Following this procedure, one can obtain the linguistic expression based on languages
Lh, Lg, Ufa, and Lies to desctibe the Register 'Itansfer Level Objects in perceptive
frame. The words in these languages are used to express the system behaviors. A
sequence of tasks and actions can be expressed by the IOL,
T1(Slea STlf){All(SAllbs SAiif); A12(SA12ba SA12f)};
T209791), ST2f){A21 (3.42112, SA21f---)};---

where T1 and T2 are the elements and control entities in L’f, A11A12... are in
included in language L'j. The perceptive reference values, which follow the task and

action words, denote the active period for the specific entity in perceptive frame.

99

The semicolon indicates the sequential process, the parallel processing is expressed
by the perceptive references. In the above expression, (Sle,ST1f) is defined as the
active period for entity T1, in other words, task T1 is started and ended by perceptive
reference values ST“, and ST”, respectively. The structure of the expression can
easily transfer the control system architecture into the general description language
with modularized description, such as Verilog.

The syntax can be described by the following parse trees for operator , and

operator ” (, )”, respectively.

Expression

Exprossio . Exprmlon
Expression 0
Expression I

Identifier Expression Expression

Expression Expression

Figure 7 .5: Parse Trees for Implementation Oriented Language.

Based on the parse trees, the high level behavior of the entire integrated automata
can be constructed by the syntax. The semantics of the perceptive controllers can be

performed by the Implementation Oriented Language.

100

An Example on IOL Programming

VHDL is a language used to express complex digital systems concepts. Figure 7.3
give the procedure for system design. Following this procedure, one can obtain the
linguistic expression based on languages L55, L53, L’fiT, and L2“. The words in these
languages are used to express the system behaviors. A sequence of tasks and actions
can be expressed by the IOL (language),

T1(ST15,ST1f){A11(SA11b, SAiif)A12(SA12b, SA12f)}

T2(5T2b, ST2f){A21(SA21b18A21f)}1

where T1 and T2 are the elements in L3, A11A12... are in included in language L}.
The perceptive reference values, which follow the task and action words, denote the
active period for the specific entity in perceptive frame. For example, (Sle,ST1f) is
defined as the active period for entity T1, in other words, task T1 is started and ended
by perceptive reference values 8le and 3T1}, respectively.

VHDL is a language used to describe complex digital systems. In order to associate
the IOL perceptive language with the hardware implementation, it is clear that we
need to build a map from the IOL perceptive language to VHDL.

The program involves the synchronization mechanism and hierarchical structure of
the entities. First, the tasks T1 and T2 are executed sequentially, while the actions may
be executed in parallel. In this case, the actions are synchronized by the perceptive
reference. Second, the actions are included in tasks, which belong to higher category
of entity. Based on the abstraction of the controller entity, the entity in IOL consists
of the inputs, outputs, active period for the entity as a feature, and other entities.

The sequential structure is:

P1: process:
Begin

T1 ,

T2.
End process;

101

Considering the perceptive referenced system, the signal mechanism in VHDL
provide the synchronization, the perceptive reference can be expressed as a trigger.

Thus, The controller entity can be described as:

Architecture T] of Task is:
signal TRIGER: perceptive reference

Begin
process
wait on TRIGGER;
Al 1,
A12,
end process;
end T1;

The TRIGGER is the perceptive reference.
In addition to the task entitis and action entities, as the lowest level entity, the low
level controller can be programmed in VHDL by its mathematic description. Usually,

it is included in a library as a module.

7. 3. 2 Hybrid Simulation

The proposed controller design method has been tested using Verilog HDL and Ca-
dence Design System. The functions of the controller can be performed by a Verilog
HDL program, which is semantically equivalent to the hybrid perceptive model. Ca-
dence design system is used to synthesize the Verilog program and simulate the given
example. The simulation system consists of a controller simulator, a simulator for
the continuous dynamics of the plant and a perceptive reference simulator. In order
to simulate the hybrid properties of the system, TestBuilder, a C++ testbench class
library, is used in the simulation system. By using Test Builder, the plant dynam-

ics, consisting of Ordinary Differential Equations(ODE), can be simulated by a C++

102

 

 

Task Command

<:

 

Hybrid

 

 

 

 

 

 

Perceptive Controller
>> Simulation
Reference Perceptive Module
reference -_
Generation 4 »

 

 

 

Sensor Test Bench

measurements (Plant,

K Dynamics
Simulation)

 

 

 

 

 

 

 

 

Figure 7.6: The Scheme of the Hybrid Simulation System.

program. As a testbench, the dynamics in C++ can communicate with HDL simu-
lator in Cadence. Based on the velocity and position commands from the controller,
the dynamics can give out the states of the system, including position, velocity, and
sensor measurements. The modules are implemented independently from each other,

they are connected only with the linguistic commands and the perceptive references.

Implementation of Arithmetic Operations

For a controllers, most frequently used operations are arithmetic operations. To
reduce the scale of the circuit, we use fixed-point number representation for imple-
mentation the control algorithm. For a signed real number, the integer part is 11-bit
long, the decimal part is 12-bit long. The arithmetic unit provided by Verilog is
implementated with unsigned division and signed multiplication.

To keep the accuracy of division and multiplication in the controller, a new arith-

metic unit is deve10ped, as shown in Figure 7.7, the division and the multiplication

103

can be done by Verilog with the desired accuracy.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A, B, C
sign 11 bits 12 bits
X3 don’t care I— Integer part Decimal part
For A/B=C 7
sign(wl)
A1: I original code of A I O. ...O
sign(w2)
Bl=I 0.... ...0 original codeofB
w3=wl 6 w2 (sign of C)
Cl=Al/Bl = I x.... ...x original code ofC
For A*B =C
si n(wl) .
A1: wl . . . .wl 2’s complementary code ofA I
sign(w2)
Bl: I w2. . ..w2 2’s complementary code ofB I
w3=wl GD w2 (sign or C)
c1=A1=~Br= 2's complementary code of C x.... . ..x

 

 

 

 

 

Figure 7.7: Arithmetic Operations.

Dynamics Model in Testbuilder

The dynamics model in Testbuilder is an ODE model. In perceptive frame, a mobile

robot model can be described as:

dw

_ = .8

ds 2a (7 )
da

For a robot arm, dynamics model is given by

D(Q)<'1' + C(q, d) + G(€1)+ Jflqm = T (710)

104

7. 3.3 Simulation results

The first task of the simulation is to generate the control signal for the robotic system
to go through a desired path with two straight lines. The robot travels toward the
wall, before reaching the wall, the robot turns and travels along the wall to go to the
destination. In the perceptive frame, the action A1 and A3 action command will be
triggered by the perceptive reference. The robot will move along X direction for 3
units, then travel along Y direction for 4 units.

As described below, the task, denoted as T 1(3, 4), means move to point(3,4).
Assuming the current position is (0,0), the task can be decomposed as two actions,
namely, A1, which means traveling from current position to (3,0), and action A2 for
moving from (3,0) to (3,4). The perceptive references will be the signals to indicate
the distance the robot traveled and to trigger the next action, while the current action
is finished.

For a typical perceptive hybrid automaton, the action planner has two inputs, the
command input and the reference input, and an output. Figure 7.8 illustrates the
schematic description synthesized by Cadence Design System. The command inputs
are Task, Task; and Tasky, the reference input is ActionRe f . F is the output to the
motion planner as its command input. Therefore, the perceptive/ hybrid automaton
is synthesizable. Figure 7.9 illustrates the implementation of Action Reference in the
given case. According to (4.22),(4.23), the wall signal is generated from the sensor
measurements. The wall signal indicades that the wall is detected and can make the
action reference to switch from 1 to 2. The low level controller is a digital circuit
to perform the low level control algorithm, it is the interface between the continuous
dynamics and the higher level discrete planners.

The integrated automata model shown in Figure 4.2 have been tested using Ca-
dence. As proved before, the entire system is synthesizable. Based on the synthesized

description, the simulation has been performed. Figure 7.10 is the signal wave form of

105

 

Figure 7.8: Schematic Description of Action Planner.

the simulation, it shows the changes of the task reference, the task input, the action
reference and the action input and the motion reference. The system performs only
one task. The task is to move the robot to destination point (3,4). From Figure 7.10,
we can see that the perceptive references triggered the system at point(3,0), when the
robot traveled along X direction for 3, i.e. at the moment 33, the wall signal becomes

1, the action reference and command switch from 1 to 2, the second action command

106

 

 

 

 

 

 

 

 

 

Task

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 7.9: Schematic Description of Action Reference.

is issued, which means the motion on Y direction, along the wall, the action command
and its parameters will be held for the entire period of the action execution, until the
task has been executed.

The second task is to show the hybrid properties of the perceptive controller, we
use the motion planner to compute the trajectory through the arithmetic operations.

Instead of two segments of straight line, the first segment is a circular path which is

107

 

 

 

 

 

 

 

 

Group:
TaskRef[l:0] = ’h
Task[1:0] = 'h
Taskx[3:0] = ’h
Tasky[3:0] = ’h

 

 

ActionRef[2:0] = ’h

 

 

Action[l:0] = ’h

 

 

ActionD[3:0] = ’h

 

MotionRef[3:0] = ’h

 

 

 

 

 

 

 

Vx[1:0] = 'h
Vy[1:0] = 'h
wall[1:01 = 'h

 

Figure 7.10: Simulation results.

 

implemented by the designed arithmetic unit. In perceptive frame the path planning

algorithm can be described as a circular path:

a: = rcos(s/r)
y = rsz'n(s/r)
. __ y
x — —;V(s)

y=§V®>

(7.11)
(7.12)
(7.13)

(7.14)

Where 7' is the radius of the circular path, 3 is the continuous motion reference. Figure

7.11 shows the trajectory in the simulation, and the continuous motion reference w.r.t.

time, which is computed by the continuous dynamics model and the motion reference

block.

108

 

 

V(m)
—¢ co
references
N s» .A
0‘ ‘t’ ‘f‘ ’r “9 0‘
.J

N

 

o
r
d
-» in
T

9
01
r

 

 

 

 

 

I
l
l

J

 

 

-1 0 1 2

A
(1'!
O)
o
M

5 4
X (m) Time(s)
(a) (b)

Figure 7.11: The Motion Trajectory in the Experiment: (a) x-y plot (b)continuous reference
w.r.t time.

For a robot arm, dynamics model is given by

D(q)d + C(q, d) + G((1)+ Jflqlfe = 7 (7-15)

Using the above model as the continuous model of the robot, one can build a
second order control hybrid simulation. The D, H, C can be calculated in hardware
part for generating the computed torques T. The following is the hybrid simulation
results based the second order robotic control simulation model. The figures indicate
the step response for the individual joints. Puma 560 first 3-joint model is used for
the simulation in Test Builder. The control signal is to move the joint for 2 degrees.

Figures 7.12, 7.13, and 7.14 show the step response of joint level control as a
second order control system. It can be seen that joint 1, 2, 3 can track the step signal
accurately. The VLSI design can satisfies the real time requirements under the given
PD control gains.

Figures 7.15, and 7.16, and 7.17 show the joint level control of joint 1, 2, and 3

109

 

joint 1 position

 

 

joint 1 velocity

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.5' l
0o ols 1 1.5 2 2.5 ‘A'o ‘5 1 1 :5 2 2.5
Time(s) Time(s)
(a) (b)
Figure 7.12: Joint Level Control — Step Response: (a) position (b) velocity
10-
2.5»
8‘ I
c 2»
a a? e~
171 2
o m
0.1.5 > 4
(\l N
‘E E
:c: 1. Si 2
0.
0.5»
-2.
0o W 1 175 2 2.5 J'o o 1 1:5 2 2.5
Time(s) Time(S)
(c) (d)
Figure 7.13: Joint Level Control — Step Response: (c) position ((1) velocity

with 14 bits long decimal part. The figures indicate that the system does not have

significant improvement in stability and tracking accuracy.

Figures 7.18, and 7.19, 7.20 and 7.21 indicate the step response of the joint level

control of joint 2 with 8 bits long decimal part. The figures show that the system still

110

 

 

 

 

 

 

 

 

 

 

 

2..
c 2‘
.9 ._
35 15* .8
o o
o. >
an m
E 1 g
.2 .2
0.5"
o l l l l -2 J L 1
0 0.5 1 1.5 2 2.5 0 0.5 1 1.5 2 2.5
Time(s) Time(s)
(e) (0
Figure 7.14: Joint Level Control — Step Response: (e) position (f) velocity
7 I I r T 40 r r r r

-42 a

+ 44

0 .
S :1
e e
OI! CI!

1- N-46L
.Ԥ 1 3;:
O O
7 7

   

 

 

 

 

 

’3 5 2 2.5 '520 0.5 1 1 5 2 2.5

1 Time(s)L Time(s) '
(g) (11)

Figure 7.15: Joint Level Force Control Signal at Step Response: (g) Joint 1 (h) Joint 2

 

compare to the results with 24 bits long arithmetic units, the accuracy of the track-
ing control is significantly decreased because of the limited length of the arithmetic
operation. In this case, the control force has jumps and discountinuities, and the

velocity on this joint is not smooth. Thus, it can be seen that 24-bit arithmetic unit

111

2.5 -

joint 1 position
0'!

0.5 ~

 

Joint 3 torque

 

-2

 

L l

 

 

1 1.5 2
Time(s)

2.5

Figure 7.16: Joint Level Force Control Signal at Step Response: Joint 3 .

 

 

l l

— .

 

10 1

joint 1 velocity

o
v

 

 

 

0.5

Figure 7.17: Joint Level Control Step Response: (a) position (b) velocity

1 1.
Time(s)

(a)

5

l

1

 

.-

 

 

2.5 0 0.5

1 Time(s)

(b)

1.5

2.5

can provide good performance in tracking accuracy, and the time requirement can be

satisfied.

112

2.5

joint 2 position
0!

0.5 -

 

 

 

joint 2 velocity

 

 

 

p

 

2.5

joint 3 position

.0
01

J 1 1 L 2 l I
-

 

 

 

‘
U!

 

 

 

 

 

 

 

 

0.5 1 1.5 2 2.5 o 0.5 1 1.5 2.5
Time(s) TI"19(3)
(C) (d)
Figure 7.18: Joint Level Control Step Response: (c) position (d) velocity
1 7 1 r 14 r I I T
.E‘
.8.
o
>
m
.E
.9.
1
l 1 1 4 -2 _L 1 J
0.5 1 1.5 2 2.5 o 1 1.5 2.5
“mun nmfl$
(e) (f)

Figure 7.19: Joint Level Force Control Step Response: (e) position (f) velocity

113

 

Torque 1

 

 

.3 l l l

 

Torque 2

 

 

 

 

1 1.5 2
Time(s)

(g)

 

 

1.5 2 2.5
Time(s)

(h)

Figure 7.20: Joint Level Control at Step Response: (g) Position of Joint 2 (h) Velocity of

Joint 2

 

Torque 3

 

 

.—

 

 

1

1 5 2 2.5

Time(s) '

Figure 7.21: Joint Level Control Signal at Step Response (i) : Joint 2 .

114

CHAPTER 8
CONCLUSIONS AND FUTURE WORK

8. 1 Conclusions

This dissertation describes the Design and VLSI implementation of Perceptive Con-
troller for Robotic Systems. The research covers task model learning, hybrid control
system modeling, analyzing, and designing. The proposed method is an efficient ap-
proach to explore hybrid systems. The main contributions of this dissertation are as
follows:

Task Modeling in Perceptive flame:

A Wavelet Based Model Identification Method has been introduced. The experi-
mental results show the effectiveness of the proposed method for identifying the mass
and the length of a nonholonomic cart by interactive action in cart pushing, when
the unknown noises generated by sensor measurements and numerical operations are
uncorrelated.

The significance of the task modeling method is that the method offers significant
advantages over the classical least square estimation methods. In model identifica-
tion for online estimation without prior statistical knowledge of measurement and
operation noises. Many applications, including home care, search, rescue, require the
mobile manipulator working in unstructured environments. Based on the method
proposed in this dissertation, the task parameters can be estimated by simple inter-
active actions between the mobile manipulator and the environment. It improves the
effectiveness of the operation significantly.

Linguistic Control Approach:

A hybrid model for the perceptive reference based robotic plan and control systems
has been proposed. The model integrates the continuous perceptive reference and

discrete references through a hybrid approach and offers significant advantages over

115

classical time based schedule-plan—control models. Based on the properties of the
proposed model, some properties of the system, including evolution of the perceptive
reference, and stability are discussed.

The hybrid model makes the system become more intelligent and flexible in the
processing of environmental sensory measurements for planning and control. The
experimental results show the effectiveness of the proposed model for processing un-
expected event, These results are significant in the modification of the designed plan
and the mechanism which triggers multiple discrete events. The intelligence of the
system has been enhanced.

Perceptive Control System Design:

In order to implement real-time systems in the perceptive frame, an implementation-
oriented design method has been introduced for robot controllers. Considering the
hybrid system model in perceptive frame, the functional abstraction of the model has
been analyzed. The high level architecture of the model makes the controller mod-
ularized, therefore, synthesizability can be guaranteed. An implementation oriented
controller design method is proposed for describing the system model. The automa-
ton based description of the robotic control system can be performed by the code
in Verilog, which is semantically equivalent to the controller model. The significant
impact is that the implementation-oriented design language provides a convenient
way for designing a real-time system. The language is used to convert the control
system design to hardware implementation via semantics description of the tasks.
The perceptive frame control can be applied to other applications in real time control
area such as motion control systems. The Verilog code has been tested by Candence
design system to be synthesized to a structural description and simulated in a hybrid
fashion. The simulation results show that based on the hybrid control model in per-
ceptive frame, the implementation oriented design method can translated the high

level description to low level VLSI implementation.

116

8.2 Suggestions for Future Research

The research work in the dissertation has only opened the door little wider to future
research investigation. In the future, there will be some areas of the analysis and

design where future research would be very beneficial. Some suggestions are as follows:

0 Model Learning: The Wavelet based online model learning method can be
extended to multiple parameter identification for more complex model learning.
Theoretical analysis will be an important argument to show the estimation
convergence in subbanding the raw signal. Also, Kalman filter can be applied

to state estimation with nonholonomic constraints.

0 System Modeling and Analysis: This dissertation presents a framework for
investigation of hybrid system in perceptive frame. In this frame work, some
theoretical analysis and design problems will be very beneficial. Context Free-
type and recursive enumerable grammars can be used in the liguistic expressions
at task level and action level, to gain more flexibility and capacity of tast-
action description. The unexpected events, perceptive reference and commands
can compose the homogenuous linguistic expression, some properties, including

non-uniformly sampling, complexity and dynamics can be extensively discussed.

a Real Time System Implementation on a Chip (ASIC): The Cadence /
testbuilder design framework provides an approach for simulating a chip-based
hybrid control system. The future research will be on the silicon implementation
of the real time system. Hence, optimization of algorithm, the sice of arithmetic

units and testing design will be the major topics.

0 Software / Hardware Co-Design: Based one the hybrid system model in per-
ceptive frame, the design and implementation procedures have been unified by

the framework of automata and linguistic descriptions. The software / hardware

117

co—design technique can be developed based on the hybrid perceptive frame-
work. Hardware and software compilation at difference level will be discussed
for task/ action assignment in the sense of real time control with the final goal of
optimizing partition plan obtained by analyzing the resource and performance

of the system.

118

BIBLIOGRAPHY

[1] Mark J.T.Smith “Subband and Wavelet Transforms: Design and Applica-
tions”Kluwer Academic Publishers, 1996.

[2] R. Alur, C. Courcoubetis, and T.A.Henzinger, “Hybrid Automata: An Algorith-
mic Approach to the specification and Verification of Hybrid Systems”, Proceed-
ings of the IEEE Vol.88, NO.7, July 2000.

[3] Panos J. Antsaklis. M. D. Lemmon. “Hybrid Systems Modeling and Autonomous
Control Systems”volume 736 of Lecture Notes in Computer Science,Pages 366-
392, Springer-Verlag, New York, 1993.

[4] Allen Back, John Guckenheimer, and Mark Myers. “A Dynamical simulation
facility for hybrid systems”volume 736 of Lecture Notes in Computer Science,
pages 255-267, Springer-Verlag, New York, 1993.

[5] Michael S. Braniky, “Studies in Hybrid Systems: Modeling, Analysis, and Con-
trol”, Ph.D Thesis of M.I.T. 1995.

[6] Michael S. Braniky, “Multiple Lyapunov Functions and Other Analysis Tools for
Switched and Hybrid Systems”, IEEE Transactions on Automatic Control, Vol
43, No.4,1998,pp.475-482.

[7] Michael S. Braniky, Vivek S. Borkar, and Sanjoy K. Mitter, “A Unified Frame-
work for Hybrid control”, Proceedings of the 33rd Conference on Decision and
Control, pp.4228-4234, Lake Buena Vista, FL—December, 1994.

[8] R. Brockett, “On the Computer Control of Movement” Proceedings of the 1988
IEEE Conference on Robotics and Automation, New York, April 1988, pp. 534-
540.

[9] R. Brockett, “Language Driven Hybrid Systems” Proc. of the 33rd Conference
on Decision and Control,Lake Buena Vista,FL,Dec.1994.

[10] R. W. Brockett. “Hybrid Model for Motion Control Systems.” in Perspectives in
Control. Editors. H. Trantelman and J .C.Willems, pp. 29-54, Birkhauser, Boston,
1993.

[11] R. Brockett, “Formal Languages for Motion Description and Map Making,” in
Robotics, (R.W. Brockett, ed.) American Mathematical Society, Providence, RI,
1990. pp. 181-193.

[12] Alan Burn and Andy Wllings, “Real-Time Systems and Programming Languages
(Third Edition) Ada 95, Real-Time Java and Real-Time POSIX” , Addison Wes-
ley Longmain, March, 2001.

119

[13] John F. Canny, “The Complexity of Robot Motion Planning”. The MIT Press,
1987.

[14] Andrew Choi, “Real-Time Fundamental Frequency Estimation by Least-Square
Fitting”, IEEE Trans. On Speech and Audio Processing, Vol. 5, No. 2, pp201-
pp205, March 1997.

[15] Ingrid Daubechies, “Ten lectures on wavelets”. Society for Industrial and ap-
plied mathematics. Philadelphia, 1992. Notes from the 1.990 CBMS-NSF Conf.
Wavelets Applications, Lowell, MA, USA.

[16] M. Egerstedt, “Linguistic Control of Mobile Robots” IEEE/RSJ IROS Maui,
Hawaii, USA, Oct. 2001.

[17] M. Egerstedt “Behavior Based Robotics Using Hybrid Automata” Lecture Notes
in Computer Science: Hybrid Systems III pp. 103-116, Springer-Verlag, March
2000.

[18] M. Egerstedt and Roger W. Brockett “Feedback Can Reduce the specification
Complexity of Motor Programs” IEEE TRANSACTIONS ON AUTOMATIC
CONTROL pp 213-223, VOL.48.NO.2, FEBRUARY 2003.

[19] Imad Elhajj, Jindong Tan, Yu Sun and Ning Xi, Supermedia Enhanced Hu—
man/Machine Cooperative Control of Robot Formations, IEEE/RSJ Interna-
tional Conference on Intelligent Robots and Systems, October, 2002, EPFL,
Switzerland

[20] Vashti Christina Galpin “Equilablence semantics for concurrency: comparison
and application”. Ph. D. Thesis, University of Edinburgh, 1998.

[21] K. S. E1, R. C. Gonzalez, and E. S. G. Lee “ROBOTICS - Control, Sensing,
Vision, and Intelligence”. McGRAW-HILL INTERNATIONAL EDITIONS, In-
dustrial Engineering series, USA.

[22] Arthur A. Giordano, Frank M.Hsu, “Least Square Estimation with Application
to Digital Signal Processing”, A Wiley-Interscience Publication 1985.

[23] Mohinder S. Grewal and Angus P. Andrews, “Kalman Filtering, theory and
practice”, Prentice Hall Information and System Sciences series, Thomas Kailath,
Series Editor Englewood Cliffs, new Jersey, 1993.

[24] R. L. Grossman, Anil Nerode, A. P. Ravn, and H. Rischel. editors. “Hybrid
Systems”, volume 736 of Lecture Notes in Computer Science, Springer-Verlag,
New York, 1993.

[25] Thomas A. Henzinger. “The theory of hybrid automata”, Proceedings of the
11th Annual Symposium on Logic in Computer Science ( LI CS), IEEE Computer
Society Press, 1996, pp. 278-292.

120

[26] Thomas A. Henzinger. “The theory of hybrid automata” Verification of Digital

and Hybrid Systems (M.K. Inan, R.P. Kurshan, eds. ), NATO ASI Series F:
Computer and Systems Sciences, Vol. 170, Springer-Verlag, 2000, pp. 265-292.

[27] Felix Hausdorff. Set Theory. Translated from the German by John R. Aumann,
ET AL, Chelsea Publishing Company, New York, NY, 1957.

[28] J .E.Hopcroft. R. Motwani and J. D. Ullman, “Introduction to Automata Theory,
Languages, and Computation.” 2nd Edition, Addison Wesley, 2001,

[29] Ling Hou, Anthony. N Michel and Hui Ye, “Stability Analysis of Switched Sys-
tems” IEEE Conference on Decision and Control, December 1996.

[30] T. C. Hsia, “System Identification: Least Square Method”. Lexington Books,
1974.

[31] R. Isermann “practical aspects of process identification”,Automatica ,1982, Vol.
16. pp.575-587.

[32] M. Kam, X. Zhu and P. Kalata, “Sensor Fusion for Mobile Robot Navigation”,
Proceedings of the IEEE, pages 108-119, vol. 85, No. 1, 1997.

[33] Hassan K. Khalil “Nonlinear Systems”, second edition, Prentice Hall, Upper
Saddle River, New Jersey,1996. ‘

[34] Akram Ladroubi, and Karlheinz Grochenig “Nonuniform Sampling and Recon-
struction in Shift-invariant Spaces” SIAM Review, Vol. 43, No.4, pp. 585-620.

[35] W. Li and J .-J .E.Slotine , “Parameter Estimation Strategies for Robotic Appli-
cations” A.S.M.E Winter Annual Meeting 1987.

[36] J. Lygeros, K. H. Johansson,S. N. Simic, J. Zhang, and S. S. Sastry “Dynamical
Properties of Hybrid System”, IEEE Transactions On Automatic Control Vol.
48, No. 1, pp2-pp17, JANUARY 2003.

[37] J. Lygeros, Karl Henrik Johansson, Slobodan N. Simic, Jun Zhang, Shankar
Sastry. “Continuity and Invariance of Hybrid Automata” Proceedings of the 4 0th
IEEE Conference on Decision and Control, Page 340-345, Orlando, Florida, De-
cember 2001.

[38] J. Lygeros, Karl Henrik Johansson, Slobodan N. Simic, Jun Zhang, Shankar
Sastry. On the Existence of Executions of Hybrid Automata Proceedings 38th
IEEE Conference on Decision and Control( CDC ’99), Phoenix, Arizona, Decem-
ber 1999.

[39] V. Manikonda, P.S. Krishnaprasad and J. Hendler, “Behaviors, Hybrid Architec-
tures and Motion Control.” In Mathematic Control Theory. pp.199—226,Springer-
verlag,1998,

121

[40] Anthony N. Michel, “Recent 'IYends in the Stability Analysis of Hybrid Dynam-
ical Systems” IEEE VOL. 45, N01, JANUARY 1999.

[41] Alan V. Oppenheim, Ronald W. Schafer “Discrete-Time Signal Processing”,
Prentice hall, Englewood Cliffs, New Jersey, 1989.

[42] Robi Polikar “The engineer’s ultimate guide to wavelet analysis, the wavelet
tutorial” , http: / /engineering.rowan.edu/ polikar/WAVELETS/WTtutorial.html

[43] Stuart J. Russell and Peter Norvig, “Artificial Intelligence”, Prentice-Hall, 1995.

[44] Hisashi Sasaki, “A Formal Semantics for Verilog-VHDL Simulation Interoper-

ability by Abstract State Machine” Design, Automation and Test in Europe
(DATE), March, 1999.

[45] Robert W. Sebesta, “Concepts of Programming Languages”, Addison-Wesley
Publishing, 5th edition, July, 2001.

[46] R. Sermann and U. Baur, “Two Step Process Identification with Correlation
Analysis and Least Squares Parameter Estimation”, Trans. of ASME, Series
G.J. of Dynamic Systems measurement and Control Vol.96,pp.425—432, 1974.

[47] Zoran Salcic “VHDL AND FPLDs: IN DIGITAL SYTEMS DESIGN, PROTO-
TYPING AND CUSTOMIZATION”, KLUWER ACADEMIC PUBLISHERS.
1998.

[48] Calude E. Shannon, “Classic paper: Communication in the Presence of Noice”,
Proceedings of the IEEE, VOL. 86, N02, FEBRUARY, 1998.

[49] M. Song, szh—Jong Tarn and N. Xi, “Integration of Task Scheduling, Sensing,
Planning an Control in Robotic Manufacturing system”, Proceedings of the IEEE
Vol.88, NO.7, July 2000.

[50] Mumin Song, szh-Jong Tarn, and Ning Xi “Integrated Hybrid System Ap-
proach for Planning and Control of Concurrent Tasks in Manufacturing Sys-
tems”. Proceedings of IEEE International Conference on Robotics and Automa-
tion, pages 1192-1197,volume 2, Leuven, Belgium, May 16-20, 1998.

[51] Yu Sun, Ning Xi, J indong Tan, and Yuechao Wang Interactive Model Identifica-
tion for Nonholonomic Cart Pushing by a Mobile Manipulator , proceedings of
IEEE ICRA 2002, Washington DC.

[52] Yu Sun, Ning Xi, Jindong Tan, ”On-line Model Learning for Robotic Manipu-
lations”IEEE International Conference on Mechatronics and Machine Vision in
Practice, Thailand.

[53] Yu Sun, Ning Xi, and Jindong Tan, A Hybrid System Approach for Event-
Based Planning and Control of Robotic Operations, accepted by ”Computational
Intelligence in Robotics and Automation” (IEEE CIRA) 2003.

122

[54] Jindong Tan. and Ning Xi, “Unified Model Approach for Planning and Con-
trol of Mobile Manipulators”, Proceedings of IEEE International Conference on
Robotics and Automation, pages 3145-3152, Seoul, Korea, May, 2001.

[55] Jindong Tan “Control of Mobile Manipulators”, Ph.D Thesis, Michigan State
University in East Lansing, 2002.

[56] szh-Jong Tarn, Mumin Song and Ning Xi “Intelligent planning and control
for hybrid system” Intelligent Robots and Systems, 1998. Proceedings, 1998
IEEE/RSJ International Conference on , Volume: 2 , 13-17 Oct 1998 Page(s):
972 -977 vol.2

[57] Lucio Tavernini. “Differential automata and their discrete simulators” ,Nonlinear
Analysis, Theory, Methods, and Applications 11(16):665-683, 1987.

[58] Michael Unser, “Sampling-5O year after Shannon”, PROCEEDINGS OF THE
IEEE, VOI.88,NO.4, APRIL, 2000.

[59] Hans S. Witsenhausen. “A class of hybrid-state continuous-time dynamic sys-
tems”IEEE Transactions on Automatic Control,11(2):161-167, 1966

[60] N. Xi, “Event-Based Motion Planning and Control for Robotic Systems” . Ph.D
thesis, Washington Univ. in St. Louis,1993.

[61] Ning Xi, szh-Jong Tarn and A. K. Bejczy “Intelligent Planning and Control for
Multirobot Coordination: An Event-Based Approach”, IEEE Trans. on Robotics
and Automation Vol.12, NO.2,June 1996.

[62] Ning Xi, szh-Jong Tarn, and A. K. Bejczy, “Intelligent Planning and Control for
Multirobot Coordination: An Event-Based Approac ”, IEEE Trans. on Robotics
and Automation, pages 439-452, vol. 12, No. 3, 1996.

[63] Ning Xi, szh-Jong Tarn, “Stability Analysis of non-time referenced internet-
based telerobotic systems”, Robotics and Autonomous Systems, pages 173-178,
vol. 32, 1996.

[64] N ing Xi and szh-Jong Tarn “Modeling and control of multiple segment robotic
operations in a perceptive reference frame” Advanced Intelligent Mechatronics
’97., IEEE/ASME International Conference on , 16-20 Jun 1997 Page(s): 76

[65] Ning Xi and szh-Jong Tarn “Integrated task scheduling and action plan-
ning/control for robotic systems based on a max-plus algebra model” Intelli-
gent Robots and Systems, 1997. IROS ’97., Proceedings of the 1997 IEEE/RSJ
International Conference on , Volume: 2 , 7-11 Sep 1997 Page(s): 926 -931 vol.2

[66] Y. Yamamoto “Control and Coordination of Locomotion and Manipulation of a
Wheeled Mobile Manipulators, Ph.D Dissertation in University of Pennsylvania.
August 1994.

123

[67] Hui Ye, Anthony N. Michel and Ling Hou “Stability Theory for Hybrid Dy-
namical System”, IEEE Transactions On Automatic Control Vol. 43, No. 43,
pp461-pp474, APRIL 1998.

[68] H. Zhuang, Zvi S. Roth “A Linear Solution to the Kinematic Parameter Identifi-
cation of Robot Manipulators” IEEE Transactions on Robotics and Automation
Vol. 9, No. 2, April 1993.

[69] Stephen Edwards, Luciano Lavagno, Edward A. Lee, and Alberto Sangiovanni-
Vincentelli, “Design of embedded Systems: Formal Models, Validation, and Syn-
thesis”. Proceedings of the IEEE, VOL.85, No. 3, March, 1997,pp366-390.

[70] Giovanni De Micheli, “Synthesis and Optimization of Digital Circuits” McGraw-
Hill, Inc. 1992.

[71] Petra Michel Ulrich Lauther Peter Duzy, “The Synthesis Approach to digital
System Design”, Kluwer Academic Publishers, 1992.

[72] Zoran Salcic, “VHDL and FPLDs In Digital Systems Design, Prototyping and
Customization”, Kluwer Academic Publishers 1998.

[73] Mark Gordon Arnord “Verilog Digital Computer Design: Algorithms into Hard-
ware”, Upper Saddle River, 1999.

[74] N elio Muniz Mendes Alves and Sergio de Mello Schneider “Implementation of an
embedded Hardware Description Language Using Haskell”. Journal of Universal
Computer Science, Vol. 9, No. 8(2003), 795-812.

[75] Catherine G. Wong and Alain J. Martin “Data-driven process decomposition for
circuit synthesis”. Proceedings of IEEE Conference on Electronic Circuits and
Systems, September 2001.

[76] Reid Harrison, Christof Koch, “Guiding a robot with an Analog VLSI motion
sensor Based on the Visual System of the Fly”, Technical Report at Center for
Neuromorphic Systes Engineering, Caltech, 2002.

[77] Jorgen Staunstrup and Wayne Wolf, “Hardware/ Software Co—Design”:
Priciples and Practice, KLUWER ACADEMIC PUBLISHERS,
BOSTON/DORDRECHT/LONDON, 1997.

[78] Toshio Takahashi, “New Digital Hardware Control Method for High Performance
AC servo Motor Drive—Accelerator Servo Drive Development Platform for Mili-
tary Application”, Military Electronics Conference, Sept. 24-25, 2004.

[79] Fabrice Aubepart, Philippe Poure and Francis Braun, “VLSI Design Approach
of Complex Motor Control, Case of Direct Torque Control of AC machine” .
The 7th IEEE International Conference on Electronics, Circuits and Systems,
ICECS 2000., Volume: 2, 2000 pp. 814 817.

124

[80] Daniel D. Gajski, Frank Vahid, Sanjiv Narayan and Jie Gong, “Specification
and Design of Embedded System”, PTR Prentice Hall, Englewood Cliffs, New
Jersey, 1994.

125

IIIIIIIIIIIIIIIIIIIIIIIIIIII

111]][llllllilllll111111[111111111