CALCULO AUTOMATICO DE SECUENCIAS DEENSAMBLADO BASADO EN UNA TECNICA DEAGRUPACION PARA LA CONSTRUCCION DE

ESTRUCTURAS MEDIANTE EQUIPOS DE ROBOTS

Alvaro Sempere, Ivan Maza y Anıbal OlleroGrupo de Robotica, Vision y Control, Universidad de Sevilla

sempere1987@gmail.com,imaza@us.es,aollero@us.esResumen

Este trabajo aborda el calculo automatico de la se-cuencia de ensamblado que permite construir unadeterminada estructura tipo celosia a partir delanalisis geometrico 3D de la misma. Dicho calcu-lo constituye el primer bloque del modulo de pla-nificacion de un equipo de robots aereos equipadoscon brazos manipuladores al cargo de la construc-cion de la estructura en lugares de difıcil acceso.En el calculo de la secuencia de ensamblado se haaplicado la tecnica conocida en la literatura como“assembly-by-disassembly” a partir de los grafosNDBG (Non-Directional Blocking Graphs) obte-nidos en el analisis geometrico de la estructura.En el artıculo se presenta una heurıstica novedo-sa basada en agrupar piezas de cara a obtener unplan de construccion lo mas paralelizable posible.

Palabras clave: ensamblado automatico, mani-pulacion aerea, planificacion automatica, grafosNDBG

1. INTRODUCCION

El trabajo que se presenta en este artıculo se en-marca dentro del proyecto europeo ARCAS finan-ciado por la Comision Europea. Uno de los objeti-vos de dicho proyecto es la construccion de estruc-turas tipo celosia (ver figura 1) usando un conjun-to de robots aereos equipados con brazos manipu-ladores. La motivacion de usar estos robots vienedel interes practico de realizar estos montajes enlugares de muy difıcil acceso por medios conven-cionales.

Figura 1: Estructura tipo celosia correspondientea una torre

En diversos artıculos se han abordado distintastecnicas para la obtencion de la secuencia de en-samblado de piezas complejas. Este artıculo secentra en un criterio importante: el calculo de lasecuencia que permite aumentar el grado de pa-ralelizacion en su construccion. Por ello nuestroobjetivo es calcular una secuencia de construccionfactible, que necesite el mınimo numero de pasospara su construccion completa.

2. TRABAJOS RELACIONADOS

El problema concreto abordado en este trabajo esel de obtener la secuencia de operaciones de en-samblado, en adelante OE, para una estructuradada. En [9] podemos encontrar una clasificacionde los tipos de estructuras enumerando una se-rie de caracterısticas intrınsecas de cada una deellas: secuencialidad; monotonicidad, la nece-sidad de realizar desplazamientos de las piezas aunas posiciones intermedias; y coherencia, cadapieza conectada hace contacto con las ya coloca-das previamente. Las estructuras abordadas en es-te trabajo son secuenciales para dos robots,monotonas y coherentes. A continuacion se re-visan los trabajos de la literatura que abordan elanalisis geometrico de la estructura, el modo derepresentar las secuencias de ensamblado y los al-goritmos para el calculo de dichas secuencias.

2.1. Analisis geometrico

Varios autores han introducido ideas como el grafode enlaces para determinar los contactos existen-tes entre piezas. En la referencia [3] se especificanlas uniones existentes entre piezas y el tipo concre-to, mientras que las referencias [14, 5] se represen-tan dichos grafos como matrices de contactos endeterminados vectores. Tambien hay especificacio-nes mas concretas [16] que indican las posicionesde las piezas mediante predicados (pieza 1 encimade pieza 2, pieza 2 en +x con pieza 5, etc.). Sehan aplicado grafos relacionales para analizar lasdistancias entre piezas desde sus vertices y/o aris-tas [10] y se empleado el espacio de configuraciono C-space en [6, 7] para definir un area geometri-ca que indica para cada dos piezas la region de

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

703

Figura 2: Construccion de la region PQ desde unvertice de P . Como puede observarse esta regioncrea dos lıneas desde el vertice origen indicandoel angulo de seccion de S que no puede cruzarse,esto es, siempre que se traslade P hacia un ~v fuerade la seccion, no existira colision

Figura 3: Representacion de un grafo AND/ORcon todas las secuencias posibles para el ensam-blado de un portico

