ࡱ> 10  !"#$%&'()*+,-./2J3K56789:;<=>?@ABCDEFGHIebUMNOPQRSTWXYZ[\]^_`acdfghijklmRoot EntryThumbnai Fս CompObj LCZp&3ࡱ> Noneࡱ> Noneࡱ> ࡱ> _958050595Ahޓ!OBսBսOle PIC LMETA HTCZ? * < 8 3f3333f333ff3fffff3f3f̙3f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙333333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffffff3fffffff3fff̙ffff3fffff3f3333f333ff3fffff3f3f̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3f (((555CCCPPP]]]kkkxxx45 "--!H "- --Hh- --H@- --@- --`8- --H8- --H- --yH- --QH- --A!- --A@- --yh- "- %--- $- "- %- "- %--- $!- "- %!- "- %--- $ss- "- %ss- "- %A--- $hshAh- "- %hshAh- "- %Mu--- $"- "- %"- --Yh- "- %p--- $VDqV- "- %VDqV- "- %F i--- $>>H j>- "- %>>H j>- "- %00g--- $@E@0h@- "- %@E@0h@- "- %[v--- $aJc[waJ- "- %aJc[waJ- --9!- --9X- --) - --Q- --X- "- %A--- $- "- %- "- %X.--- $/- "- %/- "- %0--- $[vd[v- "- %[vd[v- "- %--- $@@@- "- %@@@- "- %--- $cvc- "- %cvc- "- %+--- $-eQz+-e- "- %-eQz+-e- "- %--- $- "- %- "- %Y--- $?I?- "- %?I?- "- -- p--."Arial- 2 s1- "- -- p--.- 2 s2- "- -- --.-2 31- "- -- ps--.- 2 zvs3- "- -- Xq--.- 2 FztU4- "- -- k--.- 2 rn5- "- -- d--.-2 kg30- "- -- p[--.-2 c^s25- "- -- xp3--.-2 ;6su26- "- -- "--.- 2 6- "- -- --.- 2  7- "- -- Pp --.-2 sM27- "- -- (p--.-2 s%28- "- -- B--.- 2 "?9- "- -- H--.- 2 vK8- "- -- &--.-2 #10- "- -- {--.-2 ~29- "- -- --.-2  11-  "--Yh- --Y- --Y- -- x- --`- --MX- --Y,- --`0- "- -- 0=--.-2 G@-13- "- -- @--.-2 nC}14- "- -- 0~9--.-2 C<{-15- "- -- S--.-2 [V21- "- -- q,--.-2 3/n38- "- -- 0P--.-2 WS-34- "- -- ${--.-2 ~!20-  "--0- --P- --10- -- $ ,- --P- -- ph- -- 9$ - --i  - "- -- T--.-2 [W35- "- --  L O--.-2 z WRO  22- "- -- aX--.-2 #[^33- "- -- ^x--.-2 #{[19- "- -- @ ` --.-2 . # ]= 24- "- --  L --.-2 z O  23- "- -- --.-2 37-  "--q9- --y4- --y\- "- -- PU--.-2 >_XM17- "- -- P}--.-2 >M18- "- -- H--.-2 6  E16-  "--,- ---X- "- -- |--.-2 39- "- %S$5--- $) $6- "- %) $6- "- %\XG0--- $6` G16- "- %6` G16- "- %J--- $"EK"- "- %"EK"- "- %Vl--- $S}lS- "- %S}lS- "- %\+--- $aW:G\+aW- "- %aW:G\+aW- "- %._& --- $@ i_' @ - "- %@ i_' @ - "- %d.--- $   - "- %   - "- %U --- $] 5 U ] - "- %] 5 U ] - "- %  --- $    - "- %    - "- %@@ --- $+ U @ + - "- %+ U @ + - "- %--- $- "- %- "- %300--- $E0- "- %E0- "- %sea--- $6Rb6- "- %6Rb6- "- %c J--- $#0FK#- "- %#0FK#- "- %,t  --- $ %   - "- % %   - "- % ( --- $. ) - "- %. ) - "- %--- $- "- %- "- %@@O--- $+(U(@P+(- "- %+(U(@P+(- "- %`Y`O--- $K(u(`PK(- "- %K(u(`PK(- "- %tR--- $l'3tSl'- "- %l'3tSl'- "- %Wo4--- $5- "- %5- "- %9p --- $    - "- %    - "- %tYt# --- $_t$ _- "- %_t$ _- "- -- T--.-2 W36- "- -- x<--.-2 C?{~32- "- %Yo--- $HHpH- "- %HHpH- "- %J|0--- $1- "- %1- "- %6--- $  7 - "- %  7 - "- %H--- $>I- "- %>I- "- %+--- $%,%- "- %%,%- "- %L4--- $5- "- %5- "- %CNDD(~--- $\k~R\k- "- %\k~R\k- "- -- 0--.-2 -12- "- %@--- $k2Ak2- "- %k2Ak2- "- %--- $ - "- % - "- %-e--- $O+9.fO- "- %O+9.fO- "- %i--- $4O9yi4O- "- %4O9yi4O- "- --  Wb --.-2 e T 3pk- -ࡱ> Author  Company ProjectRoot Entry VersionCompObj!T CorelFLOW Version 2.001 Documentࡱ> ࡱ>  ?Q?!@&@22228( ࡱNoneࡱ> :|^ࡱ> Noneࡱ> CorelFLOWࡱ> ObjInfo  Contents zKeyWords  Thumbnail DescriptionApplicationName  _957721771 F ս սPIC Lܥe3 e8a<- 6666666$.7.7.7.7.7B7R7.7H;th7p7777777d9f9f9f99V:*;;T<QH;677777H;7667h777776767d966666667d9779th DAAAM INTERNATIONAL SYMPOSIUM Technical University Cluj - Napoca, Cluj - Napoca, Romania 22-24th October 1998 USE OF LOCAL SEARCH ALGORITHM FOR TASK ALLOCATION PROBLEM OF ROBOT DYNAMICS CALCULATION Davor Zorc Abstract: This paper deals with application of localized random search algorithm for finding near optimal solution for placement of processes on multiple processor system. This problem is known to be NP-Complete. As an example robots dynamics formulation is decomposed. Results show good speedups and processor use eficiency with moderate number of schedulling algorithm iterations. Key words: parallel processing, scheduling, robotics, allocation. 1. INTRODUCTION Scheduling problems in general could not be solved in polynomial time except for a limited number of special cases. On the other hand, finding all possible solutions to find the best is impossible to do because of exponential expansion of number of possible combinations (Watanabe et al., 1986), (Coffman, 1976). In this situation heuristic algorithms are used because they give good sub-optimal results in reasonable time. Although scheduling algorithms are computationally intensive, it is done in project design phase and do not cause overhead in run-time. There are simple solutions of implementing parallel processing when there are more independent jobs. Here implementation of single job with mutually dependent parts is investigated. Generally, to implement the control procedure on the multiple-processor system several problems must be solved: symbol 183 \f "Symbol" \s 10 \h partition of the control procedure into computational processes symbol 183 \f "Symbol" \s 10 \h allocation of processes on local memory of the particular processor symbol 183 \f "Symbol" \s 10 \h determination of schedule of process execution to complete the job in minimum time symbol 183 \f "Symbol" \s 10 \h there must be some kind of operating system with synchronization and communication primitives. Implementation of robot's dynamics, kinematics and path planing algorithms demands for computers with high processing power. Implementation of some of those algorithms on multiple-processor system may be economically justified, if required processor is more expensive then several slower processors with equivalent power, or if processor with enough processing power is not available at all. This paper deals with partitioning, allocation and scheduling procedures applied on RRTR robot's dynamics formulation. It shows use of local search algorithm for task allocation and scheduling. 2. FORMULATION AND PARTITION OF EULER-LAGRANGE DYNAMICS Formulation is given by Euler-Lagrange equation (Groover et al., 1986), (Paul, 1981): T = I(q)q + C(q,q) + G(q), (1) where: T - vector of forces / torques in joints q - vector of inner coordinates, dimension N x 1 I(q) - symmetric inertia matrix, dimension N x N C(q,q) - vector of torques from interactions between controlled coordinates, includes centrifugal and Coriolis forces G(q) - vector of gravity torques, dimension N x 1 This equation, calculated for RRTR robot structure, is partitioned into 39 computational processes. Partitioning strategy and details of this particular example are given in (Zorc, 1990). By observing data flow between those processes, one may construct process diagram (figure 1), where nodes represent processes. Arcs between processes impose partial ordering in time: process must not be allowed to start execution before all of his predecessors are executed. 3. SCHEDULING ALGORITHM Allocation algorithm will decide which processes will be executed by which processor and scheduling gives time-table of process executions. For the sample results which follow, SXN algorithm was used (Zorc, 1990). First the levels of processes is calculated as in standard level allocation (level is a measure of time distance for particular process to terminal process). Allocation algorithm goes as follow: whenever a processor is idle, a process is assigned to it. Between all ready and unallocated processes, random process is chosen but not from the set of all ready processes but from the narrowed set based on process level. Acceptable levels range from maximum level of all ready processes to some pre-defined lower limit. In this way near (local) neighborhood is defined and number of search possibilities is narrowed. Search may be done with arbitrary neighborhood width. Allocations are repeated until good sub-optimal solution is reached. This heuristic algorithm insures good sub-optimal allocation and schedule for this NP-complete computational problem. Algorithm is tested on IBM-PC computer. Algorithm is run in iterations and best results are recorded. Several thousands of iterations are finished within 10 seconds on 100 MHz PC. From those results speedup and processor utilization data is extracted. Speedup is the measure of improvement in execution time over single processor system. For the above dynamics formulation it is here given for allocation on 2-10 processor system (figure 2). Figure 3 shows utilization of available processors time. The main reason that it is less than 100% is that a processor must wait when there are no ready processes at the moment this processor becomes free. Algorithm S X N. Step 1- Initiate iterations, calc. levels Step 2- Do Iterations (Repeat Step 3,4,5) Step 3- Allocation initialization Step 4- Do allocation (Repeat Step 6-10) Step 5- Record minimum schedule Step 6- Choose processor Step 7- Determine ready processes Step 8- Filter the process list Step 9- Choose the process Step 10- Allocate process to processor  EMBED CorelFLOW.Document Figure 1. Process diagram for Euler - Lagrange formulation 4. CONCLUSION Results show possibility of effective implementation of RRTR- Kinematics formulation on systems with 2-10 processors. Speedups that may be obtained depend on several factors: inherent parallelism of control formulation, partitioning strategy and granulation, and on effectiveness of allocation/scheduling procedure. Local neighborhood search algorithm is shown to be effective on such a problem with moderate number of iterations.  EMBED Word.Picture.6  Figure 2. - Speedup factor vs. number of processors Figure 3. - ETA vs. number of processors 5. REFERENCES Groover M.P. et al.. (1986). Industrial Robotics - Technology, Programming and Applications, McGraw-Hill Book Company, New York Paul, R.P. (1981). Robot Manipulators: Mathematics, Programming and Control, MIT Press, Cambridge, Mass. USA Watanabe, T et al. (1986). Improvement in the Computing Time of Robot Manipulators Using a Multi-microprocessor, Transactions of the ASME, Vol. 108, September 1986 Coffman, E.G.,jr. (1976). Computer and Job- Shop Scheduling Theory, John Wiley & Sons, New York Zorc, Davor (1990). Decomposition of mechanical manipulator's control algorithms for execution on multiple processor systems, Doctor's thesis, FER- Zagreb Author: Dr.Sc. Davor Zorc, Faculty of mechanical and naval engineering, Head of Automation department, Ivana Lucica 5, HR-10000 Zagreb, Croatia, e-mail: davor.zorc@fsb.hr, http://www.sjever.fsb.hr/~dzorc/davor.html  ' .Annn (.Annnn ^: :n 6    Z -- "Arial#f-"System-z"MorseCodef--z"MorseCodef--"Arial#f--"Arial#f--"Arial#f--Q"MorseCodef--"Arial#f--z"MorseCodef--  "Arial#f- "Ariale- !2u'"Arial- !4.'"Arial- !6'"Arial- !8'"Arial- !104 ' - "Arial#f- "Arial-  !70/'"Arial-  !75K'"Arial-  !80h'"Arial-  !85'"Arial-  !90'"Arial- !95'"Arial- !100' - --wwSS00  ~ ~ Z Z Z -- --ww"">>ZZvv!!-- --n7;`rB&(\ ----Vik9;D$K f -- "Arial#f- "Arial- !Etax' -WindsorWindsor Condensed^ࡱ> LAt _ࡱ>   FMicrosoft Word 6.0 Picture MSWordDocWord.Picture.69qࡱࡱ> _Oh+'0  $ H l   DhMETA LHCompObjlObjInfoObjectPool ս սA &WordMicrosoft Word  ]nCourier New-Times New Roman- "Arial- 2 n]2'x- 2 xn]4'M- 2 n]6'- 2 n]8';-2 ;n]10'q- 2 qn]2'n:q- 2 ;qn]3'q- 2 qn]4'q- 2 qn]5'f2q- 2 3qn]6' q- 2 qn]7'q- 2 qn]8' "- "- "-- "-77- "-- "-- "-- "-mm- "-- "-- "-UU- "-- "-- "-- "-- "-- "-TT- "-((- "-- "-- "-- "-ww- "-KK- "-- "-- "-- "-- "-- "-/{- "-- "-*U- "-HK-- "---- "-1|--- "-)--- "-YF--- "-_M--*0-2 0n]SP'-ࡱ> WordDocumentVSummaryInformation(SummaryInformation( ܥe3 e]2*jjjj  1$CT4jjj<jjjj SP 8 7 6 5 4 3 2 10 8 6 4 2 .Ade()200($!u./0$DF..0$+AEF.-0$ DF.,0$U"DF.+0$$DF0*0&vml0)0& {/.0(0& 0'0&0""!0&0&0%0&+*0$0&E0#0&+*0"0&0!0&U+*0 0& 00& +*00&g!00&"+*00&"00&x#+*00&)$00&$+*00&%00&%  00&%00&%,+00&%00&M%,+00&%00&%,+00&%00&v%,+00&B%0 0& %,+0 0&%2 0('-2 0('2 0('20('P 20('!20('#20('q$20(P%E20(%20(%20(C%20(%{d 6wԲ\5a9P^L@quJm:"b)Xvx6 E7\W d~ -n~B;[X3tr˷IvG^C\)|fij=:E,቏2da6L$QgdҘac`._ɞ)/eO:aʒN4ǧ>=UawFM]q_%0;: au˅wCȿPDثzu5(0PB <*=;&$DppX cP:G 12[\] u ]abc uDa25689;<>?ABDEGHJKNOQRTUWXZ[\]xHK@Normala "A@"Default Paragraph Font  #&),]] ] ]  !"#$%&'()*+,-./0]q-[Iy 9i)YIy 9 i ) Y    ! S     M  @Epson Stylus COLOR IIsLPT1:EPMJ5CEpson Stylus COLOR IIsPj 4dhhB  Epson Stylus COLOR IIsLPT1:Epson Stylus COLOR IIsPj 4dhhB  Epson Stylus COLOR IIsLPT1: 1Times New Roman Symbol &Arial"hC%C%F!4Dr. Mario EssertDr. Mario Essertࡱ> $C:\PROG\WINWORD\TEMPLATE\NORMAL.DOTDr. Mario EssertDr. Mario Essert@+鈽@Y@+鈽@Microsoft Word 6.02_Oh+'0 D h   @d C:\WINWORD\TEMPLATE\NORMAL.DOT"8th INTERNATIONAL DAAAM SYMPOSIUMDr. Davor ZorcDr. Davor Zorc@ 刽@0H9@ս=@jMicrosoft Word 6.022!t]h ) + l m I J i k  P R .2_g7=`fU``cU`c`uDuD]cU]cV]c UV]c]cU]cU]]c]K ;<=>Gz{|};<STUV`"['?t6V]^-.678+ٰ٫٫٫٫٫٥٠ٙu ]acuD UV]cV]cuD uD9KuD9]acvKuDU]c]c\]c]cuD#9U]cKuD#9]acvKU]cuDU]c+"]rst] l I T   Q R ._%%%%%%%% 0h'  7`{|};Hh  T0h00%HZUV-/01235678%%H$:0 T0K @ Normal ]a c"A@"Default Paragraph Font @ Footer !2O2 Dr formath,0 ]a c88a  ;8+ +H8 )*lIij;=;SU89999::Dr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCFSB-AutomatikaC:\DZORC\DOC\PE-DAM98.DOCFSB-AutomatikaC:\DZORC\DOC\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOCDr. Davor ZorcD:\U\T\SCI\PE-DAM98.DOC@HP LaserJet IIPLPT1:HPPCLHP LaserJet IIP@g,,@MSUDHP LaserJet IIPd HP LaserJet IIP@g,,@MSUDHP LaserJet IIPd SSSStTimes New Roman Symbol &ArialMS SerifCG Times (W1) 1Courier5Courier New!V %F )F+ &&=8=8$Q!8th INTERNATIONAL DAAAM SYMPOSIUMDr. Davor ZorcDr. Davor Zorcࡱ>