%!PS-Adobe-3.0
%%Title: (ParKinJac\311)
%%Creator: (Microsoft Word: LaserWriter 8 8.1.1)
%%CreationDate: (13:28 Uhr Freitag, 9. Mai 1997)
%%For: (D.Henrich)
%%Pages: 20
%%DocumentFonts: Times-Italic Symbol Times-Bold Times-Roman
%%DocumentNeededFonts: Times-Italic Symbol Times-Bold Times-Roman
%%DocumentSuppliedFonts:
%%DocumentData: Clean7Bit
%%PageOrder: Ascend
%%Orientation: Portrait
%ADO_PaperArea: -31 -28 811 567
%ADO_ImageableArea: 0 0 781 538
%%EndComments
/md 192 dict def md begin
/currentpacking where {pop /sc_oldpacking currentpacking def true setpacking}if
%%BeginFile: adobe_psp_basic
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/bd{bind def}bind def
/xdf{exch def}bd
/xs{exch store}bd
/ld{load def}bd
/Z{0 def}bd
/T/true
/F/false
/:L/lineto
/lw/setlinewidth
/:M/moveto
/rl/rlineto
/rm/rmoveto
/:C/curveto
/:T/translate
/:K/closepath
/:mf/makefont
/gS/gsave
/gR/grestore
/np/newpath
14{ld}repeat
/$m matrix def
/av 81 def
/por true def
/normland false def
/psb-nosave{}bd
/pse-nosave{}bd
/us Z
/psb{/us save store}bd
/pse{us restore}bd
/level2
/languagelevel where
{
pop languagelevel 2 ge
}{
false
}ifelse
def
/featurecleanup
{
stopped
cleartomark
countdictstack exch sub dup 0 gt
{
{end}repeat
}{
pop
}ifelse
}bd
/noload Z
/startnoload
{
{/noload save store}if
}bd
/endnoload
{
{noload restore}if
}bd
level2 startnoload
/setjob
{
statusdict/jobname 3 -1 roll put
}bd
/setcopies
{
userdict/#copies 3 -1 roll put
}bd
level2 endnoload level2 not startnoload
/setjob
{
1 dict begin/JobName xdf currentdict end setuserparams
}bd
/setcopies
{
1 dict begin/NumCopies xdf currentdict end setpagedevice
}bd
level2 not endnoload
/pm Z
/mT Z
/sD Z
/realshowpage Z
/initializepage
{
/pm save store mT concat
}bd
/endp
{
pm restore showpage
}def
/$c/DeviceRGB def
/rectclip where
{
pop/rC/rectclip ld
}{
/rC
{
np 4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
:K
clip np
}bd
}ifelse
/rectfill where
{
pop/rF/rectfill ld
}{
/rF
{
gS
np
4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
fill
gR
}bd
}ifelse
/rectstroke where
{
pop/rS/rectstroke ld
}{
/rS
{
gS
np
4 2 roll
:M
1 index 0 rl
0 exch rl
neg 0 rl
:K
stroke
gR
}bd
}ifelse
%%EndFile
level2 startnoload
%%BeginFile: adobe_psp_colorspace_level1
%%Copyright: Copyright 1991-1993 Adobe Systems Incorporated. All Rights Reserved.
/G/setgray ld
/:F/setrgbcolor ld
%%EndFile
level2 endnoload level2 not startnoload
%%BeginFile: adobe_psp_colorspace_level2
%%Copyright: Copyright 1991-1993 Adobe Systems Incorporated. All Rights Reserved.
/G
{
dup dup setcolor
}bd
/setcolor where
{pop/:F/setcolor ld}if
/initializepage
{
/pm save store mT concat
$c setcolorspace
}bd
%%EndFile
level2 not endnoload
%%BeginFile: adobe_psp_uniform_graphics
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/@a
{
np :M 0 rl :L 0 exch rl 0 rl :L fill
}bd
/@b
{
np :M 0 rl 0 exch rl :L 0 rl 0 exch rl fill
}bd
/arct where
{
pop
}{
/arct
{
arcto pop pop pop pop
}bd
}ifelse
/x1 Z
/x2 Z
/y1 Z
/y2 Z
/rad Z
/@q
{
/rad xs
/y2 xs
/x2 xs
/y1 xs
/x1 xs
np
x2 x1 add 2 div y1 :M
x2 y1 x2 y2 rad arct
x2 y2 x1 y2 rad arct
x1 y2 x1 y1 rad arct
x1 y1 x2 y1 rad arct
fill
}bd
/@s
{
/rad xs
/y2 xs
/x2 xs
/y1 xs
/x1 xs
np
x2 x1 add 2 div y1 :M
x2 y1 x2 y2 rad arct
x2 y2 x1 y2 rad arct
x1 y2 x1 y1 rad arct
x1 y1 x2 y1 rad arct
:K
stroke
}bd
/@i
{
np 0 360 arc fill
}bd
/@j
{
gS
np
:T
scale
0 0 .5 0 360 arc
fill
gR
}bd
/@e
{
np
0 360 arc
:K
stroke
}bd
/@f
{
np
$m currentmatrix
pop
:T
scale
0 0 .5 0 360 arc
:K
$m setmatrix
stroke
}bd
/@k
{
gS
np
:T
0 0 :M
0 0 5 2 roll
arc fill
gR
}bd
/@l
{
gS
np
:T
0 0 :M
scale
0 0 .5 5 -2 roll arc
fill
gR
}bd
/@m
{
np
arc
stroke
}bd
/@n
{
np
$m currentmatrix
pop
:T
scale
0 0 .5 5 -2 roll arc
$m setmatrix
stroke
}bd
%%EndFile
%%BeginFile: adobe_psp_basic_text
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/S/show ld
/A{
0.0 exch ashow
}bd
/R{
0.0 exch 32 exch widthshow
}bd
/W{
0.0 3 1 roll widthshow
}bd
/J{
0.0 32 4 2 roll 0.0 exch awidthshow
}bd
/V{
0.0 4 1 roll 0.0 exch awidthshow
}bd
/fcflg true def
/fc{
fcflg{
vmstatus exch sub 50000 lt{
(%%[ Warning: Running out of memory ]%%\r)print flush/fcflg false store
}if pop
}if
}bd
/$f[1 0 0 -1 0 0]def
/:ff{$f :mf}bd
/MacEncoding StandardEncoding 256 array copy def
MacEncoding 39/quotesingle put
MacEncoding 96/grave put
/Adieresis/Aring/Ccedilla/Eacute/Ntilde/Odieresis/Udieresis/aacute
/agrave/acircumflex/adieresis/atilde/aring/ccedilla/eacute/egrave
/ecircumflex/edieresis/iacute/igrave/icircumflex/idieresis/ntilde/oacute
/ograve/ocircumflex/odieresis/otilde/uacute/ugrave/ucircumflex/udieresis
/dagger/degree/cent/sterling/section/bullet/paragraph/germandbls
/registered/copyright/trademark/acute/dieresis/notequal/AE/Oslash
/infinity/plusminus/lessequal/greaterequal/yen/mu/partialdiff/summation
/product/pi/integral/ordfeminine/ordmasculine/Omega/ae/oslash
/questiondown/exclamdown/logicalnot/radical/florin/approxequal/Delta/guillemotleft
/guillemotright/ellipsis/space/Agrave/Atilde/Otilde/OE/oe
/endash/emdash/quotedblleft/quotedblright/quoteleft/quoteright/divide/lozenge
/ydieresis/Ydieresis/fraction/currency/guilsinglleft/guilsinglright/fi/fl
/daggerdbl/periodcentered/quotesinglbase/quotedblbase/perthousand
/Acircumflex/Ecircumflex/Aacute/Edieresis/Egrave/Iacute/Icircumflex/Idieresis/Igrave
/Oacute/Ocircumflex/apple/Ograve/Uacute/Ucircumflex/Ugrave/dotlessi/circumflex/tilde
/macron/breve/dotaccent/ring/cedilla/hungarumlaut/ogonek/caron
MacEncoding 128 128 getinterval astore pop
level2 startnoload
/copyfontdict
{
findfont dup length dict
begin
{
1 index/FID ne{def}{pop pop}ifelse
}forall
}bd
level2 endnoload level2 not startnoload
/copyfontdict
{
findfont dup length dict
copy
begin
}bd
level2 not endnoload
md/fontname known not{
/fontname/customfont def
}if
/Encoding Z
/:mre
{
copyfontdict
/Encoding MacEncoding def
fontname currentdict
end
definefont :ff def
}bd
/:bsr
{
copyfontdict
/Encoding Encoding 256 array copy def
Encoding dup
}bd
/pd{put dup}bd
/:esr
{
pop pop
fontname currentdict
end
definefont :ff def
}bd
/scf
{
scalefont def
}bd
/scf-non
{
$m scale :mf setfont
}bd
/ps Z
/fz{/ps xs}bd
/sf/setfont ld
/cF/currentfont ld
/mbf
{
/makeblendedfont where
{
pop
makeblendedfont
/ABlend exch definefont
}{
pop
}ifelse
def
}def
%%EndFile
%%BeginFile: adobe_psp_derived_styles
%%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved.
/wi
version(23.0)eq
{
{
gS 0 0 0 0 rC stringwidth gR
}bind
}{
/stringwidth load
}ifelse
def
/$o 1. def
/gl{$o G}bd
/ms{:M S}bd
/condensedmtx[.82 0 0 1 0 0]def
/:mc
{
condensedmtx :mf def
}bd
/extendedmtx[1.18 0 0 1 0 0]def
/:me
{
extendedmtx :mf def
}bd
/basefont Z
/basefonto Z
/dxa Z
/dxb Z
/dxc Z
/dxd Z
/dsdx2 Z
/bfproc Z
/:fbase
{
dup/FontType get 0 eq{
dup length dict begin
dup{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall
/FDepVector exch/FDepVector get[exch/:fbase load forall]def
}/bfproc load ifelse
/customfont currentdict end definefont
}bd
/:mo
{
/bfproc{
dup dup length 2 add dict
begin
{
1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse
}forall
/PaintType 2 def
/StrokeWidth .012 0 FontMatrix idtransform pop def
/customfont currentdict
end
definefont
8 dict begin
/basefonto xdf
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
basefont setfont
( )dup 0 4 -1 roll put
dup wi
setcharwidth
0 0 :M
gS
gl
dup show
gR
basefonto setfont
show
end
}def
}store :fbase
}bd
/:mso
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxa 1 ps div def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
1 index 0 ne
{
exch dxa add exch
}if
setcharwidth
dup 0 0 ms
dup dxa 0 ms
dup dxa dxa ms
dup 0 dxa ms
gl
dxa 2. div dup ms
end
end
}def
}store :fbase
}bd
/:ms
{
/bfproc{
dup dup length 2 add dict
begin
{
1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse
}forall
/PaintType 2 def
/StrokeWidth .012 0 FontMatrix idtransform pop def
/customfont currentdict
end
definefont
8 dict begin
/basefonto xdf
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxb .05 def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
exch dup 0 ne
{
dxb add
}if
exch setcharwidth
dup dxb .01 add 0 ms
0 dxb :T
gS
gl
dup 0 0 ms
gR
basefonto setfont
0 0 ms
end
end
}def
}store :fbase
}bd
/:mss
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxc 1 ps div def
/dsdx2 .05 dxc 2 div add def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
exch dup 0 ne
{
dsdx2 add
}if
exch setcharwidth
dup dsdx2 .01 add 0 ms
0 .05 dxc 2 div sub :T
dup 0 0 ms
dup dxc 0 ms
dup dxc dxc ms
dup 0 dxc ms
gl
dxc 2 div dup ms
end
end
}def
}store :fbase
}bd
/:msb
{
/bfproc{
7 dict begin
/basefont xdf
/FontType 3 def
/FontMatrix[1 0 0 1 0 0]def
/FontBBox[0 0 1 1]def
/Encoding StandardEncoding def
/BuildChar
{
exch begin
sD begin
/dxd .03 def
basefont setfont
( )dup 0 4 -1 roll put
dup wi
1 index 0 ne
{
exch dxd add exch
}if
setcharwidth
dup 0 0 ms
dup dxd 0 ms
dup dxd dxd ms
0 dxd ms
end
end
}def
}store :fbase
}bd
/italicmtx[1 0 -.212557 1 0 0]def
/:mi
{
italicmtx :mf def
}bd
/:v
{
[exch dup/FontMatrix get exch
dup/FontInfo known
{
/FontInfo get
dup/UnderlinePosition known
{
dup/UnderlinePosition get
2 index 0
3 1 roll
transform
exch pop
}{
.1
}ifelse
3 1 roll
dup/UnderlineThickness known
{
/UnderlineThickness get
exch 0 3 1 roll
transform
exch pop
abs
}{
pop pop .067
}ifelse
}{
pop pop .1 .067
}ifelse
]
}bd
/$t Z
/$p Z
/$s Z
/:p
{
aload pop
2 index mul/$t xs
1 index mul/$p xs
.012 mul/$s xs
}bd
/:m
{gS
0 $p rm
$t lw
0 rl stroke
gR
}bd
/:n
{
gS
0 $p rm
$t lw
0 rl
gS
gl
stroke
gR
strokepath
$s lw
/setstrokeadjust where{pop
currentstrokeadjust true setstrokeadjust stroke setstrokeadjust
}{
stroke
}ifelse
gR
}bd
/:o
{gS
0 $p rm
$t 2 div dup rm
$t lw
dup 0 rl
stroke
gR
:n
}bd
%%EndFile
/currentpacking where {pop sc_oldpacking setpacking}if
end % md
%%EndProlog
%%BeginSetup
md begin
/$c[/CIEBasedABC 3 dict dup begin
/DecodeLMN[{1.8 exp}bind dup dup]def
/MatrixLMN[0.4439 0.2522 0.0436 0.3341 0.6371 0.1387 0.1725 0.1107 0.9067]def
/WhitePoint[0.9505 1.0 1.0890]def end
]def
countdictstack
[
{%stopped
%%BeginFeature: *ManualFeed False
level2 {1 dict dup /ManualFeed false put setpagedevice}{statusdict begin /manualfeed false store end} ifelse
%%EndFeature
}featurecleanup
countdictstack
[
{%stopped
%%BeginFeature: *InputSlot Upper
%%EndFeature
}featurecleanup
countdictstack
[
{%stopped
%%BeginFeature: *PageRegion A4Small
level2 {
2 dict dup /PageSize [595 842] put dup /ImagingBBox [17 22 577 819] put setpagedevice
}{
a4small
} ifelse
%%EndFeature
}featurecleanup
(D.Henrich)setjob
/pT[1 0 0 -1 28 811]def/mT[1 0 0 -1 28 811]def
/sD 16 dict def
300 level2{1 dict dup/WaitTimeout 4 -1 roll put setuserparams}{statusdict/waittimeout 3 -1 roll put}ifelse
%%IncludeFont: Times-Italic
%%IncludeFont: Symbol
%%IncludeFont: Times-Bold
%%IncludeFont: Times-Roman
/f0_1/Times-Italic :mre
/f0_12 f0_1 12 scf
/f0_10 f0_1 10 scf
/f1_1/Symbol :bsr
240/apple pd
:esr /f1_18 f1_1 18 scf
/f1_14 f1_1 14 scf
/f1_12 f1_1 12 scf
/f2_1 f1_1 :mi
/f2_12 f2_1 12 scf
/f3_1/Times-Bold :mre
/f3_18 f3_1 18 scf
/f3_14 f3_1 14 scf
/f3_12 f3_1 12 scf
/f4_1 f1_1 def
/f4_18 f4_1 18 scf
/f4_14 f4_1 14 scf
/f4_12 f4_1 12 scf
/f5_1/Times-Roman :mre
/f5_18 f5_1 18 scf
/f5_14 f5_1 14 scf
/f5_13 f5_1 13 scf
/f5_12 f5_1 12 scf
/f5_10 f5_1 10 scf
/f5_9 f5_1 9 scf
/Courier findfont[10 0 0 -10 0 0]:mf setfont
%%EndSetup
%%Page: 1 1
%%BeginPageSetup
initializepage
(D.Henrich; page: 1 of 20)setjob
%%EndPageSetup
gS 0 0 538 781 rC
42 6 :M
f0_10 sf
3.824 .382(Technical Report 10/97, University of Karlsruhe,)J
42 17 :M
.23 .023(Computer Science Department, ISSN 1432-7864)J
45 68 :M
f3_18 sf
2.886 .289(A Review of Parallel Processing Approaches to Robot)J
166 92 :M
2.385 .238(Kinematics and Jacobian)J
127 132 :M
f5_13 sf
-.11(Dominik H)A
f5_12 sf
-.125(ENRICH)A
f5_13 sf
-.096(, Joachim K)A
f5_12 sf
-.135(ARL)A
f5_13 sf
-.102( und Heinz W)A
f5_12 sf
-.214(\205RN)A
121 169 :M
f5_13 sf
.076 .008(Institute for Real-Time Computer Systems and Robotics)J
127 182 :M
-.07(University of Karlsruhe, D-76128 Karlsruhe, Germany)A
191 195 :M
-.041(e-mail: dHenrich@ira.uka.de)A
f5_9 sf
0 -3 rm
(1)S
0 3 rm
245 226 :M
f3_12 sf
.337(Abstract)A
63 256 :M
f0_12 sf
.925 .093(Due to continuously increasing demands in the area of advanced robot control, it)J
63 274 :M
.394 .039(became necessary to speed up the computation. One way to reduce the computation)J
63 292 :M
.283 .028(time is to distribute the computation onto several processing units. In this survey we)J
63 310 :M
-.128(present different approaches to parallel computation of robot kinematics and Jacobian.)A
63 328 :M
1.577 .158(Thereby, we discuss both the forward and the reverse problem. We introduce a)J
63 346 :M
-.092(classification scheme and classify the references by this scheme.)A
63 379 :M
f5_12 sf
-.035(Keywords: parallel processing, Jacobian, robot kinematics, robot control.)A
42 446 :M
f5_18 sf
(1)S
63 446 :M
f3_18 sf
.274(Introduction)A
63 480 :M
f5_12 sf
.224 .022(Due to continuously increasing demands in the area of advanced robot control, it became)J
42 498 :M
.348 .035(necessary to speed up the computation. Since it should be possible to control the motion of a)J
42 516 :M
.321 .032(robot manipulator in real-time, it is necessary to reduce the computation time to less than the)J
42 534 :M
.966 .097(cycle rate of the control loop. One way to reduce the computation time is to distribute the)J
42 552 :M
-.071(computation over several processing units.)A
63 576 :M
1.634 .163(There are other overviews and reviews on parallel processing approaches to robotic)J
42 594 :M
1.393 .139(problems. Earlier overviews include [Lee89] and [Graham89]. Lee takes a closer look at)J
42 612 :M
.325 .033(parallel approaches in [Lee91]. He tries to find common features in the different problems of)J
42 630 :M
.687 .069(kinematics, dynamics and Jacobian computation. The latest summary is from Zomaya et al.)J
42 648 :M
-.059([Zomaya96]. They summarize by saying that the field of research is still widespread and can be)A
42 666 :M
.625 .063(roughly divided into two categories: approaches using general-purpose processing units and)J
42 684 :M
-.032(approaches using customized chips. Their conclusion is that further research in this field is still)A
42 702 :M
(required.)S
-4124 -4126 -1 1 -4122 -4126 1 -4124 -4127 @a
42 725.24 -.24 .24 185.24 725 .24 42 725 @a
42 738 :M
f5_9 sf
(1)S
56 741 :M
f5_10 sf
.902 .09(Further information can be found on the Web pages of the PaRo group \(Parallel Robotics\) of the IPR at)J
56 752 :M
-.044(http://wwwipr.ira.uka.de/~paro/)A
endp
%%Page: 2 2
%%BeginPageSetup
initializepage
(D.Henrich; page: 2 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(2)S
91 94 :M
-.073(Here, we show how the computation of robot control can be done in parallel and try to give)A
70 112 :M
1.017 .102(a complete overview. In Section 2, we introduce a classification scheme. In Section 3, we)J
70 130 :M
.112 .011(discuss the achievements in the field of parallel computation of robot kinematics. The parallel)J
70 148 :M
.083 .008(computation of Jacobian is discussed in Section 4. Both of the last two sections are again split)J
70 166 :M
.128 .013(up into the forward and the reverse problem. In the summary, we give an overview of parallel)J
70 184 :M
-.11(computation and point out the most efficient approaches to robot control.)A
70 241 :M
f5_18 sf
(2)S
91 241 :M
f3_18 sf
4.852 .485(Classification Scheme)J
91 275 :M
f5_12 sf
-.012(To review the literature of the past years, we will introduce a classification scheme, which)A
70 293 :M
.009 .001(allows us to structure and compare the approaches up to now \(Table I\). With each reference in)J
70 311 :M
.339 .034(the list at the end of this article, there is a list of keywords indicating the classification of the)J
70 329 :M
.336(work.)A
91 353 :M
-.023(The classification scheme is divided into a couple of aspects. The aspect )A
f0_12 sf
-.029(Problem)A
f5_12 sf
-.023( refers to)A
70 371 :M
.144 .014(the problem that is treated in the reference. The aspect )J
f0_12 sf
.199 .02(level of parallelism)J
f5_12 sf
.167 .017( indicates on which)J
70 389 :M
-.096(level the algorithm exploits the parallelism. The aspect )A
f0_12 sf
-.104(Interconnection topology)A
f5_12 sf
-.103( indicates about)A
70 407 :M
-.125(the logical or physical topology of the communication network. The aspect )A
f0_12 sf
-.144(processing paradigm)A
70 425 :M
f5_12 sf
-.005(describes which basic approach is used in parallel processing. The aspect )A
f0_12 sf
-.005(Scalability)A
f5_12 sf
-.005( is used to)A
70 443 :M
.05 .005(determine whether the design is scalable by adding or removing processing units or whether it)J
70 461 :M
-.002(is designed for a fixed number of processors. Other aspects include )A
f0_12 sf
-.002(coordinate rotation digital)A
70 479 :M
3.168 .317(computer \(CORDIC\) arithmetic)J
f5_12 sf
1.667 .167( that cover a large number of references. But there are)J
70 497 :M
-.008(approaches that are only used in very few references and that are introduced to show that there)A
70 515 :M
-.115(is an alternative.)A
91 539 :M
1.833 .183(We introduce four levels of parallelism with decreasing granularity as described in)J
70 557 :M
2.008 .201([Sadayappan89, Zomaya92]. If several problems \(e.g., forward kinematics and forward)J
70 575 :M
.47 .047(Jacobian\) are solved in parallel, we call it parallelism on the task level. The characteristic of)J
70 593 :M
.398 .04(parallelism on the joint level is that the computations are done for all joints at once. Another)J
70 611 :M
.064 .006(level involves the exploitation of parallelism in the computation chain, e.g. if there are several)J
70 629 :M
.37 .037(independent equations. The fine-grained parallelism is the parallelism on the operation level,)J
70 647 :M
-.145(such as matrix or matrix/vector multiplication etc.)A
91 671 :M
-.046(We classify the )A
f0_12 sf
-.052(processing paradigm)A
f5_12 sf
-.037( in )A
f0_12 sf
-.048(multiple instruction, multiple data \(MIMD\))A
f5_12 sf
-.029(, )A
f0_12 sf
-.055(single)A
70 689 :M
-.091(instruction multiple data \(SIMD\))A
f5_12 sf
-.086( and )A
f0_12 sf
-.085(systolic architectures)A
f5_12 sf
-.088(. There is a slight difference between)A
70 707 :M
.427 .043(SIMD and systolic architectures. In SIMD, the same instruction is applied to many pieces of)J
70 725 :M
.554 .055(data at the same time and the instruction stream is a stream with respect to time, whereas in)J
70 743 :M
.079 .008(systolic architectures, several instructions are applied to many pieces of data at the same time,)J
70 761 :M
.32 .032(but the instructions in each processing unit depend only on the arrival of the data. So there is)J
70 779 :M
-.114(nothing like an instruction stream with respect to time.)A
endp
%%Page: 3 3
%%BeginPageSetup
initializepage
(D.Henrich; page: 3 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(3)S
91 94 :M
.068 .007(We also distinguish between static and dynamic load balancing. If static load balancing is)J
70 112 :M
-.052(used, the task schedule is computed before the program is started. Dynamic load balancing also)A
70 130 :M
.695 .069(considers the current workload of the processors and different communication times at run-)J
70 148 :M
-.096(time. In the literature, both possibilities are called scheduling.)A
70 192 :M
f3_12 sf
.671(Aspect)A
296 192 :M
.859(Keywords)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 175.24 -.24 .24 295.24 175 .24 69 175 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 175.24 -.24 .24 296.24 175 .24 295 175 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 175.24 -.24 .24 522.24 175 .24 296 175 @a
70 215 :M
f5_12 sf
-.11(Problem)A
296 215 :M
-.115(forward kinematics)A
296 228 :M
-.154(reverse kinematics)A
296 241 :M
-.063(forward Jacobian)A
296 254 :M
-.107(reverse Jacobian)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 198.24 -.24 .24 295.24 198 .24 69 198 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 198.24 -.24 .24 296.24 198 .24 295 198 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 198.24 -.24 .24 522.24 198 .24 296 198 @a
70 277 :M
-.19(Level of parallelism)A
296 277 :M
-.183(task level)A
296 290 :M
-.232(joint level)A
296 303 :M
-.195(computation chain level)A
296 316 :M
-.188(operation level)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 260.24 -.24 .24 295.24 260 .24 69 260 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 260.24 -.24 .24 296.24 260 .24 295 260 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 260.24 -.24 .24 522.24 260 .24 296 260 @a
70 339 :M
-.129(Interconnection topology)A
296 339 :M
-.16(array)A
296 352 :M
-.326(tree)A
296 365 :M
-.192(complete mesh)A
296 378 :M
-.236(pipeline)A
296 391 :M
-.121(hypercube)A
296 404 :M
-.093(special purpose)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 322.24 -.24 .24 295.24 322 .24 69 322 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 322.24 -.24 .24 296.24 322 .24 295 322 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 322.24 -.24 .24 522.24 322 .24 296 322 @a
70 427 :M
-.072(Processing paradigm)A
296 427 :M
-.663(MIMD)A
296 440 :M
-.331(SIMD)A
296 453 :M
-.14(systolic architectures)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 410.24 -.24 .24 295.24 410 .24 69 410 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 410.24 -.24 .24 296.24 410 .24 295 410 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 410.24 -.24 .24 522.24 410 .24 296 410 @a
70 476 :M
-.232(Scalability)A
296 476 :M
-.234(scalable)A
296 489 :M
-.179(not scalable)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 459.24 -.24 .24 295.24 459 .24 69 459 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 459.24 -.24 .24 296.24 459 .24 295 459 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 459.24 -.24 .24 522.24 459 .24 296 459 @a
70 512 :M
-.197(Others)A
296 512 :M
-.266(CORDIC)A
296 525 :M
-.165(dynamic load balancing)A
296 538 :M
-.181(static load balancing)A
296 551 :M
-.219(VLSI)A
296 564 :M
-.151(line-oriented robot model)A
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 495.24 -.24 .24 295.24 495 .24 69 495 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 495.24 -.24 .24 296.24 495 .24 295 495 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 495.24 -.24 .24 522.24 495 .24 296 495 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
69 570.24 -.24 .24 295.24 570 .24 69 570 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
295 570.24 -.24 .24 296.24 570 .24 295 570 @a
-4096 -4095 -1 1 -4094 -4095 1 -4096 -4096 @a
296 570.24 -.24 .24 522.24 570 .24 296 570 @a
70 587 :M
f0_12 sf
-.13(Table I: List of Keywords for the classification of the different approaches to parallel)A
70 600 :M
-.15(computation of robot kinematics and Jacobian.)A
70 663 :M
f5_18 sf
(3)S
91 663 :M
f3_18 sf
3.413 .341(Parallel Kinematics)J
70 708 :M
f5_14 sf
.25(3.1)A
98 708 :M
f3_14 sf
4.11 .411(Forward kinematics)J
91 732 :M
f5_12 sf
-.072(In order to determine the current position and orientation of the end-effector, it is necessary)A
70 750 :M
-.031(to compute matrix multiplications and trigonometric functions. The matrices are 4x4 following)A
endp
%%Page: 4 4
%%BeginPageSetup
initializepage
(D.Henrich; page: 4 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(4)S
70 94 :M
.373 .037(the notation of Denavit-Hartenberg. Altogether, this computation defines a function from the)J
70 112 :M
-.115(joint angle set to the end-effector position and orientation.)A
91 136 :M
-.088(For a manipulator with )A
f0_12 sf
-.107(n)A
f5_12 sf
-.076( joints, there are )A
f0_12 sf
-.107(n)A
f5_12 sf
-.08( matrices to multiply. It is possible to do these )A
f0_12 sf
-.107(n)A
f5_12 sf
(-)S
70 154 :M
.286 .029(1 matrix-multiplications in parallel \(joint level parallelism\). It is also possible to do a matrix-)J
70 172 :M
-.044(multiplication in parallel, since the matrices have 4 rows and columns, which can be multiplied)A
70 190 :M
1.114 .111(independently \(operation level parallelism\). The computation, the trigonometric functions,)J
70 208 :M
-.106(cannot be easily done in parallel. But there are also approaches that go in this direction.)A
91 232 :M
.361 .036(In the following, we present the different approaches to the operation level, computation)J
70 250 :M
-.118(chain level, joint level and task level.)A
91 274 :M
1.982 .198(Hamisi and Fraser exploit the parallelization possibilities on the operation level in)J
70 292 :M
.598 .06([Hamisi89]. They use a transputer network with seven T414s. In this article, the developing)J
70 310 :M
.586 .059(process and design of the MIMD computation, analysis and optimization is shown in detail.)J
70 328 :M
.292 .029(Because of limited transputer communication paths, their system is designed with only seven)J
70 346 :M
-.031(Transputers. Due to the small number of processors, the process is mapped onto the processing)A
70 364 :M
-.086(units \(PEs\) without an extra scheduling mechanism. Since they compute the forward kinematics)A
70 382 :M
.843 .084(incrementally, they compute the forward kinematics by computing the forward and reverse)J
70 400 :M
1.239 .124(Jacobian in parallel. Hence, there is also parallelism on the task level. \(See Section 4 for)J
70 418 :M
-.086(Jacobian.\) For a six degree-of-freedom \(DOF\) manipulator, the forward kinematics is computed)A
70 436 :M
.574 .057(in 8.4 ms.)J
91 460 :M
-.032(Another approach exploiting parallelism on the operation level can be found in [Funda90].)A
70 478 :M
2.93 .293(Funda and Paul test several distinct line-oriented representations of a spatial screw)J
70 496 :M
-.027(displacement. They consider line-based geometry of screws as a valuable tool for transforming)A
70 514 :M
.413 .041(lines \(for example joint axes\) between coordinate frames \(of the joints\). They obtain parallel)J
70 532 :M
.323 .032(solutions with up to 64 PEs and a speed-up by a factor of 12 to 38. One of the conclusions is)J
70 550 :M
-.089(that the point-based representations are simple, compact and computationally very efficient, and)A
70 568 :M
.511 .051(are therefore preferable in real-time applications in robotic control. This approach should be)J
70 586 :M
1.407 .141(studied more closely, as it was never proved that line-oriented approaches are slower on)J
70 604 :M
-.089(special-purpose architectures.)A
91 628 :M
.412 .041(Another article dealing with operation level parallelism is [Fijany92]. Fijany and Bejczy)J
70 646 :M
-.06(offer an architecture that uses parallelization on the joint and operation level. They combine the)A
70 664 :M
.617 .062(computation of forward kinematics with the computation of the Jacobian. The design called)J
70 682 :M
.573 .057(Algorithmically Specialized Parallel Architecture for Robotic Computations \(ASPARC\) is a)J
70 700 :M
-.095(MIMD architecture on the processing unit level and each processing unit is a SIMD architecture)A
70 718 :M
-.077(to exploit the parallelism on the operation level. The speed-up from the joint level parallelism is)A
70 736 :M
-.048(2.3 and the overall speed-up is 9.6 for a six DOF manipulator.)A
91 760 :M
.674 .067(Walker and Cavallaro use an array of CORDIC PEs to compute forward kinematics in)J
70 778 :M
1.883 .188([Walker93]. The coordinate transformation between the single joint frames are done in)J
endp
%%Page: 5 5
%%BeginPageSetup
initializepage
(D.Henrich; page: 5 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(5)S
70 94 :M
1.511 .151(CORDIC PEs as vector rotations, so they exploit operation level parallelism. Since they)J
70 112 :M
-.1(compute all four types of problems at the same time, they make use of task level parallelism and)A
70 130 :M
-.1(achieve total cycle rates of 400 )A
cF f1_12 sf
-.1(m)A
sf
-.1(s.)A
91 154 :M
1.207 .121(There is only one implementation of forward kinematics on a single VLSI chip. This)J
70 172 :M
-.125(architecture is developed in [Leung87]. Leung and Shanblatt exploit parallelism on the operation)A
70 190 :M
.071 .007(level to achieve a cycle rate of about 10 )J
cF f1_12 sf
.007(m)A
sf
.071 .007(s for a six DOF manipulator. They conclude that the)J
70 208 :M
-.133(kinematic computation is no longer the bottleneck, but rather the data communication.)A
91 232 :M
1.643 .164(Barhen uses a scalable hypercube architecture for robot control. Barhen presents an)J
70 250 :M
.157 .016(implementation for robot dynamics but the architecture is also suitable for the computation of)J
70 268 :M
1.53 .153(robot kinematics [Barhen87]. Static and dynamic load balancing techniques are used for)J
70 286 :M
.063 .006(distributing the computation tasks on the processors. In this way he considers the data transfer)J
70 304 :M
.158 .016(caused by the fact that the processors are not equally suited for the tasks since data transfer to)J
70 322 :M
-.048(neighbour processors is cheaper than data transfer to further processors.)A
91 346 :M
.581 .058(Similar to this, Ahmad and Li propose a robot controller based on a multiple arithmetic)J
70 364 :M
1.786 .179(processing unit \(APU\) in [Ahmad87]. They claim that special-purpose architectures are)J
70 382 :M
1.299 .13(expensive to design and inflexible, so they decide to use a MIMD architecture similar to)J
70 400 :M
.324 .032([Hamisi89]. With APUs or microprocessors able to execute floating point instructions in 100)J
70 418 :M
.084 .008(ns, it is possible to design a fast multi-processor network. Also, such a design may be updated)J
70 436 :M
-.082(with faster processor types as they come onto the market. The authors present simulation results)A
70 454 :M
-.064(for a PUMA manipulator computed with a MC 68881 Arithmetic Coprocessor. They ignore the)A
70 472 :M
-.017(communication overhead and get a computation time with 8 APUs of 77 )A
cF f1_12 sf
-.017(m)A
sf
-.017(s with a multiplying)A
70 490 :M
1.512 .151(time of 6 )J
cF f1_12 sf
.151(m)A
sf
1.512 .151(s and a speed-up of 6.9. They use a scheduling algorithm of the type depth-)J
70 508 :M
1.068 .107(first/implicit heuristic search \(DF/IHS\) for the distribution of the computation on multiple)J
70 526 :M
.944 .094(APUs. In [Ahmad89], they modify the DF/IHS algorithm and consider the communication)J
70 544 :M
.876 .088(overhead and even a possible contention. They compare several scheduling algorithms and)J
70 562 :M
-.053(conclude that the depth-first/minimized overhead heuristic search \(DF/MOHS\) is more suitable)A
70 580 :M
.521 .052(for forward kinematics since it minimizes the data transfer. Under the same conditions, they)J
70 598 :M
.8 .08(now get a computation time of 95 )J
cF f1_12 sf
.08(m)A
sf
.8 .08(s. Another result of their simulations is that there is an)J
70 616 :M
1.114 .111(optimal number of processors, since the communication time increases with an increasing)J
70 634 :M
.178 .018(number of processors.)J
91 658 :M
-.018(Pedicone and Johnson present a Concurrent Processor Architecture for Control \(CPAC\) in)A
70 676 :M
.554 .055([Pedicone87]. They design this special purpose architecture with two concurrent processors.)J
70 694 :M
1.221 .122(One is a continuous processing element \(CPE\), the other is a discrete processing element)J
70 712 :M
.171 .017(\(DPE\). The CPE is a vector signal processor for computing the joint angles, the DPE controls)J
70 730 :M
-.043(discrete inputs and outputs. It also monitors, and if necessary intervenes in, the operation of the)A
70 748 :M
1.2 .12(CPE. Since the CPE computes the joint angles for all joints at the same time, this design)J
70 766 :M
-.147(exploits the joint level parallelism.)A
endp
%%Page: 6 6
%%BeginPageSetup
initializepage
(D.Henrich; page: 6 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(6)S
91 94 :M
-.062(Further exploitation of parallelism at the joint level is described in [Lin91]. Lin and Lee try)A
70 112 :M
-.101(to compute all the kinematic and dynamic problems with one architecture. The characteristics of)A
70 130 :M
.786 .079(the kinematic, Jacobian and dynamic algorithms are analyzed and the common features are)J
70 148 :M
.57 .057(extracted. Starting from this, they propose a reconfigurable dual network SIMD with )J
f0_12 sf
.17(n)A
f5_12 sf
.5 .05( PEs.)J
70 166 :M
.731 .073(Thus, they are on the joint level of parallelization. They are able to solve all kinematic and)J
70 184 :M
.237 .024(dynamic problems by changing the configuration of the network by software. Another aim of)J
70 202 :M
-.095(their work is to make the network fault-tolerant.)A
91 226 :M
-.108(An article exploiting the parallelism on the task level besides [Walker93] is [Chen86]. Chen)A
70 244 :M
-.025(et al. present a multiprocessor architecture with a bus network using five PEs as a linear array.)A
70 262 :M
-.026(While a single floating point operation needs 6 )A
cF f1_12 sf
-.026(m)A
sf
-.026(s, their kinematics computation achieves rates)A
70 280 :M
-.024(of 150 Hz. They divide orientation and position computations. With five PEs, there are two for)A
70 298 :M
.503 .05(orientation, two for position and one as the "Programming level". Their system manages the)J
70 316 :M
.301 .03(dynamics computation at the same time. They achieve a relative speed-up from 3 to 5 PEs of)J
70 334 :M
.5(1.36.)A
91 358 :M
1.022 .102(The only articles dealing with scheduling extensively are [Ahmad87] and [Ahmad89].)J
70 376 :M
-.009(However, Ahmad and Li also achieve speed-ups of 7.6, which is less than the predicted speed-)A
70 394 :M
.988 .099(up of 24 calculated by the product of the joint number \(6\) and the number of fine grained)J
70 412 :M
.24 .024(operations done in parallel \(4\). With a higher number of PEs, no further speed-up is possible.)J
70 430 :M
.038 .004(This indicates that scheduling is not necessary for forward kinematics and that parallelism can)J
70 448 :M
-.112(be more easily achieved by exploiting the parallelism on several levels, like in [Fijany92].)A
91 472 :M
.377 .038(None of the speed-ups are higher than 10 in the presented approaches. Parallelization on)J
70 490 :M
.709 .071(the joint level will achieve a maximum speed-up of )J
f0_12 sf
.24(n)A
f5_12 sf
.615 .062( for a manipulator with )J
f0_12 sf
.24(n)A
f5_12 sf
.756 .076( joints. Most)J
70 508 :M
-.016(approaches parallelize on the operation level. On this level, the maximum speed-up is four due)A
70 526 :M
.281 .028(to the representation as 4x4 matrices. Therefore, for common industrial robots like PUMA or)J
70 544 :M
.109 .011(Stanford arm, there will be a speed-up of less than 4 )J
f0_12 sf
(n)S
f5_12 sf
.122 .012(. Since most of the articles address only)J
70 562 :M
-.109(one level of parallelism the actual speed-up is much less.)A
70 597 :M
f5_14 sf
.25(3.2)A
98 597 :M
f3_14 sf
4.241 .424(Reverse Kinematics)J
91 621 :M
f5_12 sf
1.013 .101(The task of reverse kinematics is to compute the joint angle set from the position and)J
70 639 :M
1.22 .122(orientation of the end-effector. This is the inverse of the function defined in the previous)J
70 657 :M
-.08(section. There are several ways to compute this inverse function as described by Lee and Chang)A
70 675 :M
.878 .088(in [Lee87]: inverse transform \(closed form\), screw algebra, dual matrices, dual quaternion,)J
70 693 :M
.409 .041(iterative, and the geometric approach. In the following, we present the iterative form and the)J
70 711 :M
1.459 .146(closed form, where the closed form references are classified as to whether they use the)J
70 729 :M
-.126(CORDIC architecture or not.)A
91 753 :M
.081 .008(. The iterative way, as proposed by [Tsai85], has not been further investigated for parallel)J
70 771 :M
.416 .042(processing. This is because the iterative solution requires more computations than the closed)J
endp
%%Page: 7 7
%%BeginPageSetup
initializepage
(D.Henrich; page: 7 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(7)S
70 94 :M
.43 .043(form. Additionally, neither guarantees convergence nor is it suited for parallelizing since the)J
70 112 :M
-.081(next iteration step can be computed as soon as the previous one has been finished.)A
91 136 :M
.65 .065(For the most common industrial robots like PUMA, Stanford, ASEA or MINIMOVER,)J
70 154 :M
-.029(there is the solution for the joint angle set in closed form. In this case, the computation is much)A
70 172 :M
.101 .01(easier because the problems of existence and uniqueness are solved. In [Lee87], the necessary)J
70 190 :M
.8 .08(computations are given: multiplications, additions, square root, and transcendental function)J
70 208 :M
.123 .012(operations. All these are floating point operations, and so the main goal should be to speed up)J
70 226 :M
-.037(the computation of these floating point operations rather than to speed up the matrix operations)A
70 244 :M
-.104(as for forward kinematics. They propose that a CORDIC architecture should do the computation)A
70 262 :M
.479 .048(work, and they present an architecture with a latency time of 720 )J
cF f1_12 sf
.048(m)A
sf
.479 .048(s and a new computation)J
70 280 :M
1.328 .133(result every 40 )J
cF f1_12 sf
.133(m)A
sf
1.328 .133(s. They decompose the joint angle equations manually in computational)J
70 298 :M
1.626 .163(modules, which are executed by a CORDIC processor. Then, the acyclic directed graph)J
70 316 :M
.383 .038(resulting from the data dependencies is balanced by inserting delay buffers. By using special)J
70 334 :M
.525 .053(tapped-delay-line-buffers, the number of buffers resulting in a maximum pipelined design is)J
70 352 :M
(reduced.)S
91 376 :M
.278 .028(In the same year, Wang and Butner presented a new architecture in [Wang87], for which)J
70 394 :M
1.056 .106(they also used a CORDIC subsystem, which computes new results every 50 )J
cF f1_12 sf
.106(m)A
sf
1.056 .106(s. A special)J
70 412 :M
.353 .035(purpose processor is designed to do the computational work. Up to four of these can work in)J
70 430 :M
2.4 .24(parallel, and hence parallelize on the highest level. The processors can be controlled)J
70 448 :M
1.049 .105(independently, so that besides reverse kinematics, other computations can be done on idle)J
70 466 :M
1.473 .147(processors. A minimal configuration consists of one processor and can control up to ten)J
70 484 :M
.573 .057(synchronized axes. The maximal configuration has four processors and can control up to 40)J
70 502 :M
1.261 .126(axes. Since there are three separate buses and three independent data paths in the special)J
70 520 :M
1.265 .126(purpose processor, it parallelizes the vector additions and multiplications \(operation level)J
70 538 :M
.479 .048(parallelism\). But there is a CORDIC subsystem which does the expensive floating point and)J
70 556 :M
-.142(trigonometric evaluations efficiently.)A
91 580 :M
.631 .063(The authors of [Harber88] use the results of [Lee87] and enhance them to construct the)J
70 598 :M
.636 .064(system on a single VLSI chip. The original work has been modified to allow the use of bit-)J
70 616 :M
-.053(serial CORDIC processors. The computation time is reduced and the throughput of the pipeline)A
70 634 :M
-.02(is increased, since normalization of the output of a CORDIC processor is avoided. They do the)A
70 652 :M
.387 .039(normalization not as usual done by introducing additional CORDIC iterations, but by adding)J
70 670 :M
-.088(stand-alone bit-serial constant multipliers, which do this in less time.)A
91 694 :M
1.587 .159(Another architecture using CORDIC processors is the one by Walker and Cavallaro)J
70 712 :M
.557 .056([Walker93]. They use an array of 16 CORDIC processors as a systolic array and combine it)J
70 730 :M
2.203 .22(with a general-purpose processor. They compute the reverse kinematics in parallel by)J
70 748 :M
-.086(computing the Jacobian matrix and its pseudoinverse in parallel. Then they use a \324resolved-rate\325)A
70 766 :M
-.108(approach to compute the joint velocities from the pseudoinverse Jacobian in the general-purpose)A
endp
%%Page: 8 8
%%BeginPageSetup
initializepage
(D.Henrich; page: 8 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(8)S
70 94 :M
1.174 .117(processor. Therefore, matrix-vector multiplications have to be executed. The desired joint)J
70 112 :M
-.109(angles can be obtained from the current joint velocities and joint angles. The array is also able to)A
70 130 :M
-.071(perform the computation of forward kinematics. Thus, all kinematic and Jacobian computations)A
70 148 :M
-.072(can be done by this architecture. They have a higher flexibility than [Wang87] because they use)A
70 166 :M
-.066(the same systolic array for multiple algorithms and, thus, the CORDIC processors are no longer)A
70 184 :M
.225 .023(a part of one pipeline but of many. It is more suitable than most approaches since they do not)J
70 202 :M
1.314 .131(depend on an existing closed form solution and their architecture is able to manage non-)J
70 220 :M
.008 .001(redundant manipulators. They implement the systolic array in VLSI since they achieve shorter)J
70 238 :M
.41 .041(computation times with it. Using this, they exploit the parallelism at the task level and at the)J
70 256 :M
-.109(operation level.)A
91 280 :M
-.002(The authors of [Ahmad87] and [Ahmad89] propose a MIMD architecture with static load)A
70 298 :M
-.103(balancing. They compare different scheduling algorithms and compute the reverse kinematics in)A
70 316 :M
.413 .041(about 400 )J
cF f1_12 sf
.041(m)A
sf
.413 .041(s. They use a scalable number of arithmetic processing units \(APU\), so that they)J
70 334 :M
.769 .077(can adapt to closed form solutions for different manipulators independent of the number of)J
70 352 :M
-.065(joints. As mentioned in Section 3.1, they parallelize at the computation chain level. The authors)A
70 370 :M
.567 .057(Zhang and Paul also apply the MIMD processing paradigm in the references [Zhang90] and)J
70 388 :M
1.764 .176([Zhang91]. They use the closed form solution to compute the reverse kinematics. They)J
70 406 :M
-.016(extrapolate the joint angles for the current computation from that from earlier computations, in)A
70 424 :M
1.954 .195(order to remove the data dependencies between the single equations. With this loss of)J
70 442 :M
.43 .043(dependency the equations can be easily done in parallel. Not only do they try to increase the)J
70 460 :M
.338 .034(data throughput as in [Lee87], but also to reduce the latency time. They use a multiprocessor)J
70 478 :M
-.02(system with one computing processor for each joint and one supervisor. They achieve a speed-)A
70 496 :M
-.062(up of approximately 2.)A
91 520 :M
.415 .041(For parallel manipulators, Gosselin exploits the mechanical architectur to obtain parallel)J
70 538 :M
.06 .006(computational algorithms [Gosselin96]. For the reverse kinematics, he obtains an independent)J
70 556 :M
1.142 .114(equation for each joint computing the length of each manipulator with given position and)J
70 574 :M
-.065(orientation of the platform. Thus, this is joint level parallelism. He achieves a theoretical speed-)A
70 592 :M
.293 .029(up of )J
f0_12 sf
.163(n)A
f5_12 sf
(.)S
91 616 :M
.054 .005(The last article [Nabhan95] in this section deals with the general parallelization of robotic)J
70 634 :M
.402 .04(computational tasks. Nabhan and Zomaya use a graph-based approach to map computational)J
70 652 :M
.694 .069(tasks on a MIMD architecture. Their algorithm automatically generates the task graph for a)J
70 670 :M
2.367 .237(given architecture. The algorithm considers the network topology and communication)J
70 688 :M
.56 .056(constraints, making it scalable for a different number of processors. The whole parallelizing)J
70 706 :M
.871 .087(process is done automatically: For a chosen robot manipulator, the computational model is)J
70 724 :M
.324 .032(generated and simplified; a task graph is generated, compressed and the tasks are assigned to)J
70 742 :M
.341 .034(the processors. They develop a special annealing algorithm, since the dynamic-highest-level-)J
70 760 :M
-.078(first/most-immediate-successors-first \(DHLF/MISF\) is time consuming.)A
endp
%%Page: 9 9
%%BeginPageSetup
initializepage
(D.Henrich; page: 9 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
293 810 :M
f5_12 sf
(9)S
91 94 :M
-.091(Other computation methods than the iterative or the closed form are listed in [Lee87]. None)A
70 112 :M
-.081(seem to be interesting enough to encourage further research work.)A
70 169 :M
f5_18 sf
(4)S
91 169 :M
f3_18 sf
2.507 .251(Parallel Jacobian)J
70 214 :M
f5_14 sf
.25(4.1)A
98 214 :M
f3_14 sf
3.185 .318(Forward Jacobian)J
91 238 :M
f5_12 sf
.662 .066(The computation of the forward Jacobian is similar to the forward kinematics, so many)J
70 256 :M
-.001(references deal with both problems. The velocity of the end-effector should be computed from)A
70 274 :M
.785 .078(the joint rates. This requires coordinate transformations from one joint to every other joint.)J
70 292 :M
-.096(Coordinate transformations require, for example, the multiplication of matrices as introduced by)A
70 310 :M
-.088(Denavit and Hardenberg.)A
91 334 :M
-.106(There are three main approaches to the forward Jacobian: General-purpose architectures not)A
70 352 :M
.922 .092(specially designed for the problem of robot control, spezialized architectures with general-)J
70 370 :M
.189 .019(purpose processors or arithmetic units, and architectures especially designed for robot control)J
70 388 :M
-.061(with microprocessors that are not off-the-shelf.)A
91 412 :M
.536 .054(In the following, we will discuss these three approaches of robot arm control. The early)J
70 430 :M
.257 .026(approaches using general-purpose architectures use only scheduling approaches. Luh and Lin)J
70 448 :M
2.177 .218(divided the entire task into subtasks in [Luh82] and rearranged them to distribute the)J
70 466 :M
.111 .011(computational tasks efficiently on multiple PEs. They ignored the data transfer time since this)J
70 484 :M
1.022 .102(consumes less time then their simulated time of 50 )J
cF f1_12 sf
.102(m)A
sf
1.022 .102(s per multiplication. They assumed a)J
70 502 :M
-.071(MIMD architecture with general-purpose PEs and they assigned one PE to each joint exploiting)A
70 520 :M
-.038(parallelism at the joint level. Although they mainly consider dynamic computations, their work)A
70 538 :M
.683 .068(is adaptable for Jacobian computations since the main issue of their work is the design of a)J
70 556 :M
2.213 .221(near-optimal scheduling algorithm. This work is continued by Kasahara and Narita in)J
70 574 :M
.14 .014([Kasahara85] who use common 8086 and 8087 processors and a scalable MIMD architecture.)J
70 592 :M
-.069(They also consider the dynamics problem, but their results in scheduling and load balancing are)A
70 610 :M
.023 .002(also applicable for the forward Jacobian. They employ two scheduling algorithms: DF/IHS, as)J
70 628 :M
1.067 .107(discussed in Section 3.1, and Critical Path / Most Immediate Successors First \(CP/MISF\).)J
70 646 :M
-.084(They recommend DF/IHS since with CP/MISF the optimality and accuracy of the result can not)A
70 664 :M
.329 .033(be guaranteed. Another approach based on general-purpose architectures was investigated by)J
70 682 :M
.093 .009(Kokusho et al. in [Kokusho95]. In a multi-transputer network, they use a double-layered load)J
70 700 :M
.865 .086(distribution with a DF/IHS for the logical layer and a Distributed Problem Solver for Task)J
70 718 :M
.113 .011(Scheduling \(DPSTS\) for the physical layer. This is because the DF/IHS cannot consider time-)J
70 736 :M
.719 .072(delay due to inter-processor communication and the cost for message routings. The DPSTS)J
70 754 :M
1.234 .123(modifies and optimizes the schedule received from DF/IHS according to the architectural)J
70 772 :M
.273 .027(features. The DPSTS is implemented as a part of the firmware on each PE. Finally, an article)J
endp
%%Page: 10 10
%%BeginPageSetup
initializepage
(D.Henrich; page: 10 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(10)S
70 94 :M
-.016(handling the parallel processing on general MIMD architectures is [Nabhan95] by Nabhan and)A
70 112 :M
-.084(Zomaya. They exploit the parallelism on the level of the computation chain using a graph-based)A
70 130 :M
-.045(approach that considers the communication overhead, congestion possibilities, and the network)A
70 148 :M
-.052(topology. Therefore, it is independent of the concrete hardware implementation. They achieved)A
70 166 :M
.07 .007(computation times for the forward Jacobian in the range of 50 )J
cF f1_12 sf
.007(m)A
sf
.07 .007(s and a speed-up of 1.5 with 4)J
70 184 :M
1.23 .123(PEs for a PUMA560. Thus, they showed that it is not necessary to develop an expensive)J
70 202 :M
2.193 .219(special-purpose architecture or even special PEs to solve the forward Jacobian. These)J
70 220 :M
.44 .044(approaches with general-purpose architectures can be scalable and a change in the algorithm)J
70 238 :M
-.071(does not cause any change in the hardware.)A
91 262 :M
1.681 .168(As mentioned in Section 3.1, Hamisi and Fraser described the implementation on a)J
70 280 :M
-.044(network of transputers in [Hamisi89]. This article covers another approach: They use a special-)A
70 298 :M
3.1 .31(purpose network topology and general-purpose PEs. Therefore, they can use cheap)J
70 316 :M
-.027(components to adapt their hardware to the problem of robot control and exploit the potential of)A
70 334 :M
-.107(parallelism in the algorithm. The main difference from the previously discussed approaches is to)A
70 352 :M
2.327 .233(adapt the specialization of the network topology to the problems of robot control. In)J
70 370 :M
-.005([Hamisi89], the control itself is done by computing the actual position of the end-effector with)A
70 388 :M
1.248 .125(forward kinematics, and at the same time computing the forward Jacobian. From that the)J
70 406 :M
.425 .042(reverse Jacobian is calculated to compute the necessary joint rates from the difference of the)J
70 424 :M
.623 .062(actual and desired positions of the end-effector in order to correct the position. The level of)J
70 442 :M
.207 .021(parallelism is the joint level, since it assigns a PE to each column of the Jacobian matrix. The)J
70 460 :M
.036 .004(columns of the Jacobian describe the corresponding joint rates. There is also parallelism at the)J
70 478 :M
.509 .051(task level since Hamisi and Fraser compute forward kinematics and the Jacobian in parallel.)J
70 496 :M
.342 .034(They achieve a computation time of 6.1 ms and a speed-up of 2.9 for a six DOF manipulator)J
70 514 :M
2.115 .211(with 6 PEs. A second approach uses common PEs with no special assumptions and a)J
70 532 :M
.278 .028(specialized hardware and software architecture [Lin91]. Contrary to [Hamisi89], Lin and Lee)J
70 550 :M
.247 .025(do not use a MIMD but a SIMD topology. They assume that advanced robot control schemes)J
70 568 :M
.198 .02(require all four kinematics and Jacobian problems and additionally the dynamics problem. So)J
70 586 :M
-.006(they designed a machine providing the flexibility to solve all problems while maintaining high)A
70 604 :M
-.057(efficiency. To achieve this, they study these features of the robot control problems and describe)A
70 622 :M
.024 .002(a parallel architecture that matches the common features. They exploit parallelism at the joint-)J
70 640 :M
1.381 .138(level using identical PEs for each joint and two reconfigurable networks. They show the)J
70 658 :M
.582 .058(implementation of dynamics computations, but as the authors point out, it is also suited for)J
70 676 :M
-.02(kinematics and Jacobian computation. In [Zomaya92], Zomaya presents different architectures)A
70 694 :M
-.106(to implement parallel Jacobian computation. In all architectures, the parallelism at the joint level)A
70 712 :M
.204 .02(is exploited using T414 and T800 transputers. Various network schemes to minimize the data)J
70 730 :M
-.084(transfer between the PEs are investigated. As a result, the minimization of data transfer between)A
70 748 :M
-.087(the PEs is more important than a uniform load of each PE. With an architecture with 7 PEs for a)A
70 766 :M
.546 .055(six DOF manipulator, a computation time of 0.38 )J
cF f1_12 sf
.055(m)A
sf
.546 .055(s and a speed-up of 5.5 is achieved. The)J
endp
%%Page: 11 11
%%BeginPageSetup
initializepage
(D.Henrich; page: 11 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(11)S
70 94 :M
.007 .001(article by Gosselin [Gosselin96] presents no processing paradigm, but since the algorithms for)J
70 112 :M
1.334 .133(reverse kinematics and forward Jacobian are presented with each PE doing the same, we)J
70 130 :M
-.052(suggest the SIMD topology. Hence, this reference with a speed-up of )A
f0_12 sf
-.063(n)A
f5_12 sf
-.049( is classified as one with)A
70 148 :M
-.05(a special-purpose network topology and general-purpose PEs.)A
91 172 :M
1.619 .162(One of the first articles using systolic networks to compute the forward Jacobian is)J
70 190 :M
.844 .084([Orin87] by Orin, Olson and Chao. Orin and Schrader have published a serial algorithm to)J
70 208 :M
.295 .03(compute the Jacobian in [Orin84]. The difficulties in implementing in real time led them to a)J
70 226 :M
-.036(parallel approach. They discuss a serial, a pipeline and a parallel algorithm for the computation)A
70 244 :M
.112 .011(of the Jacobian. They conclude that it is possible to reduce the computation time from O\()J
f0_12 sf
(n)S
f5_12 sf
.079 .008(\) to)J
70 262 :M
.252(O\(log\312)A
f0_12 sf
.292(n)A
f5_12 sf
.792 .079(\), and for n\312=\3127, to achieve a speed-up of 2.35 with 8 PEs with a parallel algorithm)J
70 280 :M
.163 .016(exploiting the joint level parallelism. The pipeline algorithm can reduce the computation time)J
70 298 :M
.468 .047(and therefore improve data throughput, but the latency time is the same as in the serial case.)J
70 316 :M
.675 .067(They introduce additional redundant computations in the parallel algorithm to achieve local)J
70 334 :M
.536 .054(communication. They use the hypercube topology, since the single matrix operations can be)J
70 352 :M
.372 .037(simply mapped on it. Furthermore, it is possible to propagate a result in log\312)J
f0_12 sf
.127(n)A
f5_12 sf
.225 .022( steps to )J
f0_12 sf
.127(n)A
f5_12 sf
.374 .037( PEs,)J
70 370 :M
.493 .049(so that the desired O\(log\312)J
f0_12 sf
.161(n)A
f5_12 sf
.512 .051(\) time could be achieved. After the algorithm and the architecture)J
70 388 :M
.777 .078(were designed, they designed a robotics processor on a VLSI chip with four ports and four)J
70 406 :M
.255 .025(internal buses based on a Harvard architecture. In [Yeung88] and [Yeung89], Yeung and Lee)J
70 424 :M
.9 .09(compared the Jacobian computation on the uniprocessor, SIMD, and systolic architectures.)J
70 442 :M
2.096 .21(They offer two possibilities for the systolic case: a linear pipeline with 18 PEs and a)J
70 460 :M
(computation time of O\()S
f0_12 sf
(n)S
f5_12 sf
(\) or a parallel pipeline with O\()S
f0_12 sf
(n)S
f5_12 sf
(\312log\312)S
f0_12 sf
(n)S
f5_12 sf
.006 .001(\) PEs and a computation time of)J
70 478 :M
.525 .053(3 cycles. The systolic architectures are completely implemented in VLSI. The main point of)J
70 496 :M
-.052(these four articles on systolic architectures and their implementation in VLSI is the fact that the)A
70 514 :M
1.408 .141(Jacobian computation is not only faster because of faster computation times of primitive)J
70 532 :M
1.528 .153(operations and communication times in a systolic array, but also because the algorithms)J
70 550 :M
1.863 .186(implementable in VLSI are in O\(log\312)J
f0_12 sf
.536(n)A
f5_12 sf
1.761 .176(\). In [Sadayappan89] and in the later publication)J
70 568 :M
.71 .071([Orin91], Sadayappan, Ling, Olson and Orin introduced the idea of parallelism on different)J
70 586 :M
1.724 .172(levels. They designed an architecture on two levels. They developed a Robotics Vector)J
70 604 :M
.541 .054(Processor \(RVP\), which contains three multipliers and three adders controlled as a SIMD to)J
70 622 :M
.727 .073(exploit parallelism on the operation level, since the main task was to multiply matrices and)J
70 640 :M
.285 .028(vectors. The RVPs themselves are controlled as MIMD, so that their task can be presented in)J
70 658 :M
.135 .014(the usual task graph for applying schedule optimization. Hence, the level exploited here is the)J
70 676 :M
-.012(computation chain level. Two further references, [Walker93] and [Hemkumar94], consider the)A
70 694 :M
.224 .022(implementation of CORDIC arithmetic for Jacobian computation. The CORDIC arithmetic is)J
70 712 :M
-.04(implemented in VLSI. In [Walker93], the architecture is systolic, since that is the most suitable)A
70 730 :M
.675 .067(for CORDIC processors. Hemkumar and Cavallaro consider the difficulty of computing the)J
70 748 :M
1.271 .127(forward and reverse Jacobian for redundant manipulators. See Section 4.2. They also use)J
endp
%%Page: 12 12
%%BeginPageSetup
initializepage
(D.Henrich; page: 12 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(12)S
70 94 :M
.571 .057(CORDIC PEs to combine them in a systolic array to form a systolic machine, which is then)J
70 112 :M
-.139(implemented in VLSI.)A
91 136 :M
.078 .008(Comparing the different approaches, it seems that there are advantages and disadvantages)J
70 154 :M
-.02(for all of them. But since the general-purpose PEs in special-purpose interconnection networks)A
70 172 :M
.139 .014(achieve a computation time of 0.38 )J
cF f1_12 sf
.014(m)A
sf
.139 .014(s in [Zomaya92], making real-time control possible, it is)J
70 190 :M
-.058(questionable whether the further speed-up of VLSI implementation justifies its inflexibility. On)A
70 208 :M
-.044(the other hand, the exploitation of the operation level is only valuable in VLSI implementation,)A
70 226 :M
-.094(since the communication overhead would otherwise be too big.)A
70 261 :M
f5_14 sf
.25(4.2)A
98 261 :M
f3_14 sf
3.369 .337(Reverse Jacobian)J
91 285 :M
f5_12 sf
-.09(The problem of the reverse Jacobian is to compute the joint velocities from the desired end-)A
70 303 :M
-.001(effector velocity. There are more computations to be made than for the former three problems.)A
70 321 :M
-.141(The computations are matrix multiplication, vector addition, matrix-vector multiplication and the)A
70 339 :M
-.076(computation of the inverse or pseudo-inverse of the Jacobian.)A
91 363 :M
.177 .018(For non-redundant manipulators, the computation of the reverse Jacobian is the inversion)J
70 381 :M
-.013(of the Jacobian matrix computed for the forward Jacobian. The articles [Hamisi89, Zomaya92,)A
70 399 :M
.874 .087(Fujioka93, Kokusho95] consider this case. In the redundant case, where the inverse matrix)J
70 417 :M
2.15 .215(does not exist, a pseudo-inverse must be computed. This case is treated in [Chang89,)J
70 435 :M
1.63 .163(Walker93, Hemkumar94, Maciejewski94]. There are two equations to compute the joint)J
70 453 :M
.769 .077(velocities using the pseudo-inverse: one with a projection of an arbitrary vector on the null)J
70 471 :M
.063 .006(space of the Jacobian, the other using some secondary criterion to fix the arbitrary vector. The)J
70 489 :M
-.076(first equation is the faster one in most references, since there are less operations to do.)A
91 513 :M
-.013(The first article considering the singularities in robot work space is [Chang89]. Chang and)A
70 531 :M
.674 .067(Lee concentrate on the problem of numerical instabilities in the computation in the pseudo-)J
70 549 :M
.975 .097(inverse of the Jacobian. They use a residue arithmetic to avoid floating point errors. Their)J
70 567 :M
-.056(parallelization is hence on three levels: they use a data-driven processor array for exploiting the)A
70 585 :M
-.045(operation level parallelism, a linear array as a pipeline to exploit the joint level parallelism, and)A
70 603 :M
-.005(separate processing units for any modulus in the residue arithmetic as a very fine grained level)A
70 621 :M
-.045(under the operation level. The number of moduli is in the range of two to ten, depending on the)A
70 639 :M
-.146(desired numerical precision. Especially exploiting parallelism in the residue arithmetic makes the)A
70 657 :M
.192 .019(parallel design valuable. The theoretical speed-up is 4)J
0 -3 rm
(.)S
0 3 rm
f0_12 sf
.08(m)A
f5_12 sf
0 -3 rm
(.)S
0 3 rm
f0_12 sf
.056(n)A
f5_12 sf
.127 .013(, where )J
f0_12 sf
.056(n)A
f5_12 sf
.127 .013( is the joint number and )J
f0_12 sf
(m)S
70 675 :M
f5_12 sf
.341 .034(the number of moduli. For a six DOF manipulator the speed-up is about 120. They achieve a)J
70 693 :M
-.107(latency time of 7 )A
cF f1_12 sf
-.107(m)A
sf
-.107(s for a 12-DOF manipulator.)A
91 717 :M
2.086 .209(The architecture proposed by Walker and Cavallaro [Walker93] is also capable of)J
70 735 :M
1.298 .13(computing the pseudo-inverse Jacobian since their CORDIC array is able to compute the)J
70 753 :M
-.05(singular value decomposition \(SVD\). With this, the pseudo-inverse can be easily computed. As)A
endp
%%Page: 13 13
%%BeginPageSetup
initializepage
(D.Henrich; page: 13 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(13)S
70 94 :M
.032 .003(mentioned in Section 3, they exploit parallelism at the task level, and, similar to [Chang89], at)J
70 112 :M
-.082(the operation level by computing the rows of the pseudo-inverse Jacobian.)A
91 136 :M
-.083(A further approach for redundant manipulators is discussed by Hemkumar and Cavallaro in)A
70 154 :M
.864 .086([Hemkumar94]. They use an array of CORDIC PEs to exploit parallelism on the operation)J
70 172 :M
1.657 .166(level. Different implementations of CORDIC PEs are investigated to speed-up the SVD)J
70 190 :M
1.681 .168(computation and matrix multiplication. The use of CORDIC leads to an operation level)J
70 208 :M
.047 .005(parallelism. In contrast to [Walker93], they do not use an array of CORDIC PEs but a special-)J
70 226 :M
.223 .022(purpose topology. The latest work investigating parallel computations of reverse Jacobian for)J
70 244 :M
.655 .066(redundant manipulators is [Maciejewski94]. Maciejewski and Reagin achieve a speed-up of)J
70 262 :M
.936 .094(3.61 with four digital signal processors \(DSP\) for a seven DOF manipulator \(CESAR\). As)J
70 280 :M
-.05(opposed to other approaches, they exploit parallelism at the joint level, since they calculate two)A
70 298 :M
.2 .02(columns of the SVD in each PE. Each of four PEs communicate with two other PEs since the)J
70 316 :M
-.086(PEs are lined up in a linear array.)A
91 340 :M
.525 .052(An approach not considering singularities in the manipulator work space is presented in)J
70 358 :M
.115 .011([Hamisi89]. They compute the reverse Jacobian as an inversion of the forward Jacobian using)J
70 376 :M
.07 .007(Gaussian elimination. Their transputer cluster exploits joint level parallelism since each of the)J
70 394 :M
.713 .071(six PEs calculates a column needed for a six DOF manipulator. They use the MIMD as the)J
70 412 :M
.222 .022(processing paradigm, though they do not use a scheduling algorithm. Since they use a special)J
70 430 :M
.657 .066(purpose interconnection topology, their approach is not scalable without complete redesign.)J
70 448 :M
.579 .058(Zomaya uses a Transputer network like Hamisi and Fraser in [Zomaya92]. He discusses the)J
70 466 :M
.037 .004(methods for parallel inversion. As a result, he concludes that the Gaussian elimination method)J
70 484 :M
-.002(is faster then the Gauss-Jordan method. Although the speed-ups with Gauss-Jordan are higher.)A
70 502 :M
-.039(The computation time for a six DOF is 0.64 )A
cF f1_12 sf
-.039(m)A
sf
-.039(s and the speed-up is 2.2 with 3 PEs.)A
91 526 :M
.353 .035(An interesting approach is [Fujioka93]. Fujioka and Kameyama design a PE using VLSI)J
70 544 :M
-.056(techniques. They combine two adders and two multipliers on each PE to exploit operation level)A
70 562 :M
-.023(parallelism. Since each PE has a switching unit for its input and output, they can be configured)A
70 580 :M
.053 .005(in different topologies for different problems. E.g., for vector addition, they can be configured)J
70 598 :M
.353 .035(as a linear array, and for matrix multiplication they can be configured as an two-dimensional)J
70 616 :M
.582 .058(array. Since the PEs are reconfigurable, the architecture is scalable. Fujioka and Kameyama)J
70 634 :M
.915 .091(achieve a latency time of less than 32 )J
cF f1_12 sf
.091(m)A
sf
.915 .091(s for a twelve DOF redundant manipulator. As the)J
70 652 :M
.965 .097(number of PEs increases with increasing number of controlled joints, they also exploit the)J
70 670 :M
-.139(parallelism of joint level.)A
91 694 :M
1.15 .115(Finally, Kokusho et al. discuss the use of scheduling algorithms and load-distribution)J
70 712 :M
.194 .019(mechanisms for MIMD architectures for computing robot control in [Kokusho95]. Since they)J
70 730 :M
.198 .02(use scheduling algorithms, it is obvious that they exploit parallelism at the computation chain)J
70 748 :M
-.013(level. They achieve speed-ups up to 3 with 25 PEs for the Stanford arm. They assume a square)A
70 766 :M
-.097(array as the interconnection topology.)A
endp
%%Page: 14 14
%%BeginPageSetup
initializepage
(D.Henrich; page: 14 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(14)S
91 94 :M
.702 .07(As presented, there are approaches using all levels of parallelism. The most promising)J
70 112 :M
-.037(approaches seem to be the ones using parallelism on the joint and operation levels, whereas the)A
70 130 :M
1.496 .15(computation chain level suffers from low efficiency. As shown in [Zomaya92], for non-)J
70 148 :M
.28 .028(redundant manipulators it is neither necessary to implement the algorithm in VLSI nor to use)J
70 166 :M
.085 .009(special-purpose PEs like CORDIC. Even the most complex problem of robot position control,)J
70 184 :M
-.047(the reverse Jacobian, can be computed in real-time using appropriate parallel architectures with)A
70 202 :M
.131 .013(general-purpose PEs. For redundant manipulators, the additional computation work requires a)J
70 220 :M
-.05(parallelization on many levels like in [Chang89], but this case seems to be solvable in real-time)A
70 238 :M
.168(also.)A
70 295 :M
f5_18 sf
(5)S
91 295 :M
f3_18 sf
.17(Summary)A
91 329 :M
f5_12 sf
.236 .024(We have shown that the parallel processing approaches of robot kinematics and Jacobian)J
70 347 :M
-.012(render short computation times. Hence, the architectures and algorithms developed for parallel)A
70 365 :M
.111 .011(robot control allow real-time applications, since common latency times are less than 50 )J
cF f1_12 sf
.011(m)A
sf
.111 .011(s for)J
70 383 :M
-.063(all four problems of robot control. This is far below the cycle rates of a manipulator \(a few ms\).)A
70 401 :M
2.205 .22(There is still a great demand for faster computation, since with increasing number of)J
70 419 :M
1.043 .104(manipulator joints, e.g., for a replica of the human hand or for mechanically stiff, parallel)J
70 437 :M
-.044(manipulators, only parallel approaches can calculate this in about the same time as for six DOF)A
70 455 :M
-.091(manipulators [Gosselin96]. The other main reason for perpetual demand on more computational)A
70 473 :M
.892 .089(power is the wish to reduce positioning errors through further reduction of the sample rate)J
70 491 :M
-.095([Zhang91, Khosla87]. Other incentives for reducing computation time are the skills of advanced)A
70 509 :M
.456 .046(robots. Tactile and vision sensors make it possible to avoid moving obstacles, but to do this,)J
70 527 :M
-.083(the robot kinematics has to be fast enough to evade or stop effectively [Khosla87].)A
91 551 :M
.311 .031(The individual articles reflect the variety of possible approaches. Our list of keywords in)J
70 569 :M
.134 .013(Table I serves as an overview of these approaches. The conclusion as to which architecture or)J
70 587 :M
.418 .042(parallelization is best cannot be made. There are too many advantages and disadvantages for)J
70 605 :M
-.001(each approach. There is no such thing as a universal parallel robot control architecture, though)A
70 623 :M
-.005(some authors claim this. There is still a wide field of research to be done for developing small,)A
70 641 :M
-.057(cheap, flexible, fast robot control systems with parallel processing.)A
70 698 :M
f3_18 sf
.67(Acknowledgements)A
91 732 :M
f5_12 sf
.403 .04(The work was performed at the Institute for Real-Time Computer Systems and Robotics)J
70 750 :M
2.073 .207(\(IPR\) under Prof. Dr.-Ing. U. Rembold, Prof. Dr.-Ing. H. W\232rn, and Prof. Dr.-Ing. R.)J
endp
%%Page: 15 15
%%BeginPageSetup
initializepage
(D.Henrich; page: 15 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(15)S
70 94 :M
-.059(Dillmann at University of Karlsruhe. We wish to thank Albert Y. Zomaya for his interest in our)A
70 112 :M
-.023(work. Many thanks to Stefanie Grupp for proof-reading.)A
70 169 :M
f3_18 sf
.675(References)A
70 203 :M
f5_12 sf
-.164([Ahmad87])A
155 203 :M
-.113(S. Ahmad & B. Li: Optimal design of multiple arithmetic processor-based)A
155 221 :M
-.017(robot controllers. Proc. 1987 IEEE Int. Conf. on Robotics and Automation,)A
155 239 :M
.813 .081(pp. 660-663, 1987.)J
155 257 :M
f3_12 sf
.124 .012(Keywords: )J
f5_12 sf
.096 .01(forward and reverse kinematics, computation chain level, one)J
155 275 :M
-.099(dimensional array, MIMD, static load balancing, scalable.)A
70 299 :M
-.164([Ahmad89])A
155 299 :M
-.072(S. Ahmad & B. Li: Robot control computation in microprocessor systems)A
155 317 :M
-.105(with multiple arithmetic processors using a modified DF/IHS scheduling)A
155 335 :M
.084 .008(algorithm. IEEE Trans. on Systems, Mman, and Cybernetics, Vol. 19, No.)J
155 353 :M
.212 .021(5, September/October, pp. 1167-1178, 1989.)J
155 371 :M
f3_12 sf
.124 .012(Keywords: )J
f5_12 sf
.096 .01(forward and reverse kinematics, computation chain level, one)J
155 389 :M
-.099(dimensional array, MIMD, static load balancing, scalable.)A
70 413 :M
-.071([Barhen87])A
155 413 :M
-.088(J. Barhen: Hypercube ensembles: an architecture for intelligent robots.)A
155 431 :M
-.017(Computer architectures for robotics and automation.\(Eds. J. H. Graham\),)A
155 449 :M
.147 .015(Gordon and Breach science publishers. New York, pp.195-236, 1987.)J
155 467 :M
f3_12 sf
.251 .025(Keywords: )J
f5_12 sf
.222 .022(forward kinematics, dynamics, computation chain level,)J
155 485 :M
-.095(hypercube, MIMD, dynamic load balancing, static load balancing, scalable.)A
70 509 :M
-.098([Capriot91])A
155 509 :M
-.028(F. D. Capriot & S. S. Khanuja & M. M. Stanisic & O. Duta: A singularity)A
155 527 :M
-.107(free six degree of freedom manipulator. in Advances in robot kinematics by)A
155 545 :M
-.008(S. Stifter & Jadran Lenarcic, Springer-Verlag/Wien, pp. 128-135, 1991.)A
155 563 :M
f3_12 sf
2.08 .208(Keywords: )J
f5_12 sf
.413(General.)A
70 587 :M
-.04([Chang89])A
155 587 :M
-.044(P. R. Chang & C. S. G. Lee: Residue arithmetic VLSI array architecture for)A
155 605 :M
-.078(manipulator pseudo-inverse Jacobian computation. IEEE Trans. on Robotics)A
155 623 :M
.276 .028(and Automation, Vol. 5, No. 5, October, pp. 569-582, 1989.)J
155 641 :M
f3_12 sf
.305 .03(Keywords: )J
f5_12 sf
.225 .022(reverse Jacobian, operation and joint level, array network,)J
155 659 :M
-.066(linear pipe, systolic array, SIMD, VLSI, integer arithmetic, scalable.)A
70 683 :M
-.045([Chen86])A
155 683 :M
.201 .02(J. B. Chen & R. S. Fearing & B. S. Armstrong & J. W. Burdick: NYMPH:)J
155 701 :M
-.049(A multiprocessor for manipulation applications. Proc. 1986 IEEE Int. Conf.)A
155 719 :M
.064 .006(on Robotics and Automation, pp. 1731-1736, 1986.)J
155 737 :M
f3_12 sf
.398 .04(Keywords: )J
f5_12 sf
.311 .031(forward kinematics, task level, bus network, MIMD, scalable.)J
endp
%%Page: 16 16
%%BeginPageSetup
initializepage
(D.Henrich; page: 16 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(16)S
70 94 :M
-.072([Fijany92])A
155 94 :M
-.102(A. Fijany & A. Bejczy: Parallel computation systems for robotics algorithms)A
155 112 :M
-.027(and architectures. New York World Scientific Publishing Co. Pte. Ltd.,)A
155 130 :M
.25(1992.)A
155 148 :M
f3_12 sf
.179 .018(Keywords: )J
f5_12 sf
.139 .014(forward kinematics and forward Jacobian, operation and joint)J
155 166 :M
-.063(level, SIMD, MIMD, non-scalable.)A
70 190 :M
-.065([Fujioka93])A
155 190 :M
-.116(Y. Fujioka & M. Kameyama: 2400-MFLOPS reconfigurable parallel VLSI)A
155 208 :M
.086 .009(processor for robot control. Proc. 1993 Int. Conf. on Robotics and)J
155 226 :M
.35 .035(Automation, pp.149-154, 1993.)J
155 244 :M
f3_12 sf
.125 .012(Keywords: )J
f5_12 sf
.096 .01(forward kinematics and reverse Jacobian, operation and joint)J
155 262 :M
-.039(level, one or two dimensional array, SIMD, VLSI, scalable.)A
70 286 :M
([Funda90])S
155 286 :M
-.039(J. Funda & R. P. Paul: A computational analysis of screw transformations in)A
155 304 :M
.159 .016(robotics. IEEE Trans. on Robotics and Automation, Vol. 6, No. 3, June, pp.)J
155 322 :M
1.253 .125(348-356, 1990..)J
155 340 :M
f3_12 sf
.308 .031(Keywords: )J
f5_12 sf
.28 .028(forward kinematics, operation level, line-oriented.)J
70 364 :M
([Gosselin96])S
155 364 :M
-.107(C. M. Gosselin: Parallel computational algorithms for the kinematics and)A
155 382 :M
-.109(dynamics of planar and spatial parallel manipulators. Trans. of the ASME:)A
155 400 :M
.079 .008(Journal of dynamic Systems, Measurement, and Control , Vol. 118, No. 1,)J
155 418 :M
.518 .052(March, pp. 22-28, 1996.)J
155 436 :M
f3_12 sf
.344 .034(Keywords: )J
f5_12 sf
.266 .027(reverse kinematics, forward Jacobian, joint level, SIMD, non-)J
155 454 :M
-.08(scalable.)A
70 478 :M
-.07([Graham89])A
155 478 :M
-.069(J. H. Graham: Special computer architectures for robotics, tutorial and)A
155 496 :M
.061 .006(survey. IEEE Trans. on Robotics and Automation, Vol. 5, No. 5, October,)J
155 514 :M
.813 .081(pp. 543-554, 1989.)J
155 532 :M
f3_12 sf
1.812 .181(Keywords: )J
f5_12 sf
.386(Overview.)A
70 556 :M
-.072([Hamisi89])A
155 556 :M
-.102(F. Hamisi & D. A Fraser: Transputer-based implementation of real-time robot)A
155 574 :M
.097 .01(position control. Microprocessors and microsystems, Vol. 13, No. 5,)J
155 592 :M
.3 .03(December, pp. 644-652, 1989.)J
155 610 :M
f3_12 sf
.405 .04(Keywords: )J
f5_12 sf
.339 .034(forward kinematics, forward and reverse Jacobian, operation,)J
155 628 :M
-.068(task and joint level, special purpose, MIMD, non-scalable.)A
70 652 :M
-.032([Harber88])A
155 652 :M
.047 .005(R. G. Harber & J. Li & X. Hu & S. C. Bass: The application of bit-serial)J
155 670 :M
-.046(CORDIC units to the design of inverse kinematics processors. Proc. 1988)A
155 688 :M
.051 .005(IEEE Conf. on Robotics and Automation, pp. 1152-1157, 1988.)J
155 706 :M
f3_12 sf
.175 .018(Keywords: )J
f5_12 sf
.151 .015(reverse kinematics, computation chain level, CORDIC, VLSI,)J
155 724 :M
-.053(non-scalable.)A
endp
%%Page: 17 17
%%BeginPageSetup
initializepage
(D.Henrich; page: 17 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(17)S
70 94 :M
-.087([Hemkumar94])A
155 94 :M
-.045(N. D. Hemkumar & J. R. Cavallaro: Redundant and on-line CORDIC for)A
155 112 :M
.122 .012(unitary transformations. IEEE Trans. on computers, Vol. 43, No. 8, August,)J
155 130 :M
1.054 .105(pp. 941-954, 1994..)J
155 148 :M
f3_12 sf
.351 .035(Keywords: )J
f5_12 sf
.265 .027(forward and reverse Jacobian, operation level, systolic array,)J
155 166 :M
-.024(VLSI, CORDIC, non-scalable.)A
70 190 :M
-.056([Kasahara85])A
155 190 :M
-.054(H. Kasahara & S. Narrita: Parallel processing of robot-arm control)A
155 208 :M
-.086(computation on a multimicroprocessor system. IEEE Journal of Robotics and)A
155 226 :M
.44 .044(Automation, Vol. 1, No. 2, pp. 104-113, 1985.)J
155 244 :M
f3_12 sf
.155 .016(Keywords: )J
f5_12 sf
.128 .013(forward kinematics, MIMD, static load balancing, scalable.)J
70 268 :M
([Khosla87])S
155 268 :M
.023 .002(P. K. Khosla: Choosing sampling rates for robot control. Proc. 1987 IEEE)J
155 286 :M
.206 .021(Int. Conf. on Robotics and Automation, Vol. 1, pp. 169-174, 1987.)J
155 304 :M
f3_12 sf
2.08 .208(Keywords: )J
f5_12 sf
.413(General.)A
70 328 :M
.068([Kokusho95])A
155 328 :M
-.099(Y. Kokusho: Parallel computation for manipulator control using the double-)A
155 346 :M
-.112(layered load-distribution mechanism on multi-transputer networks. Intelligent)A
155 364 :M
.24 .024(Autonomy Systems, IOS Press, 1995.)J
155 382 :M
f3_12 sf
.148 .015(Keywords: )J
f5_12 sf
.119 .012(forward and reverse Jacobian, computation chain level, MIMD,)J
155 400 :M
-.031(scheduling, scalable.)A
70 424 :M
-.161([Lee87])A
155 424 :M
-.056(C. S. G. Lee & P. R. Chang: A maximum pipelined CORDIC architecture for)A
155 442 :M
-.103(inverse kinematic position computation. IEEE Journal of Robotics and)A
155 460 :M
.329 .033(Automation, Vol. 3, No. 5, October, pp. 445-458, 1987.)J
155 478 :M
f3_12 sf
.135 .014(Keywords: )J
f5_12 sf
.115 .012(reverse kinematics, computation chain level, pipeline,)J
155 496 :M
-.084(CORDIC, static load balancing, non-scalable.)A
70 520 :M
-.161([Lee89])A
155 520 :M
-.042(C. S. G. Lee: Introduction, Robot manipulators: algorithms and architectures.)A
155 538 :M
.057 .006(IEEE Trans. on Robotics and Automation, Vol. 5, No. 5, October, pp. 541-)J
155 556 :M
1.053 .105(542, 1989.)J
155 574 :M
f3_12 sf
1.812 .181(Keywords: )J
f5_12 sf
.386(Overview.)A
70 598 :M
-.161([Lee91])A
155 598 :M
-.049(C. S. G. Lee: On the parallel algorithms for robotics computation. Sensor-)A
155 616 :M
-.012(based Robots: Algorithms and Architectures. \(Eds. C. S. G. Lee\) Springer-)A
155 634 :M
.359 .036(Verlag, New York, pp. 239-280, 1991.)J
155 652 :M
f3_12 sf
1.812 .181(Keywords: )J
f5_12 sf
.386(Overview.)A
70 676 :M
-.08([Leung87])A
155 676 :M
-.049(S. S. Leung & M. A. Shanblatt: Real-time DKS on a single chip. IEEE)A
155 694 :M
.17 .017(Journal of Robotics and Automation, Vol. 3, No. 4, August, pp. 281-290,)J
155 712 :M
.25(1987.)A
155 730 :M
f3_12 sf
.368 .037(Keywords: )J
f5_12 sf
.325 .032(forward kinematics, operation level, VLSI, non-scalable.)J
endp
%%Page: 18 18
%%BeginPageSetup
initializepage
(D.Henrich; page: 18 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(18)S
70 94 :M
-.108([Lin91])A
155 94 :M
-.054(C.-T. Lin & C. S. G. Lee: Fault-tolerant reconfigurable architecture for robot)A
155 112 :M
-.052(kinematics and dynamics computations. IEEE Trans. on Systems, Man, and)A
155 130 :M
.155 .016(Cybernetics, Vol.21, No.5, September/October , 1991.)J
155 148 :M
f3_12 sf
.094 .009(Keywords: )J
f5_12 sf
.073 .007(kinematics and Jacobian, joint level, generalized cube network,)J
155 166 :M
-.081(SIMD, fault-tolerant.)A
70 190 :M
-.053([Luh82])A
155 190 :M
-.039(J. Y. S. Luh & C. S. Lin: Scheduling of parallel computation for a computer-)A
155 208 :M
-.074(controlled mechanical manipulator. IEEE Trans. on Systems, Man, and)A
155 226 :M
.292 .029(Cybernetics, Vol. 12, No. 2, March/April, pp. 214-234, 1982.)J
155 244 :M
f3_12 sf
.473 .047(Keywords: )J
f5_12 sf
.394 .039(forward Jacobian, joint level, MIMD, scheduling.)J
70 268 :M
-.164([Maciejewksi94])A
155 268 :M
-.12(A. A. Maciejewski & J. M. Reagin: A parallel algorithm and architecture for)A
155 286 :M
-.101(the control of kinematically redundant manipulators. IEEE Trans. on Robotics)A
155 304 :M
.342 .034(and Automation, Vol. 10, No. 4, August, pp. 405-414, 1994.)J
155 322 :M
f3_12 sf
.204 .02(Keywords: )J
f5_12 sf
.158 .016(reverse Jacobian, joint level, linear array, MIMD, non-scalable.)J
70 346 :M
-.033([Nabhan95])A
155 346 :M
-.094(T. M. Nabhan & A. Y. Zomaya: Application of parallel processing to robotic)A
155 364 :M
.041 .004(computational tasks. The Int. Journal of Robotics Research, Vol. 14, No. 1,)J
155 382 :M
.84 .084(February, pp.76-86, 1995.)J
155 400 :M
f3_12 sf
.18 .018(Keywords: )J
f5_12 sf
.153 .015(forward Jacobian, computation chain level, MIMD, scalable.)J
70 424 :M
-.14([Orin84])A
155 424 :M
-.08(D. E. Orin & W. W. Schrader: Efficient computation of the Jacobian for)A
155 442 :M
.124 .012(robot manipulators. Int. Journal of Robotics Research, Vol. 3, No. 4,)J
155 460 :M
.508 .051(Winter, pp. 66-75, 1984.)J
155 478 :M
f3_12 sf
1.439 .144(Keywords: )J
f5_12 sf
1.613 .161(forward Jacobian.)J
70 502 :M
-.14([Orin87])A
155 502 :M
-.004(D. E. Orin & K. W. Olson & H. H. Chao: Systolic architectures for)A
155 520 :M
-.095(computation of the Jacobian for robot manipulators. in Computer)A
155 538 :M
-.045(Architectures for Robotics and Automation \(Eds. James H. Graham\), Gordon)A
155 556 :M
.132 .013(and Breach Science Publishers, pp. 39-67, 1987.)J
155 574 :M
f3_12 sf
.471 .047(Keywords: )J
f5_12 sf
.378 .038(forward Jacobian, joint level, hypercube, systolic, scalable.)J
70 598 :M
-.14([Orin91])A
155 598 :M
.034 .003(D. E. Orin & P. Sadayappan, Y. L. C. Ling & K. W. Olson: Robotics Vector)J
155 616 :M
-.086(Processor architecture for real-time control. Sensor-based Robots: Algorithms)A
155 634 :M
.136 .014(and Architectures. \(Eds. C. S. G. Lee\) Springer-Verlag, New York, pp. 203-)J
155 652 :M
1.053 .105(238, 1991.)J
155 670 :M
f3_12 sf
.282 .028(Keywords: )J
f5_12 sf
.229 .023(forward Jacobian and forward kinematics, operation and)J
155 688 :M
-.098(computation chain level, MIMD,SIMD, VLSI.)A
70 712 :M
-.088([Pedicone87])A
155 712 :M
(J. T. Pedicone & T. L. Johnson: Robot motion control with CPAC. in)S
155 730 :M
-.069(Computer Architectures for Robotics and Automation \(Eds. J. Graham\) New)A
155 748 :M
.112 .011(York, Gordon and Breach Science Publishers, March, pp. 214-234, 1987.)J
155 766 :M
f3_12 sf
.291 .029(Keywords: )J
f5_12 sf
.251 .025(forward kinematics, joint level, MIMD, non-scalable.)J
endp
%%Page: 19 19
%%BeginPageSetup
initializepage
(D.Henrich; page: 19 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(19)S
70 94 :M
-.074([Sadayappan89])A
155 94 :M
-.013(P. Sadayappan & Y.-L. C. Ling & K. W. Olson & D. E. Orin: A restructable)A
155 112 :M
-.097(VLSI robotics vector processor architecture for real-time control. IEEE Trans.)A
155 130 :M
.178 .018(on Robotics and Automation, Vol. 5, No. 5, October , pp. 583-598, 1989.)J
155 148 :M
f3_12 sf
.282 .028(Keywords: )J
f5_12 sf
.229 .023(forward kinematics and forward Jacobian, operation and)J
155 166 :M
-.096(computation chain level, MIMD, SIMD, VLSI.)A
70 190 :M
-.092([Tsai85])A
155 190 :M
-.063(L. W. Tsai & A. P. Morgan: Solving the kinematics of the most general six-)A
155 208 :M
-.055(and five-DOF manipulators by continuation methods. Trans. ASME, J.)A
155 226 :M
.071 .007(Mechanism, Transmissions, Automation in Design, 107, June, pp. 189-200,)J
155 244 :M
.25(1985.)A
155 262 :M
f3_12 sf
.499 .05(Keywords: )J
f5_12 sf
.434 .043(reverse kinematics, iterative form.)J
70 286 :M
-.143([Walker93])A
155 286 :M
-.135(I. D. Walker: Parallel VLSI architectures for real-time kinematics of)A
155 304 :M
-.009(redundant robots. IEEE Int. Conf. on Robotics and Automation, pp. 870-)A
155 322 :M
1.053 .105(877, 1993.)J
155 340 :M
f3_12 sf
.215 .021(Keywords: )J
f5_12 sf
.179 .018(forward kinematics, reverse kinematics forward and reverse)J
155 358 :M
-.04(Jacobian, task and operation level, systolic array, VLSI, CORDIC.)A
70 382 :M
-.091([Wang87])A
155 382 :M
-.031(Y. Wang & S. E. Butner: A new architecture for robot control. Proc. 1987)A
155 400 :M
.101 .01(IEEE Conf. on Robotics and Automation, , pp. 664- 670, 1987.)J
155 418 :M
f3_12 sf
.146 .015(Keywords: )J
f5_12 sf
.117 .012(reverse kinematics, task and operation level, MIMD, CORDIC,)J
155 436 :M
-.053(non-scalable.)A
70 460 :M
-.122([Yeung88])A
155 460 :M
-.055(T. B. Yeung & C. S. G. Lee: Efficient parallel algorithms and VLSI)A
155 478 :M
-.072(architectures for manipulator Jacobian computation. Proc. 1988 IEEE Conf.)A
155 496 :M
.064 .006(on Robotics and Automation, pp. 1158-1163, 1988.)J
155 514 :M
f3_12 sf
.541 .054(Keywords: )J
f5_12 sf
.438 .044(forward Jacobian, operation level, SIMD, systolic, VLSI,)J
155 532 :M
-.08(scalable.)A
70 556 :M
-.122([Yeung89])A
155 556 :M
-.055(T. B. Yeung & C. S. G. Lee: Efficient parallel algorithms and VLSI)A
155 574 :M
-.075(architectures for manipulator Jacobian computation. IEEE Trans. on Systems,)A
155 592 :M
.152 .015(Man, and Cybernetics, Vol. 19, No. 5, September/October, pp. 1154-1165,)J
155 610 :M
.25(1989.)A
155 628 :M
f3_12 sf
.541 .054(Keywords: )J
f5_12 sf
.438 .044(forward Jacobian, operation level, SIMD, systolic, VLSI,)J
155 646 :M
-.08(scalable.)A
70 670 :M
-.08([Zhang90])A
155 670 :M
-.061(H. Zhang & R. P. Paul: A parallel inverse kinematics solution for robot)A
155 688 :M
-.093(manipulators based on multiprocessing and linear extrapolation. IEEE Trans.)A
155 706 :M
.066 .007(on Robotics and Automation, pp. 468-474, 1990.)J
155 724 :M
f3_12 sf
.232 .023(Keywords: )J
f5_12 sf
.198 .02(reverse kinematics, joint level, MIMD, non-scalable.)J
endp
%%Page: 20 20
%%BeginPageSetup
initializepage
(D.Henrich; page: 20 of 20)setjob
%%EndPageSetup
-28 -31 :T
gS 28 31 538 781 rC
290 810 :M
f5_12 sf
(20)S
70 94 :M
-.08([Zhang91])A
155 94 :M
-.061(H. Zhang & R. P. Paul: A parallel inverse kinematics solution for robot)A
155 112 :M
-.093(manipulators based on multiprocessing and linear extrapolation. IEEE Trans.)A
155 130 :M
.178 .018(on Robotics and Automation, Vol. 7, No. 5, October, pp. 660-669, 1991.)J
155 148 :M
f3_12 sf
.232 .023(Keywords: )J
f5_12 sf
.198 .02(reverse kinematics, joint level, MIMD, non-scalable.)J
70 172 :M
-.145([Zomaya92])A
155 172 :M
-.135(A. Y. Zomaya: Modelling and simulation of robot manipulators -A parallel)A
155 190 :M
.047 .005(processing approach. World Scientific Publishing Co. Pte. Ltd., 1992.)J
155 208 :M
f3_12 sf
.274 .027(Keywords: )J
f5_12 sf
.224 .022(forward Jacobian, reverse Jacobian, joint and computation)J
155 226 :M
-.079(chain level, tree, MIMD, non-scalable.)A
70 250 :M
-.145([Zomaya96])A
155 250 :M
-.075(A. Y. Zomaya: Parallel and distributed computing handbook. McGraw-Hill,)A
155 268 :M
.771 .077(pp. 1149-1159, 1996.)J
155 286 :M
f3_12 sf
1.812 .181(Keywords: )J
f5_12 sf
.386(Overview.)A
endp
%%Trailer
end % md
%%EOF