libre contacto entre ellas. En particular en [6] sehace alusion a la operacion P Q, la diferenciade Minkowski (ver figura 2), determinando ası lazona libre de obstaculo entre dos polıgonos P y Q.

2.2. Representacion de secuencias deensamblado

En este ambito existen un cierto numero de traba-jos que van desde la creacion de tecnicas base cla-ramente diferenciables hasta las constantes adap-taciones realizadas a partir de estas. Una primeracategorıa podrıa ser la tecnica que hace uso delconocido grafo AND/OR, presentada en [8] y queha sido citado en numerosas ocasiones en el ambi-to de la secuenciacion. Se calcula la combinatoriatotal y se representa en un grafo AND/OR, en elcual las ramas AND (bifurcaciones con el sımbolodel angulo en la figura 3) indican descomposicionen una unica pieza o en un subconjunto, mien-tras que las OR (distintos caminos dobles desdeun mismo nodo) permite diversificar el camino dedesmontaje presentando varias posibilidades.

Por otro lado en [6] se analiza un algoritmo basadoen el motion space estableciendo las traslaciones

que hay que seguir para ensamblar la estructurausando trayectorias comprendidas en las areas delC − space. Tambien es posible estudiar la viabili-dad de las secuencias a partir de bases de conoci-miento [3], por geometrıa [14], con algoritmos ad-hoc [18] diferenciando entre conectores y piezas,o desde la construccion de grafos de interseccionNDBG (Non-Directional Blocking Graph) [17].

2.3. Metodos para el calculo de lassecuencias de ensamblado

Un metodo ampliamente usado es el denomina-do assembly-by-disassembly. Se parte de la es-tructura inicial, se van obteniendo las distintaspiezas o subconjuntos que pueden ser desconecta-dos (actualizandose la estructura en cada paso) yse vuelve a repetir el proceso hasta que queda com-pletamente desconectada. Esta tecnica puede apli-carse sobre la representacion basada en los grafosde interseccion NDBG mencionados anteriormen-te, donde a partir de los bloqueos entre piezas sepueden obtener las distintas desconexiones (tam-bien conocidas como descomposiciones) a lo largodel desmontaje completo.

Hay otros algoritmos basados en colonias de hor-migas [16, 15, 5], uso de redes neuronales [13],tecnicas evolutivas [4, 11] y sistemas inmunitarios[2]. Otra tecnica interesante es la de [12], que apartir del grafo de enlaces transformado en unamatriz de uniones, calcula una secuencia factibleeliminando sucesivamente las columnas de las par-tes ya colocadas en el ensamblado y examinandolas filas para otras uniones candidatas.

Todos estos algoritmos pueden ser ajustados pa-ra obtener la secuencia factible desde el punto devista geometrico o para la optimizacion en basea una serie de caracterısticas como el numero dereorientaciones [16], herramientas usadas, numerode piezas movidas, etc. Tambien hay algoritmosbasados en redes de Petri que sirven para evaluarel grado de dificultad de una secuencia, pudiendoobtener la optima [1].

3. SOLUCION ADOPTADA

El esquema de diseno que se ha seguido para re-solver el problema se presenta en la figura 4 y sebasa en los siguientes modulos: calculo del NDBG,aplicacion de la tecnica assembly-by-disassembly,heurısticas de seleccion, seleccion de la secuenciaoptima y construccion final. Dentro de esta seccionse describen los distintos modulos.

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

704

Figura 4: Esquema propuesto para la obtencion dela secuencia de ensamblado

3.1. Calculo del grafo NDBG

Sea S una estructura, si ⊆ S un subconjunto depiezas y gS el grafo DBG, Directional BlockingGraph de S en una direccion ~t, definimos gS(~t)como un grafo dirigido G = (V,E) con:

V 6= 0

E ⊆ {(a, b) ∈ V × V : a 6= b} , (1)

donde (a, b) es una arista con origen en a y destinoen b, y el conjunto V son los vertices, cumpliendoque el nodo ni ∈ V se identifica con la pieza Pi dela estructura S.

Si una pieza P ∈ S colisiona con otra Q ∈ S alo largo de ~t entonces (P,Q) ∈ gS(~t), siguiendo ladefinicion de la expresion (1). El conjunto de to-dos los gS(~v) para cualquier direccion ~v formara elgrafo NDBG, en adelante GS .

