Heuristic fitness classification en problemas de ensamblaje

    Los problemas de ensamblaje de partes, son un desafío en el campo de la robótica actual. Ensamblar un objeto desconocido, requiere sortear todo tipo de problemas relacionados con la visión computarizada, con el mero objetivo de poder llevar el problema físico a un modelo computacional.

    Aún siguiendo la hipótesis de que se ha solucionado el problema anterior, el original sigue lejos de estar resuelto. Modelar lo desconocido requiere el uso de modelos abstractos altamente flexibles, como el modelo de grafos usado en el proyecto SIR [1], donde se utiliza la Teoría de grafos para modelar un rompecabezas desconocido en un modelo computacional.

    El modelo establece como el cromosoma, a la solución posible al artefacto a ensamblar. Siendo así, los genes representan las adyacencias entre un subcomponente a y un subcomponente b del artefacto. Los alelos de dichos genes serán las caras (bordes) que serán ensamblados entre ambos subcomponentes (un componente puede tener mas de una cara o borde).

    En cuanto al modelo de grafos , un subcomponente del artefacto es representado por un vértice. La conexión o ensamblaje entre una cara de un subcomponente y la de otro, serán las aristas entre los vértices.

    Las combinaciones posibles para un ensamblado a fuerza bruta crecen de forma exponencial-factorial n^y!. La solución de un problema de estas características, es la optimización de las distancias entre los bordes de los componentes, es decir, que al conectar un lado de un componente con el de otro, la diferencia entre estos debe minimizarse de forma tal que el encaje sea casi perfecto. Por ello, el problema de ensamblar componentes de un artefacto, es un problema de optimización de distancias, NP-Completo [1]. El trabajo citado previamente propone el uso de algoritmos genéticos con heurísticas tales que contemplen la aleatoriedad controlada necesaria para armar un artefacto de forma coherente con sus características originarias (respetar la forma real del artefacto).

    Los auteres han dado en llamar Heuristic Fitness Classification al algoritmo genético capaz de considerar estas no-aleatoriedades inherentes al problema de ensamblado de piezas desconocidas.

    Se asume con este modelo que al ensamblar una pieza,  los genes que tienen una distancia borde a borde mínima, tienen mayor probabilidad de estar presentes en una solución óptima.. Para evitar que dichos genes sean separados por las operaciones, el flujo de trabajo del GA incluye una forma de etiquetar aquellos genes que superen un porcentaje de similitud entre bordes definida. SIR contempla dos límites que pueden ajustarse a distintos valores de similitud entre bordes. Esto crea dos clases nuevas de genes: genes candidato y genes sticky (pegajosos). Candidato refiere a aquellos genes que tienen un porcentaje de similitud aceptable (ej. 70%) como parte de un cromosoma apto pero no considerado “óptimo”. Sticky se refiere a aquellos genes que tienen una distancia “óptima” (>=90%).

    Los genes Sticky o Candidatos tienen menor probabilidad de ser afectados por las operaciones genéticas. Esta heurística permite que las operaciones no desmantelen genes aptos durante la mutación o la cruza. El proceso de etiquetado es llevado a cabo por la función de ajuste. Esta capacidad puede ser activada o no durante la ejecución del GA dependiendo de la situación de convergencia del algoritmo. En el siguiente gráfico se muestra un flujo de ejecución del algoritmo propuesto.