Sistema L

El sistema L original de Lindenmayer para modelar el crecimiento de las algas.

variables  : AB

constantes  : ninguna

axioma  : A

Reglas  : (A → AB), (B → A)

lo cual produce:

n = 0  : A

n = 1  : AB

n = 2  : ABA

n = 3  : ABAAB

n = 4  : ABAABABA

n = 5  : ABAABABAABAAB

n = 6  : ABAABABAABAABAABAABABA

n = 7  : ABABABAABAABABAABABAABAABABAABAAB

n=0: Un comienzo (axioma/iniciador) / \ n=1: AB, la única A inicial generada en AB por la regla (A → AB), la regla (B → A) no se pudo aplicar. /| \ n=2: ABA, antigua cadena AB con todas las reglas aplicadas, A se convirtió de nuevo en AB, la antigua B se convirtió en A / | | | \ n=3: ABAAB observe que todas las A producen una copia de sí mismas en primer lugar, luego una B, que a su vez... / | | | \ | \ \ n=4: ABAABABA ... en una A una generación después, comenzando a generar/repetir/recurrir entonces

• variables  : 0, 1
• constantes : "[", "]"
• axioma  : 0
• reglas  : (1 → 11), (0 → 1[0]0)

La forma se construye alimentando recursivamente el axioma a través de las reglas de producción. Cada carácter de la cadena de entrada se compara con la lista de reglas para determinar con qué carácter o cadena reemplazarlo en la cadena de salida. En este ejemplo, un '1' en la cadena de entrada se convierte en '11' en la cadena de salida, mientras que ' [ ' permanece igual. Aplicando esto al axioma de '0', se obtiene:

Se puede observar que esta cadena crece rápidamente en tamaño y complejidad. Esta cadena se puede representar como una imagen utilizando gráficos de tortuga , donde a cada símbolo se le asigna una operación gráfica que la tortuga debe realizar. Por ejemplo, en el ejemplo anterior, a la tortuga se le pueden dar las siguientes instrucciones:

• 0: dibuja un segmento de línea que termine en una hoja.
• 1: dibuja un segmento de línea
• [ : posición y ángulo de empuje, girar a la izquierda 45 grados
• ] : posición y ángulo de salida, girar a la derecha 45 grados

Las operaciones push y pop se refieren a una pila LIFO (una gramática más técnica tendría símbolos separados para "empujar posición" y "girar a la izquierda"). Cuando la interpretación de la tortuga encuentra un ' [ ', la posición y el ángulo actuales se guardan y se restauran cuando la interpretación encuentra un ' ] '. Si se han "empujado" varios valores, una operación "pop" restaura los valores guardados más recientemente. Aplicando las reglas gráficas enumeradas anteriormente a la recursión anterior, se obtiene:

variables  : AB

constantes  : ninguna

inicio  : Una {cadena de caracteres inicial}

Reglas  : (A → ABA), (B → BBB)

Sea A "avanzar" y B "mover hacia adelante".

Esto produce el famoso conjunto fractal de Cantor sobre una línea recta real R.

Una variante de la curva de Koch que utiliza únicamente ángulos rectos.

variables  : F

constantes  : + −

inicio  : F

Reglas  : (F → F+F − F − F+F)

Aquí, F significa "avanzar", + significa "girar 90° a la izquierda" y − significa "girar 90° a la derecha" (ver gráficos de tortuga ).

n = 0:

F

n = 1:

F+F − F − F+F

n = 2:

F+F − F − F+F+F + F − F − F+F − F + F − F − F+F − F − F+F+F+F − F − F+F

n = 3:

F+F − F − F+F+F + F − F − F+F − F + F − F − F+F − F − F+F+F+F − F − F+F+

F+F − F − F+F+F+ F − F − F+F − F +F − F − F+F − F+ F − F − F+F+F+F − F − F+F −

F+F − F − F+F+F+ F − F − F+F − F +F − F − F+F − F+ F − F − F+F+F+F − F − F+F −

F+F − F − F+F+F + F − F − F+F − F + F − F − F+F − F − F+F+F+F − F − F+F+

F+F − F − F+F+F + F − F − F+F − F + F − F − F+F − F − F+F+F+F − F − F+F

El triángulo de Sierpinski dibujado utilizando un sistema L.

variables  : FG

constantes  : + −

inicio  : F − G − G

Reglas  : (F → F − G+F+G − F), (G → GG)

ángulo  : 120°

Aquí, F y G significan "avanzar", + significa "girar a la izquierda en ángulo" y − significa "girar a la derecha en ángulo".