Sea w = (n1, n2, ..., nk) el camino de nodos co-menzando en n1 y terminando en nk. Se define unconjunto fuertemente conectado CFC de gS(~v) co-mo aquel subconjunto maximal de nodos tal que

∀nj ∈ gS(~v) ∧ ∀nk ∈ gS(~v) → (2)

∃w = (nj , nj+1, ..., nk−1, nk) ∧(nj+1, ..., nk−1) ∈ gS(~v) .

Es decir para cualquier par de nodos (n1, n2) ∈gS(~v) existe un camino de n1 a n2 y ademas todoslos nodos del camino pertenecen a gS(~v). Sabien-do esto, los conjuntos fuertemente conectados deun grafo gS(~v) se traducen a subconjuntos de pie-zas o simplemente piezas unicas que pueden serdesconectados de S.

Sea d~t una descomposicion o un CFC representa-do como una lista de piezas que pueden ser des-conectadas hacia una direccion ~t, y sea D el con-junto desconectable que incluye todas las descom-posiciones posibles, se dice que un conjunto de npiezas pertenece a D si

{n|(n, pi)/∀pi ∈ S ∧ (n, pi) /∈ gS(~tj)

}∈ d~tj

. (3)

En la figura 5 se observa un ejemplo que ilustralos distintos gS(~v) que componen el conjunto GS .Cada uno esta asociado a una direccion concreta,de tal manera que el espacio posible es una circun-ferencia S2. Por el contrario, para una estructuraen tres dimensiones el espacio de direcciones serıauna esfera S3 tal que

GS =k=n⋃k=1

gS(~tk) (4)

∀~tk ∈ Sj , n =∣∣∣~d∣∣∣ .

Figura 5: Representacion del conjunto GS comple-to para una estructura. Se pueden ver los distintosgrafos gS(~v) agrupados por secciones donde ~v ∈ S2

Cabe notar que un nodo P1 que no interseccio-ne con otro P2 en gS(~t1) asegura que P1 no cho-cara con P2 desde su posicion actual ~x hasta~x + ~t1 · ∞. Esto es ası porque una de las carac-terısticas de las estructuras abordadas en este tra-bajo es la monotonıa: las piezas nunca necesitantrasladarse a posiciones intermedias para su des-conexion.

Como se vera mas adelante el proceso de desen-samblado es iterativo hasta que la estructura que-da totalmente desconectada, esto es, ∀ni y ∀gS(~tj)con ni ∈ gS(~tj) se cumple que ni no tiene ningunarco, ni de entrada ni de salida. Finalmente se cal-cula la secuencia de montaje como la inversa de lasecuencia de desmontaje obtenida y con sus tras-laciones invertidas.

Por ultimo anadir que aunque en [17] se hable derotaciones para desconectar las piezas o incluso de

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

705

traslaciones multiples en [7], en este trabajo sola-mente se consideran traslaciones de un paso.Esto permite cumplir las definiciones de los gra-fos de interseccion vistas mas arriba y la expre-sion (3). Asimismo como direcciones de traslacionpara construir el NDBG se han empleado las co-rrespondientes a cada uno de los ejes cartesianosen ambas direcciones: ±x,±y,±z.

3.2. Tecnica “assembly-by-disassembly”y heurısticas de seleccion

Tomando como partida el conjunto GS , se haempleado el algoritmo 1 para obtener la secuen-cia de ensamblado. En dicho algoritmo la funcioncalcDesconectable calcula el conjunto desconecta-ble D para cualquier direccion ~v del GS actual y laeleccion correspondiente de una d ∈ D o varias deellas. Dicha funcion se describe en el algoritmo 2.

GS ←− Construye grafo de intersecciones ;Secuencia ←− inicializar lista;while existan piezas conectadas en GS do

D∗ ←− calcDesconectable(GS);Actualizar informacion en GS ;Anadir D∗ en Secuencia;

endAlgorithm 1: Algoritmo base de secuenciacion

Sea D∗ un subconjunto desconectable que con-tiene varias descomposiciones y que cumple queD∗ ⊆ D. La variable Secuencia es una lista dedescomposiciones di ∈ D∗ y tras pasar por elmodulo denominado construccion final (ver figu-ra 4), dicha variable contendra las operaciones deensamblado OE en su orden correcto (ver sec-cion 3.4).

