UTRRG's efforts on decision-making in advanced
robotics systems started decades ago with mathematical modeling of
manipulators' kinematics, dynamics, and compliance. Based upon
these models, performance criteria were
defined and constructed.
Multi-criteria inverse kinematics
methods were then developed to solve the redundancy problem.
Finally, to
manage all the choices of selecting performance criteria and other
parameters for a given task,
decision making strategies were also developed.I. Performance Criteria
When attempting to improve performance of a redundant robotic system
for a given task by means of resource allocation, there must be some
metrics that are used to determine optimal allocation. These
metrics are usually called “performance criteria.” By definition,
performance criteria are real-valued, typically non-negative,
functions defined on the joint space to measure some quality of the “states” of a
manipulator.
A) Criteria Development
Numerous performance criteria have been developed
and refined at UTRRG
[Bevill, 1990][Van
Doren, 1992][Browning,
1996][Harden, 1997][Cocca,
2000] with many more found in the literature. Some of
these performance criteria are listed in the following table.
Table 1. Performance criteria.
| Purpose |
Performance Criteria |
|
Limit
avoidance |
Joint Range Availability
Velocity Limit Avoidance
Torque Limit Avoidance
Joint Torque Norm |
|
Obstacle
avoidance |
Smallest Minimum Distance
Average Minimum Distance Reciprocal
Artificial Force and Torque |
|
Speed of
operation |
Generalized EEF Speed
Velocity Transmission Ratio |
|
Load
carrying capacity |
Generalized EEF Force
Force Transmission Ratio |
|
Manipulator
precision |
Velocity Transmission Ratio
Generalized EEF Load Stiffness
EEF Potential Energy |
|
Energy
minimization |
Kinetic Energy
Inertia Frobenius Norm |
|
Cyclic
motion |
Joint Drift Minimization |
For more detailed discussion of these performance criteria,
please refer to [Pryor et al.,
1999], [Pryor, 2002],
[Tisius, 2004], or
[Pholsiri, 2004].
B) Criteria Normalization
Due to mathematical complexity of performance criteria,
there are some issues that must be dealt with before they
can be successfully applied to the decision making problem.
These issues include subjectivity, frame dependency,
scaling, normalization, task dependency, levels of
redundancy resolution, and couplings and conflicts
[Bevill, 1990][Pryor,
2002][Pholsiri,
2004]. At the center of these issues is
normalization, which if not done properly could render the
decision making scheme ineffective.
In common complex task completion, multiple criteria are
needed. To linearly combine these criteria (a popular
method for dealing with multi-criteria optimization), they
must be properly normalized so that their magnitudes are
comparable and their weights correctly represent their
relative importance.
Bevill [1990] was the
first at UTRRG to tackle the normalization problem. Tisius [2004]
proposed an empirical method of criteria normalization
achievable by constructing statistical maps of criteria values over
the robot workspace. These statistical maps can be initially
constructed and incrementally enhanced while the robot executes
tasks. These maps provide an alternative to local
normalization of criteria with
global normalization, which can yield better results.
II. Multi-Criteria Inverse Kinematics
UTRRG has inspired to develop generalized inverse
kinematics methods that can be applied to any serial
manipulator. To this end, three main inverse
kinematics methods have been developed.
A) Direct Search
The Direst Search method was to robustly solve the inverse kinematics
problem by using the forward position solution to guide the search for
the inverse solution [Hooper, 1994]. The search begins with an estimated solution,
which serves as a base configuration. Then small joint perturbations
are introduced to generate new configurations and the error is
calculated at each of these new configurations. A new base
configuration that reduces the error is then chosen. This process
continues until the search finds a solution, i.e. the error is zero.
The search is direct in the sense that it does not use any derivatives
and hence it is robust, especially at or around mathematical
singularities.
B) Hybrid Generalized Inverse
To improve the speed of the Direct Search method, the
Performance-Based Hybrid Generalized Inverse
method (Figure 1) was later developed
[Kapoor, 1996][Kapoor
et al., 1998].
A generalized, iterative inverse (see Figure 2) was used to solve the
inverse kinematics problem of a selected 6-DOF substructure to meet
the end-effector constraints. The remaining joints were then used to
generate joint-space options using the direct search. Criteria are
then evaluated at each of these options and the options are ranked
based on some metrics. The option with the best ranking is then
selected.
|
 |
|
Figure 1. Performance-Based
Hybrid Generalized Inverse. |
|
 |