• 
  n = 2
• 
  n = 4
• 
  n = 6

También es posible aproximar el triángulo de Sierpinski utilizando un sistema L de curvas de punta de flecha de Sierpiński .

variables  : AB

constantes  : + −

inicio  : A

Reglas  : (A → B − A − B), (B → A+B+A)

ángulo  : 60°

Aquí, A y B significan "avanzar", + significa "girar a la izquierda en ángulo" y − significa "girar a la derecha en ángulo" (ver gráficos de tortuga ).

La curva del dragón dibujada utilizando un sistema L.

variables  : FG

constantes  : + −

inicio  : F

Reglas  : (F → F+G), (G → FG)

ángulo  : 90°

Aquí, F y G significan "avanzar", + significa "girar a la izquierda en ángulo" y − significa "girar a la derecha en ángulo".

variables  : XF

constantes  : + − [ ]

inicio  : -X

reglas  : (X → F+[[X]-X]-F[-FX]+X), (F → FF)

ángulo  : 25°

Primero, se debe inicializar una pila vacía. Esto sigue el método LIFO (último en entrar, primero en salir) para agregar y eliminar elementos. Aquí, F significa "dibujar hacia adelante", − significa "girar a la derecha 25°" y + significa "girar a la izquierda 25°". X no corresponde a ninguna acción de dibujo y se usa para controlar la evolución de la curva. El corchete "[" corresponde a guardar los valores actuales de posición y ángulo, por lo que la posición y el ángulo se colocan en la parte superior de la pila. Cuando se encuentra el token "]", se extrae un elemento de la pila y se restablecen la posición y el ángulo. Cada "[" precede a cada token "]".

El modelo gramatical que hemos analizado hasta ahora ha sido determinista; es decir, dado cualquier símbolo del alfabeto de la gramática, existe exactamente una regla de producción, que siempre se elige y siempre realiza la misma conversión. Una alternativa es especificar más de una regla de producción para un símbolo, asignando a cada una una probabilidad de ocurrencia. Por ejemplo, en la gramática del Ejemplo 2, podríamos cambiar la regla para reescribir "0" de:

0 → 1[0]0

a una regla probabilística:

0 (0,5) → 1[0]0

0 (0,5) → 0

En este proceso, si se encuentra un "0" durante la reescritura de la cadena, existe un 50 % de probabilidad de que se comporte como se describió anteriormente y un 50 % de probabilidad de que no cambie durante la producción. Cuando se utiliza una gramática estocástica en un contexto evolutivo , es recomendable incorporar una semilla aleatoria al genotipo para que las propiedades estocásticas de la imagen permanezcan constantes entre generaciones.

Una regla de producción sensible al contexto no solo considera el símbolo que está modificando, sino también los símbolos de la cadena que aparecen antes y después de él. Por ejemplo, la regla de producción:

b < a > c → aa

transforma "a" en "aa", pero solo si la "a" aparece entre una "b" y una "c" en la cadena de entrada:

…de vuelta…

Al igual que con las producciones estocásticas, existen múltiples producciones para manejar símbolos en diferentes contextos. Si no se encuentra ninguna regla de producción para un contexto dado, se asume la producción de identidad y el símbolo no cambia al transformarse. Si existen producciones sensibles al contexto y libres de contexto dentro de la misma gramática, se asume que la producción sensible al contexto tiene prioridad cuando sea aplicable.

En una gramática paramétrica, cada símbolo del alfabeto tiene asociada una lista de parámetros. Un símbolo junto con su lista de parámetros se denomina módulo, y una cadena en una gramática paramétrica es una serie de módulos. Un ejemplo de cadena podría ser:

a(0,1)[b(0,0)]a(1,2)

Los parámetros pueden ser utilizados por las funciones de dibujo y también por las reglas de producción. Las reglas de producción pueden utilizar los parámetros de dos maneras: primero, en una instrucción condicional que determina si se aplicará la regla, y segundo, la regla de producción puede modificar los parámetros reales. Por ejemplo, observe:

a(x,y)  : x == 0 → a(1, y+1)b(2,3)

El módulo a(x,y) se transforma según esta regla de producción si se cumple la condición x=0. Por ejemplo, a(0,2) se transformaría, mientras que a(1,2) no.

En la parte de transformación de la regla de producción, tanto los parámetros como los módulos completos pueden verse afectados. En el ejemplo anterior, el módulo b(x,y) se agrega a la cadena, con parámetros iniciales (2,3). Además, los parámetros del módulo ya existente se transforman. Bajo la regla de producción anterior,