ListaDescomposiciones ←− lista de conjuntosfuertemente conectados;for ∆←− ListaDescomposiciones do

if H(∆) = true thenD∗ ←− Anade ∆;

else

end

endAlgorithm 2: Funcion que selecciona descompo-siciones ∆ en base a la funcion heurıstica H(∆)que se describe en la seccion 4, y que sirve paraconstruir un subconjunto desconectable D∗

En base a estos algoritmos y siguiendo el esquemade la figura 4, el modulo assembly-by-disassemblyse encarga de calcular la lista de descomposicio-nes, y este a su vez se comunica con el moduloque implementa las heurısticas de seleccion. Esteultimo modulo selecciona una o varias descompo-siciones en funcion de un criterio concreto en base

a la funcion H(∆). Por tanto se tiene un ciclo deconsultas continuo entre modulos para decidir lasdescomposiciones a seleccionar.

3.3. Seleccion de secuencia optima

Una vez el bucle del algoritmo 1 finaliza, la es-tructura queda completamente desconectada y lasecuencia calculada pasa al siguiente modulo en-cargado de seleccionar la secuencia optima. Tantoen este modulo como en la funcion H(∆) se me-dira la calidad de una descomposicion o de la se-cuencia completa usando la aproximacion que seexplicara en la seccion 4.1.

3.4. Construccion final

Finalmente las secuencias seleccionadas pasan alultimo modulo encargado de construir la lista deOE a partir de la secuencia de desmontaje obte-nida cambiando el orden de las operaciones, invir-tiendo las traslaciones y realizando procesamien-tos opcionales, como por ejemplo especificar lasposiciones de las piezas a lo largo de la secuenciacalculada.

El formato seguido para la representacion de la se-cuencia toma como base el lenguaje PDDL (Plan-ning Domain Definition Language). Cada accionde montaje sera una OE caracterizada por el tipo(pieza fija o movil), vector de traslacion, partes in-volucradas, efectos que indican la posicion de laspiezas colocadas y precondiciones que determinanlas posiciones de las piezas objetivo a las que seconectan las involucradas en esta operacion.

En la siguiente seccion se describen con mas de-talle los modulos encargados de la heurıstica deseleccion y de la seleccion de secuencia optima,enumerando distintas tecnicas implementadas pa-ra lograr la secuencia optima paralela con menornumero de pasos para su construccion.

4. TECNICAS DE BUSQUEDASDE LA SOLUCION

4.1. Definicion de ındice de una secuenciao descomposicion

Se han definido dos ındices para medir la cali-dad de una secuencia: ındice basado en el numerode movimientos requeridos (Im) e ındice de pa-ralelizacion (Ip). Ambos usan filosofıas parecidas,basandose en la adicion de un contador a cadapieza. Un contador cP asociado a una pieza P in-dicara a partir de que instante concreto puede co-nectarse una pieza cualquiera a P . Dicho contadorpermite incorporar de manera sencilla el dominiotemporal a la planificacion. El calculo de Ip y Im

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

706

explicado a continuacion se realiza en el moduloque selecciona la secuencia optima siguiendo unenfoque de busqueda global.

Sea un subconjunto TOE de piezas trasladas deuna operacion de ensamblado concreta OE y COE

el conjunto de piezas a las que se conectan TOE , elalgoritmo 3 se ha empleado para calcular los con-tadores de una secuencia. Cada vez que se mueveuna pieza p, su contador cp es incrementado.

Inicializar contadores a 0 de cada pieza;for OE ←− secuencia do

for PiezaM ←− TOE docPiezaM + +

endfor PiezaC ←− C∗

OE docPiezaC + +

end

endAlgorithm 3: Funcion que calcula los contadoresde una secuencia dada. Se define C∗OE como elconjunto de piezas ∈ COE tal que interseccionencon TOE en la direccion de traslacion de OE

Para el ındice Im se calcula la suma de todos loscontadores

∑ni=1 cpi