|
Figure 2. Generalized,
iterative inverse for 6-DOF structure. |
C) Compromise Solution
Compromise Solution (CS) [Cetin, 1999][Cetin et al., 2003] is a concept in goal
programming or goal setting in multiple objective optimizations where
even though the solution is not truly optimal (a truly optimal
solution implies that every objective is optimized, which is usually
unattainable due to conflicts), the decision maker is still satisfied
with the solution with respect to his/her goals. Instead of trying to
optimize a performance index, which is generally a linear combination
of performance criteria, CS attempts to find a solution that makes
most, if not all, of the criteria within acceptable levels.
Solving the inverse kinematics at the position level, CS uses a
nonlinear programming optimization technique to find an optimal
solution. The optimal solution, in this case, is a solution in
which performance criteria values deviate from their target values the
least. This method offers the user a luxury to specify his goals and
allows the user to be actively involved in the redundancy resolution
process. In summary, CS tries to minimize the lp-norm
of the weighted sum of the percent deviations of all criteria while
satisfying the trajectory constraints and attempting to keep each
deviation under its Maximum Allowable Variation. Implementation of
this method utilizes Generalized Reduced Gradient (GRG) nonlinear
optimization algorithm [Smith
and Lasdon, 1992].
The main limitation with the current practice in the decision
making system for redundant robots is that the whole process is too
complicated for an inexperienced user. First, the user needs to
analyze the tasks at hand. Then, he needs to choose a set of
performance criteria that "he thinks" are relevant to the tasks.
This is difficult because (1) many of the criteria do not have task-level
interpretations that an average user can easily relate to and (2)
there are couplings and conflicts among several performance criteria. Finally,
depending on the optimization scheme chosen, he must combine all the
select criteria. Perhaps the most popular method used to combine
criteria is the weighted sum method. In this method, each
criterion is assigned a "weight" that represents its importance
relative to other criteria. The composite performance objective
is then formed by adding the products of the criteria and their
assigned weights. In order for the weight sum method to be of
any use, the criteria must be properly normalized so that no one
criterion artificially dominates the solution because of its
relatively large magnitude. III. Decision Making Strategies
In order to streamline the decision making process to make it
more efficient and more accessible to non-expert users, the
following decision making strategies were developed. A) Critical Boundaries
Discovering that optimizing too many criteria sometimes realizes
no performance gain, Pryor [2002]
introduced the critical boundary
concept to decrease the number of criteria to be included in the
multi-criteria inverse kinematics scheme at a given time. The
basic idea is intuitive and straightforward: a criterion can only be
included when it is necessary for the task completion. For
instance, when all joints of the robot are somewhat in the middle of
their travel ranges, there is no need to optimize the joint limit
avoidance criterion. Only when some joints approach their limits (or
the criterion crosses its critical boundary) should the joint limit
avoidance criterion be included. Using this simple strategy,
Pryor demonstrated that a 10-DOF robot could complete a fairly
complex operation while conventional methods failed. During
the operation, at most three criteria were active at a given
time and all critical boundaries were traversed many times,
justifying the use of critical boundaries. B) Task-Based
Decision Making
The task-based decision making approach
[Pholsiri, 2004][Pholsiri
et al., 2004] is our most recent development in this
research area. Its uniqueness lies in the fact that robotic
tasks are numerically described in terms of velocity, force, and
accuracy requirements and these task requirements are achieved using
real-time robot capability analysis in the redundancy resolution
process. Two major components of task-based decision making
approach are real-time Robot Capability Analysis (RCA) and
Task-Based Redundancy Resolution (TBRR). Real-time Robot
Capability Analysis (RCA)
Real-time RCA is a major component of task-based decision making.
Conventionally, two methods or tools -- ellipsoid and polytope --
are used to analyze robotic capabilities (Figure 3(a)).
Ellipsoid is simple with closed-form solutions but inaccurate due to
the use of 2-norm. Polytope is accurate but complex and, for
high-DOF robots, its computation can be prohibitively expensive (see
[Hwang et al., 2000]
for example).
Since neither ellipsoid nor polytope could satisfy our needs, we have developed the Vector Expansion (VE) method to accurately
estimate in real time robot capabilities given the robot's
configuration and properties. The VE method was adapted from
the ellipsoid expansion method
[Bowling and Khatib, 1995]
that was used to analyze the isotropic acceleration characteristics
of non-redundant serial manipulators. In contrast to the
joint-to-task-space mapping in the ellipsoid and polytope methods,
the VE method borrows the reverse mapping technique from the
ellipsoid expansion method (Figure 3).
(a)
(b) Figure 3. (a) Ellipsoid vs
Polytope and (b) the Vector Expansion method.
Task-Based Redundancy Resolution (TBRR)
TBRR functions on the basic premise that we need to "find a
solution that first and foremost satisfies the system and task
constraints and then optimizes a desired performance objective."
Figure 4. TBRR schematic diagram.
In addition to real-time RCA and TBRR,
Pholsiri [2004] also
proposed two other supporting components as part of the decision
making and control framework:
- Learning algorithm of subjective system parameters
- Force control integration with TBRR
|