a(0,2)

Se convierte

a(1,3)b(2,3)

ya que el parámetro "x" de a(x,y) se transforma explícitamente en un "1" y el parámetro "y" de a se incrementa en uno.

Las gramáticas paramétricas permiten que la longitud de las líneas y los ángulos de ramificación se determinen mediante la propia gramática, en lugar de mediante los métodos de interpretación de Turtle. Además, si se especifica la edad como parámetro para un módulo, las reglas pueden cambiar según la edad de un segmento de la planta, lo que permite crear animaciones de todo el ciclo de vida del árbol.

El modelo bidireccional separa explícitamente el sistema de reescritura simbólica de la asignación de formas. Por ejemplo, el proceso de reescritura de cadenas en el Ejemplo 2 (Árbol fractal) es independiente de cómo se asignan las operaciones gráficas a los símbolos. En otras palabras, un número infinito de métodos de dibujo son aplicables a un sistema de reescritura dado.

El modelo bidireccional consta de 1) un proceso directo que construye el árbol de derivación con reglas de producción, y 2) un proceso inverso que materializa el árbol con formas de manera gradual (desde las hojas hasta la raíz). Cada paso de derivación inversa implica un razonamiento geométrico-topológico esencial. Con este marco bidireccional, las restricciones y los objetivos de diseño se codifican en la traducción de la gramática a la forma. En aplicaciones de diseño arquitectónico, la gramática bidireccional presenta una conectividad interna consistente y una rica jerarquía espacial. ^{[ 4 ]}

Históricamente, la construcción de sistemas L dependía en gran medida del trabajo manual de expertos, ^{[ 5 ] [ 6 ] [ 7 ]} lo que requería mediciones detalladas, conocimiento del dominio y una inversión de tiempo considerable. El proceso a menudo implicaba analizar estructuras biológicas y codificar sus reglas de desarrollo en sistemas L, símbolo por símbolo. Este método laborioso hacía que la creación de modelos precisos para procesos complejos fuera tediosa y propensa a errores.

Un ejemplo notable es el trabajo de Nishida ^{[ 7 ]} sobre cipreses japoneses, donde segmentó manualmente ramas a partir de una serie de imágenes e identificó 42 mecanismos de crecimiento distintos para construir un sistema L estocástico. A pesar del considerable esfuerzo invertido, el sistema resultante solo proporcionó una aproximación del crecimiento del árbol, lo que ilustra las dificultades de codificar manualmente procesos biológicos tan detallados. Esta ardua tarea fue descrita como «tediosa e intrincada», lo que subraya las limitaciones de los métodos manuales.

Los desafíos de la construcción manual de sistemas L también están bien documentados en *The Algorithmic Beauty of Plants ^{* [ 6 ]} , de Przemyslaw Prusinkiewicz y Aristid Lindenmayer. El libro demuestra cómo los sistemas L pueden modelar elegantemente el crecimiento de las plantas y los patrones fractales, pero los ejemplos a menudo requerían la intervención de expertos para definir las reglas necesarias.

La construcción manual se vio aún más limitada por la necesidad de conocimientos especializados en el dominio, como se observa en otras aplicaciones de los sistemas L más allá de la biología, como el diseño arquitectónico y la modelización urbana. ^{[ 8 ]} En estos campos, la creación de un sistema L preciso requería no solo la comprensión del formalismo del sistema L, sino también un conocimiento extenso del dominio que se estaba modelando.

La idea de automatizar la inferencia de sistemas L surgió para abordar las ineficiencias de los métodos manuales, que a menudo requerían amplios conocimientos especializados, mediciones y procesos de ensayo y error. Esta automatización tenía como objetivo permitir la inferencia de sistemas L directamente a partir de datos de observación, eliminando la necesidad de codificar manualmente las reglas.

Los algoritmos iniciales se centraron principalmente en sistemas L deterministas libres de contexto (sistemas D0L), que se encuentran entre los tipos más simples de sistemas L. Estos primeros esfuerzos demostraron la viabilidad de la inferencia automática, pero su alcance era muy limitado, ya que generalmente solo manejaban sistemas con alfabetos pequeños y reglas de reescritura simples. ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} Por ejemplo, el trabajo de Nakano ^{[ 10 ]} destacó los desafíos de inferir sistemas L con alfabetos más grandes y estructuras más complejas, describiendo la tarea como "inmensamente complicada".