, mientras que para Ip se em-pleara el maximo de los contadores max(cpi), dadoque este ultimo ındice indica el numero de pasosnecesarios para el montaje. Como metrica de refe-rencia se usara normalmente la del Ip, dejando laprimera para comparar con secuencias en las quese minimice el numero de traslaciones para cadapieza. No obstante con Im se tiene una definicionde la calidad de secuencia mas precisa, ya que elintervalo de valores va desde |POE | a∞, incremen-tando por cada OE el valor conjunto en r, siendor = +(|TOE |+ |C∗

OE |). Es decir, se incrementa enel numero de piezas de los conjuntos T y C parala OE actual, que en el peor de los casos sera 2.Por el contrario Ip suele incrementarse en menormedida.

A continuacion se describen las dos tecnicas deoptimizacion (heurısticas de seleccion) que se handesarrollado. Estas tecnicas se centran en el algo-ritmo 2.

4.2. Ramificacion y poda (BF)

Inicialmente se desarrollo un algoritmo de fuer-za bruta (brute force, BF) que sirviera de refe-rencia para evaluar las nuevas tecnicas. Para elalgoritmo 1 se trata de que el bucle recorra lossubconjuntos de piezas en profundidad, esto es,si una desconexion genera un nuevo subconjunto,el algoritmo inspecciona este ultimo hasta desco-nectarlo completamente, y ası hasta terminar contodos. Introduciendo una cota en la ejecucion pa-

Figura 6: El GS obtiene que los tornillos del 1 al4 son desconectables, pero se ve claramente queen vez de realizar 4 operaciones separadas podrıarealizarse solamente una con los 4 tornillos

ra evitar seguir calculando secuencias que superenuna metrica umbral y realizando un computo par-cial de la metrica para las secuencias parcialmenteconstruidas, se consigue reducir el tiempo de eje-cucion Tc, pero no tanto como para que esta tecni-ca sea util de cara a estructuras complejas comose vera en la seccion 5.

4.3. Tecnica de agrupacion (TA)

En este caso, a lo largo de las operaciones se de-tecta que existen varios subconjuntos que podrıandesconectarse a la vez, esto es, mediante una uni-ca operacion de desmontaje. Con esta simple ideael despliegue de un arbol de ejecucion se reducedrasticamente. Para la estructura de la figura 6con BF se obtienen 4! secuencias en el peor de loscasos y solamente una con la tecnica de agrupa-cion.

Para realizar esta agrupacion de desconexiones sedeben seguir las siguientes reglas:

Los subconjuntos no pueden tener piezas encomun. Esto darıa lugar a incongruencias,apareciendo en la secuencia operaciones co-mo (conectar A y B a C) y (conectar B a C)a la vez, algo carente de sentido fısico.

Siguiendo las definiciones vistas en la sec-cion 4.1, para dos descomposiciones a agru-par ∆1 y ∆2 y dos piezas p1 y p2, no puedecumplirse que

(p1 ∈ T∆1∧ p1 ∈ C∗

∆2) ∨ (5)

(p2 ∈ T∆2∧ p2 ∈ C∗

∆1) . (6)

Esto evita situaciones en las que se desconec-tan dos subconjuntos de piezas en traslacionestales que existe colision geometrica.

Con todo esto se evita un proceso muy determinis-ta en el calculo de la secuencia, dando lugar a unpequeno abanico de posibilidades aun realizandola agrupacion, y se consigue ademas decrementarel tiempo de computo Tc considerablemente.

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

707

4.4. Caracterısticas de las tecnicas BF yTA

Las distintas caracterısticas son enumeradas acontinuacion:

Ejecucion independiente. Sea Ni el nume-ro de secuencias de un subconjunto i, |Si| .Sabiendo que el algoritmo 1 sigue un compor-tamiento en profundidad por cada uno de lossubconjuntos generados a partir de las des-composiciones del assembly-by-disassembly,el numero de secuencias con BF serıa de∏i=n

i=1 Ni. Para cada subconjunto de mane-ra independiente la mejora es considerable:∑i=n

i=1 Ni.

Cacheado de subconjuntos. A partir delo anterior se determina que es posible in-cluso almacenar las secuencias calculadas delos subconjuntos, de tal manera que se evi-ten calculos redundantes. Experimentalmentese ha visto que para estructuras de 12 piezasexisten mas de 5000 coincidencias.

Combinaciones de subconjuntos. Esto esuna caracterıstica para evitar ejecuciones ma-sivas. No es mas que diferenciar el caso de ob-tener desconexiones solo de subconjuntos pre-sentes en el perımetro de la estructura o biencalcular todas las posibles combinaciones desubconjuntos.

