AUTOMATIC ASSEMBLY TASK ASSIGNMENT FOR A
MULTIROBOT ENVIRONMENT
C. Del Valle* and E.F. Camacho**
*Depa amen o de Lenguajes y Sis emas In o má icos, Uni e sidad de Se illa, 41012 Se illa, Spain
([email p o ec ed])
**Depa amen o de Ingenie ía de Sis emas y Au omá ica, Uni e sidad de Se illa, 4/012 Se illa, Spain
Abs ac : This pape p esen s an algo i hm A• o ob aining he "bes " assembly plan o
a p oduc in a mul i obo sys em. Toe algo i hm akes in o accoun , in addi ion o he
assembly imes, he imes needed o change ools in he obo s. Toe objec i e o he plan
is he minimiza ion o he makespan. To mee his objec i e, he algo i hm s a s om he
And/O g aph (comp essed ep esen a ion o all easible assembly plans) and he
in o ma ion on each assembly ask ( obo and ool needed, and assembly ime).
Keywo ds: Flexible manu ac u ing sys ems; assembly obo s; indus ial obo s; a i icial
in elligence; op imiza ion p oblems; scheduling algo i hms
1. INTRODUCTION
Au oma ic assembly is one o he a eas o manu ac
u ing ha has no been ully de eloped in indus y.
This is mainly because obo con ol and o -line
p og amming ha e no e ol ed as expec ed
(Ma ensson, 1990), as esul o he ac ha he
assembly p ocess is much mo e complex han
p ocesses in o he obo ic applica ions and pa s
manu ac u ing. The e o e, un il ecen ly, indus ial
obo s we e used p ima ily in simple assembly
applica ions. This si ua ion is changing, howe e , and
Flexible Assembly Sys ems ha e become a e y
impo an issue because o he need o p oduce small
lo s o p oduc s, bu he deg ee o lexibili y is s ill
low (Boneschansche , 1993).
The e a e di e en s ages in he whole p ocess o
assembly, such as design o p oduc s and pa s,
design o ix u es, g asp selec ion, pa h planning,
ine-mo ion planning, senso in eg a ion, e c. One o
he mos impo an issues in he whole p ocess is
planning assembly asks, whose op imali y will ha e
a signi ican e ec on he inal cos o he assembled
p oduc (Kusiak, 1990). Toe assembly planning
p oblem in ol es he iden i ica ion, selec ion and
sequencing o assembly ope a ions, s a ed as hei
e ec s on he pa s. Toe iden i ica ion o assembly
ope a ions usually leads o he se o all easible
assembly plans. The numbe o hem g ows expo
nen ially wi h he numbe o pa s, and depends on
o he ac o s, such as how he single pa s a e in e 
connec ed in he whole assembly, i.e. he s uc u e o
he g aph o connec ions. In ac , his p oblem has
been p o ed o be NP-comple e in bo h he wo
dimensional (Ka aki and Koloun zakis, 1995) añ.d
h ee-dimensional (Ka aki, e al., 1995; Wilson, e
al., 1995) cases.
Two di e en app oaches ha e been used in ob aining
assembly plans. A i s , in e ac i e planne s que ied
he use o geome ic- easoning in o ma ion (Bou 
jaul , 1984; De Fazio and Whi ney, 1987). Mo e
ecen ly, planne s wo k au oma ically om a geome 
ic and ela ional model o he assembly (Home o de
Mello and Sande son, 1991 b) and om a CAD model
and o he non-geome ic in o ma ion (Ames, e al.,
1995; Romney, e al. , 1995).
Wi hin his scope, he ep esen a ion o assembly
plans is an impo an issue. Toe use o And/O
g aphs o his pu pose (Home o de Mello and
Sande son, 1990, 1991a, b) is becoming one o he
mos s anda d ways o ep esen ing all possible
assembly plans. I can be ob ained by s udying he
opposi e p oblem, ha o disassembly, bu main
aining he cons ain s o assembly. Mos au oma 
ic planne s wo k wi h his s a egy. The esul is a
ep esen a ion which is adequa e o a goal-di ec ed
app oach. Mo eo e , Home o de Mello and
Sande son (1990) and Wol e (1992) showed ha his
s uc u e is mo e e icien in mos cases han o he
enume a i e ones.
An op imum assembly plan is now sough , selec ed
om he se o all easible assembly plans. A a ie y
o c i e ia has been used o choosing an op ima! one.
Fo example, Wol e (1988) combines he a ings
ela ed o manipulabili y o subassemblies, ix u e
complexi y, and he numbe o di e en . di ec ions
om which ope a ions a e pe o med, o comple e a
plan. C i e ia including he minimiza ion o eo ien a
ion and ix u e equi emen s we e in oduced by De
Fazio e al. (1990). Hen ioud (1989) p oposed he
aid o an expe abou he ope a ional and logis ic
complexi y, and s a egic ad an ages o selec he bes
assembly ee (plan). Homem de Mello and
Sande son ( 1990) p oposed assigning o he hype a cs
o he And/O g aph weigh s ha depend on he
complexi y o he assembly asks and on he s abili y
o he in e media e sub-assemblies, and using gene ic
sea ch algo i hms such as he AO* o ob ain he bes
plan. Thei p oposal (1991c) o so ne op imiza ion
c i e ia based on maximizing he numbe o di e en
assembly sequences encompassed by he assembly
plan, and on maximizing he amoun o pa allelism
(simul anei y) possible in he execu ion o he assem
bly asks, is used in a heu is ic sea ch algo i hm. In
ano he way, an algo i hm is p oposed in (Holland,
e al., 1992) o a speci ic assembly cell, and o
ba ches o p oduc s.
This pape p esen s an algo i hm A* (Nilsson, 1980;
Pea l, 1984) o ob aining he "bes " assembly plan
o a p oduc in a mul i obo sys em. The app oach
used he e is ha o Home o de Mello and Sande son
(1990; 1991c), bu mo e de ailed in o ma ion o he
assembly asks is conside ed. The algo i hm akes
in o accoun , in addi ion o he assembly imes, he
imes needed o change ools in he obo s. Toe ob
jec i e o he plan is he minimiza ion o he o al
assembly ime (makespan). To mee his objec i e,
he algo i hm s a s om he And/O g aph (com
p essed ep esen a ion o all easible assembly plans)
and he in o ma ion abou each assembly ask ( obo
and ool needed and assembly ime).
The pape is o ganized as ollows: Sec ion 2 de-
sc ibes he p oblem o assembly- ask assignmen . Toe
p oposed algo i hm is desc ibed in Sec ion 3, and
so ne o he esul s ob ained a e p esen ed in Sec ion
4. So ne inal ema ks a e made in he concluding
sec ion.
2. PROBLEM STATEMENT
Toe p ocess o joining pa s oge he o o m a uni
is known as assembly. The joining p ocess esul s in
he connec ion o one pa wi h pa s al eady assem
bled. A sub-assembly is a g oup o pa s ha ing he
p ope y o being able o be assembled independen ly
o o he pa s o he p oduc . An assembly plan is a
se o assembly asks wi h o de ing amongs i s ele
men s. Each ask consis s o joining a se o sub
assemblies o gi e ise o an e e la ge sub-assem
bly. An assembly sequence is an o de ed sequence o
he assembly asks sa is ying all he o de ing con
s ain s. Each assembly plan co esponds o one o
mo e assembly sequences.
An And/O g aph is a ep esen a ion o he se o all
assembly plans possible o a p oduc . Toe O nades
co espond o sub-assemblies, he op node co e
sponds o he whole assembly, and he lea nodes
co espond o he indi idual pa s. Each And nade
co esponds o he assembly ask joining he sub
assemblies o i s wo inal nodes p oducing he sub
assembly o i s ini ial node. In he And/O g aph
ep esen a ion o assembly plans, an And/O pa h
whose op node is he And/O g aph op node and
whose lea nades a e he And/O g aph lea nodes is
associa ed o an assembly plan, and is e e ed o as
an assembly ee. An impo an ad an age o his
ep esen a ion, used in his wo k, is ha he And/O
g aph shows he independence o assembly asks ha
can be execu ed in pa allel. Figu e 1 shows an exam
ple o his ep esen a ion. And nades a e omi ed.
This wo k is cen e ed on he p oblem o choosing he
bes assembly plan, ha is one o he And/O ees o
he And/O g aph. The majo i y o app oaches used
Fig. l. The And/O g aph o he p oduc ABCDE.
up o now make his selec ion in a planning phase in
which nei he he assembly sys em, no how he
assembly asks wi hin i will be ma e ialized, is aken
in o accoun .
This wo k akes in o accoun he physical ealiza ion
o he assembly. I is assumed ha he assembly asks
co espondíng o he And/O g aph ha e been e alu
a ed sepa a ely, in he sense o es ima ing he e
sou ces necessa y o hei ealiza ion ( obo s, ools,
ix u es ... ) as well as hei app oxima e du a ion
imes. These imes should include an es ima ion o
he imes needed o o he ope a ions, such as ans
po a ion o pa s and subassemblies. Po an And/O
g aph wi h a la ge numbe o nodes his is no an
easy ask, and he help o a compu e -aided sys em
is necessa y. Toe nodes co esponding o asks which
a e no ealizable as he adequa e ools a e no a ail
able a e elimina ed om he And/O g aph.
Ano he ac aken in o accoun he e, is he ime
necessa y o changing he ools in he obo s, which
is o he same o de as he execu ion ime o he
assembly asks and he e o e canno be dis ega ded as
in Pa s manu ac u ing. Fu he mo e, he choice is
no limí ed o he assembly plan, bu also speci ies
when each ask is o be ca ied ou in o de o míni
mize he makespan (so ne asks which could po en
ially be ca ied ou in pa allel ha e o be delayed
because hey need common esou ces).
Toe algo i hm can be used in an o -line manne o
ob aining an op imum ini ial solu ion o he assembly
p ocess. Howe e , due on one hand o he lexibili y
o modi ying he con e gence c i e ia o he algo
i hm owa ds a no s ic ly op imum solu ion, and on
he o he o he ac ha as he assembly p ocess
ad ances he esul ing p oblem becomes smalle , he
algo i hm could be applicable on-line o modi y ei he
he plan o he ini ial sequence, in o de o co ec
he a ia ions wi h espec o he ini ial solu ion.
3. ALGORITHM DESCRIPTION
As has been s a ed p e iously, he algo i hm is cen
e ed on he choice o an assembly plan o a com
ple e p oduc in a mul iple- obo sys em, whe::e he
esou ces necessa y o ca ying ou each ask ep e
sen ed in he And/O g aph ( obo s, ools ... ) appea
as da a, as well as he imes necessa y o hei exe
cu ion. As well as he choice o assembly plan, he
execu ion o de s o he asks in each obo a e speci
ied by an analysis o hei execu ion in pa allel in
he assembly sys em gi en.
Because o he se -up o he And/O g aph, he as
sembly p oblem can be s udied, s a ing om he
inal si ua ion and going owa ds he ini ial one.
Toe algo i hm has wo well-di e en ia ed pa s: one
o hem s udies he sequen ial execu ion o assembly
asks, and he o he sol es he pa allel execu ion o
assembly asks ( he ep esen a ion h ough he
And/O g aph allows a na u al s udy o his s age).
This is ac ually he mos complex sec ion, because
he execu ion o asks on one side o he global as
sembly is no independen o he es , and can in lu
ence he execu ion o asks in he o he pa o he
assembly.
Heu is ic unc ions based on he execu ion o asks
aken only om he pa o he ee below he node,
and he ime emaining o he use o ools and obo s
(supposing he mínimum numbe o ool changes, in
o de o main ain he algo i hm as A*) ha e been used
in o de o expand he mínimum numbe o nodes
and a oid edundan nodes.
Because he e is un uppe limí o he makespan, he
pa allel algo i hm does no need o inish when he
bes expec ed cos is highe han ha limi .
Toe algo i hm is used o -line o ob ain an op imum
i s assembly plan. Howe e , as he assembly p o
cess e ol es, i can be used on-line o co ec he
changes which could ha e occu ed du ing he assem
bly p ocess, by p uning he And/O g aph o he
subassemblies al eady pe o med. Toe op imíza ion
c i e ia can easily be changed, acco ding o he pa 
icula needs o he applica ion.
3 .1. Sequen ial Execu ion o Tasks
An algo i hm A· o sea ch o he global assembly
plan can be implemen ed in he ollowing way. Be
ginning wi h an ini ial node whose s a e ep esen s
he comple e assembly ealiza ion, and he e o e
co esponds o he oo node o he And/O g aph
(comple e assembly), all i s possible successo s a e
gene a ed, whose s a es will ep esen he execu ion
a he end o he assembly p ocess o he asks co e
sponding o he And nodes coming om he oo
node o he And/O g aph.
Two ypes o nodes may be gene a ed, depending on
he des ina ion O nodes o each chosen And node. I
a leas one o hese O nodes co esponds o an
indi idual pa , he assembly p ocess will con inue o
be sequen ial, and he node esul ing om he expan
sion may be ea ed as he ini ial node, whe e he
node co esponding o he non- i ial sub-assembly
will ake he place o he oo node.
I , on he o he hand, he applica ion o he ask
s a s om wo sub-assemblies, each wi h a ious
pa s, in he esul ing plan (o plans in gene al) he
ask a angemen is no o ally speci ied ( a ious
possible sequences exis o each assembly plan}, o
asks may be ca ied ou in pa allel. The e is also an
in e dependence amongs he sub-assemblies, because
hey po en ially use he same se o esou ces. Toe
ea men o his ype o node has he e o e o be
unde aken in a di e en way om hose co espond
ing o sequen ial ask execu ion, and his will connec
wi h he second pa o his algo i hm.
Toe e alua ion unc ion used o he nodes gene a ed
in his pa is
(n) = g(n) + h(n), (1)
g(n) being he ime accumula ed in he execu ion o
asks co esponding o he s a e o node n, including
he delays in he necessa y ool changes, and h(n)
being an op imis ic es ima ion o he emaining ime
in which o comple e he global p ocess. (h(n) should
be a lowe bound o he emaining ime o he algo
i hm o be A·.) Due o he ac ha a ious di e en
plans (and he e o e di e en ask se s which would
comple e he assembly p ocess) may be eached om
node n, a de ailed s udy would be compu a ionally
cos ly, and he e o e
h(n) = a(n) · min(pJ (2)
has been chosen, a(n) being he numbe o asks
necessa y o comple e he assembly plan, and p¡ he
p ocessing ime o ask i. As can be seen, i is also
impossible o de e mine he minimum numbe o ool
changes wi hou a de ailed s udy, and he e o e when
es ima ing h(n) i is assumed o be ze o.
All he assembly ees ( ask p ecedence ees) a e
ob ained o he "pa allel" nodes, and a e s udied
sepa a ely. Toe unc ion h (n) co esponding o each
ee is de ined in he ollowing subsec ion.
3.2. Pa allel Execu ion o Tasks
Toe objec i e o his pa o he algo i hm is o de e 
mine he o al minimum ime o he execu ion o he
p ecedence ees ob ained in he p e ious sec ion. In
o de o do his, an algo i hm A* is again used. Toe
nodes o he expansion ee now p esen pa ial in o 
ma ion abou he execu ion o he assembly p ocess.
Conc e ely, a each expansion s ep only one assembly
ask is in oduced, and i s p ocessing ime will a ec
only one o he wo ks a ions, he same s a e being
e ained by he o he wo ks a ions.
Toe s a e co esponding o one node o he expansion
ee is ep esen ed by using he asks a ailable o
in oduc ion in he s a e o he nex s ep, e med
"candida es", and hei ea lies s a ing imes, deno 
ed es ( J. A he same ime, he las ool used is
included o each obo , as well as he inal ime o
use.
Toe e alua ion unc ion o he nodes ob ained by his
algo i hm is simila o (1), being now
g(n) = he la ges o he ea lies s a ing imes o
candida es(n) and he inal imes o he
al eady inished in n wi hou successo s.
h(n) = max(h¡(n),hi(n))
(3)
h1
(n) =es ima ion o he ime emaining i he in e 
dependencies be ween di e en b anches in
he ee a e no aken in o accoun . I is
looked a only in dep h.
hi(n) =es ima ion o ime needed i only he e
maining usage imes o he ools in each
obo a e aken in o accoun , u he sup
posing he numbe o ool changes o be a
a minimum.
Figu e 2 shows a ask p ecedence ee, di e en
expansion nodes and in o ma ion abou hei co e
sponding s a es. l is also accompanied by he Gan
cha s.
Toe heu is ic unc ion h¡(n) can be de ined as ol
lows:
h¡(n) =max ( hl(n,JJ - (n,JJ )
candida es(n)
whe e
(n,J) = g(n) -es (n,J)
hJ(n,J) = h;'(J) +
max ( (l,R;,las ool(RJ -
obo s (es (n,J)-las _ ime(RJ), O)
h;'(J) = p(J) +
max ( h;'(JJ + (l;,R(J),T(J)) ).
successo s o J
(4)
(5)
(6)
(7)
In he abo e exp essions, n is an expansion node, J
is an assembly ask, las _ ool(RJ and las _ ime(RJ a e
he las ool used in obo R; and he ime o las use
espec i ely, and (es (n,J)-las _ ime(RJ) is he exis 
ing ime slack. R(J) and T(J) a e he obo and ool
necessa y o he execu ion o ask J, and p(J) is i s
p ocessing ime. (J,R, T) is he added delay, due o
he ac ha he ool T is being used by obo R in
ask J and successo s, because o he necessa y ool
changes.
No ice ha h¡(J) does no depend on he expansion
nodes, and hus allows one o calcula e a lowe
bound p io o using he A· algo i hm.
.........
R1 T1
p•1
. . . . . . . . . . .
p-4
. . . .
R1 T2
............ ' ........................ '
. . . . . . . . . . . . . . . . . . ' . . . . . . . . . . '
.... . . . . . . . . . . . . . . ' . .
:R2T4
:p-2 J2
R1 T1
J5 p-5 .........
....
p-3 J6 ...........
J1 • o
J2 • O o
R1 • -· 2 4 8 8 10 TIME
R2- -·
g . o
J1 J1
J2 • O
J3 • 1
J4 • 1
R1 • T1 • 1 R1 T1
R2. ····-· R2
g . 1
J4
J2 • 8
J3. 3
J6. 4
R1 • T1 -1
R2·T3-3 R1
g . R2
J2
J3. 11
J5 • 8
J6 • 4
R1 • T1 -1
R2 • T4 • 8 R1 T1
g . 11 R2 ... T4
T3
Fig. 2. A ask p ecedence ee, so ne expansion nodes, and hei co esponding Gan cha s.
h2 can be de ined as ollows:
hi(n) =max ( h;(n,RJ - (n,RJ )
obo s (8)
whe e
(n,RJ = g(n) -las _ ime(RJ (9)
and hln,RJ is he minimum ime o use o obo R;
wi hou conside ing he ask p ecedence cons ain s.
Fi s simpli ica ion: Each ool is associa ed wi h only
one obo . The calcula ion o hin,R) is equi alen o
he a elling salesman p oblem, when conside ing
he ools no ye used and an ini ial node co espond
ing o he las -used ool in he obo R.
h;(n,R) = L 1 (J'J + ool-change imes (10)
T¡E T(R)
wi h 1 (J'J he emaining ime o usage o ool T.
Second simpli ica ion: Tool-changing imes do no
depend on he ype o ool.
hi(n) could be imp o ed by using he ea lies usable
ime o R ins ead o using (n,RJ. No ice ha asks
no included in n should be conside ed in his case.
De ini ion: A ask ; is compa ible wi h [including]
ask j i , on including his ask a he ollowing le e!,
he s a o ; and ha o i s successo s in he ask
p ecedence ee a e no delayed.
This de ini ion allows he numbe o expanded nodes
o be minimized. The candida es asks compa ible
wi h ano he ask included in he nex le e! will be
included in successi e le els.
The expansion o a node is ca ied ou by he algo
i hm shown in Fig. 3.
No ice ha he algo i hm can be ex ended o he case
whe e he e is mo e han one candida e ool o
each assembly ask. A lis o candida e ools has o
P ocedu e Expand(n)
Le J = {11, ... ,JJ be he s o candida es(n) and
EST = {es ,, ... ,es J i s ea lies s a ing imes.
es _min = min(es J
l he e is jus one ask l¡ wi h es ¡
= es _min
lnclude in open a nade whose s a e is ha o n plus J,
/ he e a e asks no compa ible wi h l¡
Expand(n), es ided o l'= {Jm, wi h lm
no compa ible wi h JJ
endi
else
Le NTI, be he numbe o asks no compa ible wi h J,,
and Nl1_min = min(Nl7¡), o es ¡=es _min
lnclude in open a nade whose s a e is ha o n plus J,,
wi h J, such ha Nl1=Nl1_min
/ NI1_min�O
Expand(n), es ic ed o l'= {Jm
, wi h Jm
no compa ible wi h J J
endi
endi
Fig. 3. Algo i hm o he expansion o nodes.

be conside ed when expanding he nodes. A e y
simple heu is ic unc ion consis ing o only conside 
ing he assembly imes o he emaining asks could
be used. A mo e in o med heu is ic unc ion would
equi e a mo e complex algo i hm.
4. RESULTS
Toe algo i hm has been es ed in a a ie y o si ua
ions, conside ing di e en p oduc s uc u es (num
be o pa s, numbe o connec ions be ween pa s),
di e en ypes o And/O g aphs (numbe o sub
assemblies, numbe o assembly asks o each sub
assembly), and di e en assembly esou ces (numbe
o obo s, numbe o ools).
Toe solu ion ob ained o he assembly ask assign
men o he lashligh shown in Fig. 4 (Homem de
Mello and Sande son, 1990c) is shown in Fig. 5. Toe
assembly en i onmen was composed o wo obo s
and wo assembly ools pe obo . Toe o iginal com
ple e And/O g aph con ains 35 And nodes, 24 O
nodes and 37 possible assembly plans, and is no
shown o he lack o space. Toe Gan cha s co e
sponding o he solu ion a e shown in Fig. 6.
5. CONCLUSIONS
An A· algo i hm o ob aining he op imum assembly
plan o a mul i obo en i onmen has been p esen 
ed. The algo i hm minimizes he makespan o he
assembly.
To apply he algo i hm, possible assembly asks
should be speci ied by an And/O g aph. Toe algo
i hm needs he de ini ion o he necessa y ools and
an es ima ion o he ime equi ed o each assembly
ope a ion.
The algo i hm has been es ed wi h p oblems o
di e se complexi y.
6. ACKNOWLEDGMENT
The au ho s would like o acknowledge CICYT o
unding he wo k. Toe au ho s would also like o
ex end hei hanks o he anonymous e e ees o
hei help ul sugges ions.
7. REFERENCES
Ames, A.L., T.L. Cal on, R.E. Jones, S.G.
Kau man, C.A. Laguna and R.H. Wilson
(1995). Lessons Lea ned om a Second Gene 
a ion Assembly Planning Sys em. P oc. 1995
IIINQ U!NS IUIJI IIEA.SCTOR BATTBIY END
Fig. 4. P oduc example: a lashligh .
111
IIM.
ao
L E
Fig. 5. T ee solu ion o he p oduc example ob
ained om he And/O g aph.
TASK CHANGE TASK TASK TASI<
R1 31 TOOL 11 4
TASI< CIWIQE �
R2 30 TOOL
TIME
Fig. 6. Gan cha s o he ee solu ion in a wo
obo en i onmen .
IEEE In l. Symp. on Assembly and Task Plan
ning, pp. 41-47.
Boneschansche , N. (1993). Plan Gene a ion o
Flexible Assembly Sys ems. PhD hesis Del
Uni e si y o Technology, Del , Toe Ne he 
lands.
Bou jaul , A. (1984). Con ibu ion a une App oche
Mé hodologique de l'Assemblage Au oma isé:
Elabo a ion Au oma ique des Séquences
Opé a oi es. These d'é a , Uni e si é de
F anche-Com é, Besaneon, F ance.
De Fazio, T.L., T.E. Abell, G.P. Ambla d, O.E.
Whi ney (1990). Compu e -aided assembly
sequence edi ing and choice: Edi ing c i e ia,
bases, ules, and echnique. P oc. IEEE In .
Con . Sys . Eng., pp. 416-422.
De Fazio, T.L. and O.E. Whi ney (1987). Simpli ied
Gene a ion o All Mechanical Assembly Se-
quences. IEEE J. Robo ics and Au oma ., Vol.
3, No. 6, pp. 640-658. Also, Co ec ions, Vol.
4, No. 6, pp. 705-708.
Hen ioud, J.M. (1989). Con ibu ion a la
concep ualisa ion de l'assemblage au oma isé:
nou elle app oche en ue de dé e mina ion des
p ocessus d'assemblage. These d'é a ,
Uni e si é de F anche-Com é, Besancon,
F ance.
Holland, W. an, N. Boneschansche and W.F.
B ons oo (1992). Task Assignmen in a Flexi
ble Assembly Cell Using And/O G aphs. P oc.
23 d /n . Symp. lnd. Robo s. Ba celona, Spain,
Oc obe 6-8, pp. 653-658, 642.
Homem de Mello, L.S. and A.C. Sande son (1990).
And/O G aph Rep esen a ion o Assembly
Plans. IEEE T ans. Robo ics Au oma . Vol. 6,
No. 2, pp. 188-199.
Homem de Mello, L.S. and A.C. Sande son (1991a).
Rep esen a ions o Mechanical Assembly Se
quences. IEEE T ans. Robo ics Au oma . Vol.
7, No. 2, pp. 211-227.
Home o de Mello, L.S. and A.C. Sande son (1991b).
A Co ec and Comple e Algo i hm o he
Gene a ion o Mechanical Assembly Sequences.
IEEE T ans. Robo ics Au oma . Vol. 7, No. 2,
pp. 228-240.
Home o de Mello, L.S. and A.C. Sande son (1991c).
Two C i e ia o he Selec ion o Assembly
Plans: Maximizing he Flexibili y o Sequencing
he Assembly Tasks and Minimizing he Assem
bly Time Th ough Pa allel Execu ion o Assem
bly Tasks. /EEE T ans. Robo ics Au oma . Vol.
7, No. 5, pp. 626-633.
Ka aki, L., J.C. La ombe and R.H. Wilson (1993).
On he Complexi y o Assembly Pa i ioning.
ln o ma ion P ocessing Le e s. Vol. 48, pp.
229-235.
Ka aky, L. and M. Koloun zakis (1995). Pa i ion
ing a plana assembly in o wo connec ed pa s
is NP-comple e. ln o ma ionP ocessing Le e s.
Vol. 55, pp. 156-165.
Kusiak, A. (1990). ln elligen Manu ac u ing Sys
ems. P en ice-Hall In e na ional Se ies in Indus
ial and Sys ems Enginee ing.
Ma ensson, N. (1990). Robo Abili y o he 90's.
P oc. 21s ln . Symp. lnd. Robo s. Copenhagen,
Denma k, Oc obe 23-25, 1990, pp. 193-198.
Nilsson, N.J. (1980). P incipies o/ A i icial ln elli
gence. Chenanso Fo ks, NY: Tioga.
Pea l, J. (1984). Heu is ics: In elligen Sea ch S a e
gies o Compu e P oblem Sol ing. Reading,
MA, Addison-Wesley.
Romney, B., C. Goda d, M. Goldwasse , G.
Ramkuma (1995). An E icien Sys em o
Geome ic Assembly Sequence Gene a ion and
E alua ion. P oc. 1995 ASME In ema ional
Compu e s in Enginee ing Con e ence, pp. 699-
712.
Wilson, R.H., L. Ka aki, T. Lozano-Pé ez and J.C.
La ombe (1995). Two-Handed Assembly Se
quencing. ln ema ional Joumal o/ Robo ic
Resea ch. Vol. 14, pp. 335-350.
Wol e , J. (1988). On he au oma ic gene a ion o/
plans o mechanical assembly. Ph.D. hesis.
Uni . o Michigan. Depa men o Compu e ,
In o ma ion and Con ol Enginee ing, Sep em
be 1988.
Wol e , J. (1992). A Combina o ial Analysis o
Enume a i e Da a S uc u es o Assembly
Planning. Joumal o/Design and Manu ac u ing.
Vol. 2, No. 2, June 1992, pp. 93-104.