Las primeras herramientas para la inferencia de sistemas L a menudo se diseñaban para asistir a los expertos en lugar de reemplazarlos. Por ejemplo, los sistemas que presentaban al usuario una población de posibles sistemas L, permitiéndole seleccionar opciones estéticamente agradables o plausibles, reducían parte de la carga de trabajo manual. ^{[ 12 ] [ 13 ]} Sin embargo, estas herramientas dependían en gran medida del juicio humano y no automatizaban completamente el proceso de inferencia.

Algunos algoritmos iniciales estaban estrechamente integrados en dominios de investigación específicos, principalmente en el modelado de plantas. ^{[ 13 ]} Estos enfoques utilizaban el conocimiento del dominio para restringir el espacio de búsqueda y obtener mejores resultados. Sin embargo, su dependencia de reglas predefinidas específicas del dominio limitaba su generalización y aplicabilidad a otras áreas.

Los intentos de crear algoritmos generalizados para la inferencia de sistemas L comenzaron con sistemas deterministas libres de contexto. Los investigadores buscaban inferir sistemas L a partir únicamente de datos, como secuencias de cadenas o datos temporales de imágenes, sin depender del conocimiento específico del dominio. Estos algoritmos encontraron desafíos significativos, ^{[ 14 ] [ 15 ]} entre los que se incluyen:

• El crecimiento exponencial del espacio de búsqueda aumenta con el tamaño del alfabeto y la complejidad de las reglas.

• El manejo de datos imperfectos o ruidosos introdujo errores en los sistemas inferidos.

• Se produjeron limitaciones en la eficiencia computacional, ya que los métodos de búsqueda exhaustiva se volvieron intratables salvo en los casos más sencillos.

La tesis doctoral de Bernard ^{[ 16 ]} , dirigida por el Dr. Ian McQuillan en la Universidad de Saskatchewan, representa un avance significativo en la inferencia de sistemas L, al introducir el conjunto de herramientas de inferencia de modelos de plantas (PMIT). A pesar de su nombre, esta herramienta es independiente del problema y se denomina así debido a la fuente de financiación original del proyecto P2IRC. Estas herramientas abordan los desafíos de la inferencia de sistemas L deterministas, estocásticos y paramétricos:

Sistemas L deterministas libres de contexto (D0L):

La herramienta PMIT-D0L mejoró el estado del arte al permitir la inferencia de sistemas L con hasta 31 símbolos, en comparación con los algoritmos anteriores que solo admitían dos. Esto se logró mediante técnicas de codificación novedosas y métodos de reducción del espacio de búsqueda.

Sistemas L deterministas sensibles al contexto (D(j,k)L):

La herramienta PMIT-DCSL mejoró aún más la inferencia de sistemas L deterministas al demostrar que las técnicas funcionaban en el caso sensible al contexto con pocas modificaciones. Esta herramienta también presentó mejoras adicionales que permitieron la inferencia de sistemas L deterministas con hasta cientos de símbolos. Además, este trabajo y el artículo teórico de McQuillan ^{[ 17 ]} demuestran la complejidad de la inferencia de sistemas L sensibles al contexto. En un trabajo inédito, Bernard afirma demostrar que la sensibilidad al contexto nunca cambia la naturaleza fundamental del problema de inferencia, independientemente de la regla de selección. Es decir, inferir sistemas L estocásticos sensibles al contexto es posible si es posible inferir sistemas L libres de contexto.

Sistemas L estocásticos (S0L):

Para sistemas L estocásticos, se desarrolló PMIT-S0L, que utiliza un enfoque híbrido de algoritmos voraces y genéticos para inferir sistemas a partir de múltiples secuencias de cadenas. La herramienta demostró la capacidad de inferir reglas de reescritura y probabilidades con alta precisión, un logro sin precedentes en este campo.

Sistemas L paramétricos temporales:

McQuillan fue el primero en darse cuenta de que los sistemas L paramétricos podían considerarse sistemas L estocásticos; sin embargo, esto no resolvía el problema de inferir las reglas de selección paramétricas. Mediante la programación genética cartesiana, se podían inferir sistemas L paramétricos junto con las reglas de selección paramétricas, siempre que el conjunto de parámetros incluyera el tiempo (para proporcionar una secuencia a los parámetros, aunque el tiempo es un parámetro razonable para cualquier proceso real). Esta herramienta, PMIT-PARAM, infirió con éxito sistemas complejos con hasta 27 reglas de reescritura, estableciendo un nuevo referente en la inferencia de sistemas L.