5. ANALISIS DE LASTECNICAS PROPUESTAS

Se define la complejidad de una estructura C co-mo la suma del numero de arcos de todos los gra-fos del conjunto GS . Dicha complejidad se empleasiempre en el eje horizontal de las graficas de estaseccion.

Las figuras 7 y 8 comparan los tiempos de ejecu-cion Tc de las tecnicas BF y TA. En la figura 7 sepuede comprobar la diferencia en Tc para la tecni-ca BF , analizando el uso del cacheado de sub-conjuntos. Con complejidades superiores a 120el Tc se hace demasiado alto. Se puede observar laexistencia de un maximo en la complejidad 108 yuna bajada en la siguiente estructura mas comple-ja. Eso se debe a los subconjuntos obtenidos: unaestructura a la que en un momento dado se le pue-dan desconectar 10 piezas individuales tendra mu-cho mas Tc que otra con 2 subconjuntos de 3 piezascada una, ya que la casuıstica es mucho mayor enel primer caso.

En la figura 8 se analiza la tecnica TA cuandose emplean descomposiciones perimetrales o todas

las combinaciones posibles. Como es obvio la ca-suıstica para todas las combinaciones es inmensa yel Tc aumenta. No obstante los tiempos son meno-res que en la figura 7 para las mismas estructuras.

En la figura 9 se muestra la comparativa a efec-tos de calidad de la secuencia en base a los ındicesIm e Ip. Se aprecia que los Im del metodo BFson peores que los obtenidos mediante la tecnicaTA a partir de cierto punto (cuando teoricamen-te deberıan ser iguales o mejores). La explicaciones que a partir de una complejidad 120, el meto-do BF obtiene resultados incompletos debido alexcesivo Tc que obliga a detener la ejecucion. Sepuede observar tambien que tomando todas lascombinaciones posibles, el TA obtiene mejores se-cuencias que TA con solo perimetrales. Tambienes importante explicar que desde 100 hacia atraslos resultados son identicos, con lo cual las secuen-cias obtenidas con la tecnica TA son tan optimascomo las del metodo BF de referencia.

Por ultimo en la figura 10 se observa el mismofenomeno explicada anteriormente para el metodoBF . A partir de una complejidad 54, el numerode pasos necesarios para construir los montajes esel optimo (3) tanto con descomposiciones superfi-ciales o perimetrales como para todas las combi-naciones.

6. CONCLUSIONES YDESARROLLOS FUTUROS

Se ha comprobado que la tecnica TA desarrolla-da ofrece buenos resultados, tanto en tiempos deejecucion como en las metricas empleadas para va-lorar las secuencias. Asimismo, se ha visto que lametrica del numero de movimientos Im en la se-cuencia ofrece peores resultados que la Ip. En lapractica, Im intenta dejar el maximo numero depiezas sin mover, como piezas base, a costa de mo-ver subconjuntos muy grandes, incrementando sucontador. Por el contrario la Ip intentara desplazartodos los subconjuntos que pueda para un mismopaso. Por ejemplo, en el primer paso de desmonta-je desconectara todos los subconjuntos que modi-fiquen los Im lo mınimo posible, mejorando ası laparalelizacion de la secuencia.

Como se ha visto en el presente artıculo, hay unabusqueda local en la parte de la seleccion de unao varias descomposiciones y una busqueda globalcuando se elige una o varias secuencias de entretodas las generadas. Siguiendo esta lınea se podrıadefinir otra metrica como Msec = E+P , en la queE serıa el esfuerzo generado hasta una fase (me-dicion de las operaciones anteriores a la actual enla secuencia que se esta generando) y P una me-dida probabilıstica que indicarıa un valor aproxi-

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

708

Figura 7: Tc de ramificacion y poda

Figura 8: Tc de la tecnica TA

Figura 9: Im de ramificacion y poda frente a TA

Figura 10: Ip de BF frente a TA

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

709

mado del esfuerzo que falta para completar la se-cuencia en caso de elegir una descomposicion con-creta. Asimismo, como desarrollo futuro tambiense podrıa disenar otro algoritmo para seleccionaraquellas descomposiciones que mas componentesconexas del grafo genere tras su descomposicion,ademas de que dichas componentes dispongan deun numero de piezas parecido.

Agradecimientos

Este trabajo ha sido financiado parcialmente porel proyecto ARCAS (ICT-2011-287617) del septi-mo Programa Marco de la Comision Europea y losproyectos nacionales RANCOM (P11-TIC-7066) yCLEAR (DPI2011-28937-C02-01).

Referencias

[1] D. Ben-Arieh, R.R. Kumar, and M.K.Tiwari. Analysis of assembly opera-tions’difficulty using enhanced expert high-level colored fuzzy petri net model. Robo-tics and Computer-Integrated Manufacturing,20(5):385–403, 2004.

[2] P.-B. Cao and R.-B. Xiao. Assembly plan-ning using a novel immune approach. Inter-national Journal of Advanced ManufacturingTechnology, 31(7-8):770–782, 2007.

[3] C.K. Choi, X.F. Zha, T.L. Ng, and W.S. Lau.On the automatic generation of product as-sembly sequences. International Journal ofProduction Research, 36(3):617–633, 1998.

[4] S.D. Dao and R.M. Marian. Geneticalgorithms for integrated optimisation ofprecedence-constrained production sequen-cing and scheduling. Lecture Notes in Elec-trical Engineering, 130 LNEE:65–80, 2013.

[5] Jifeng Guo, Ping Wang, and Naigang Cui.Adaptive ant colony algorithm for on-orbitassembly planning. In Industrial Electronicsand Applications, 2007. ICIEA 2007. 2ndIEEE Conference on, pages 1590–1593, 2007.

[6] D. Halperin, J.-C. Latombe, and R.H. Wil-son. A general framework for assembly plan-ning: The motion space approach. Algorith-mica (New York), 26(3-4):577–601, 2000.

[7] D. Halperin and R.H. Wilson. Assemblypartitioning along simple paths: The caseof multiple translations. Advanced Robotics,11(2):127–145, 1997.

[8] Luiz S. Homem de Mello and Arthur C. San-derson. And/or graph representation of as-sembly plans. IEEE Transactions on Roboticsand Automation, 6(2):188–199, 1990.

[9] P. Jimenez. Survey on assembly sequencing:a combinatorial and geometrical perspective.Journal of Intelligent Manufacturing, pages1–16, 2011.

[10] J.-C. Latombe, R.H. Wilson, and F. Cazals.Assembly sequencing with toleranced parts.CAD Computer Aided Design, 29(2):159–174,1997.

[11] R.M. Marian, L.H.S. Luong, and K. Abhary.Assembly sequence planning and optimisa-tion using genetic algorithms part i. automa-tic generation of feasible assembly sequences.Applied Soft Computing Journal, 2(3):223–253, 2003.

[12] R.M. Marian, L.H.S. Luong, and K. Abhary.A genetic algorithm for the optimisation ofassembly sequences. Computers and Indus-trial Engineering, 50(4):503–527, 2006.

[13] C. Sinanoglu and H.R. Borklu. An assem-bly sequence-planning system for mechanicalparts using neural network. Assembly Auto-mation, 25(1):38–52, 2005.

[14] C. Sinanoglu and Borklu H.R. An approachto determine geometric feasibility to assem-bly states by intersection matrices in assem-bly sequence planning. Journal of IntelligentManufacturing, 15(4):543–559, 2004.

[15] H.-E. Tseng. An improved ant colony sys-tem for assembly sequence planning based onconnector concept. Lecture Notes in Electri-cal Engineering, 97 LNEE(VOL. 1):881–888,2011.

[16] J.F. Wang, J.H. Liu, and Y.F. Zhong. Anovel ant colony algorithm for assembly se-quence planning. International Journal ofAdvanced Manufacturing Technology, 25(11-12):1137–1143, 2005.

[17] R.H. Wilson and J.-C. Latombe. Geometricreasoning about mechanical assembly. Artifi-cial Intelligence, 71(2):371–396, 1994.

[18] Z. Yin, H. Ding, H. Li, and Y. Xiong. Aconnector-based hierarchical approach to as-sembly sequence planning for mechanical as-semblies. CAD Computer Aided Design,35(1):37–56, 2003.

XXXIV Jornadas de Automática. Terrassa, 4 al 6 de Septiembre de 2013

710