El rincón de la simulación (métodos numéricos)

B

#30 tampoco es que estuviese totalmente fuera de contexto xD, a lo mejor me pongo en contacto contigo más adelante.

1 respuesta
Hipnos

Pensando sobre lo del olfato...

Se me ocurre que puedes dividir sectorialmente el olfato de la hormiga, y sumar las distintas intensidades que lleguen de esa dirección. En las intensidades a sumar:

  1. Por cercanía de alimento. Se puede usar un modelo parecido al gravitacional (suponiendo que la sensibilidad de la hormiga sea infinita, pero inversamente proporcional al cuadrado de la distancia).
  2. Por rastro dejado por otra hormiga (obteniendo el punto más cercano de entre las distintas trazas, y ponderado por la intensida de dicho rastro(a mayor intensidad de rastro, la hormiga amiga ha detectado más cantidad de comida)).

Así, la hormiga tendría una dirección aproximada, acotada por uno de los arcos de entre los distintos sectores. El vector dirección se podría tomar como un ángulo aleatorio dentro de ese arco.

2 respuestas
B

#32 en principio una hormiga no tiene sensibilidad infinita ni soltará más o menos rastro según la comida que detecte, al menos hasta donde yo sé, lo que hace que las hormigas acaben encontrando el camino más rápido a la comida es que cuanto menos tengan que andar y desandar menos se disipa el rastro (porque vuelven a pasar por allí), y más hormigas van yendo y se va "llenando" el rastro.

También pensé en tomar directamente el punto más cercano (ponderado por intensidad, pero no significa que haya detectado más cantidad de comida sino que ha pasado por ahí hace menos tiempo), pero no sé por qué me moló más la idea de que tuviera en cuenta todos los rastros a la vez (en plan no es capaz de distinguir la dirección porque todas las hormigas huelen igual, no sé si me explico). Pero creo que ambas ideas tienen sus puntos a favor y en contra, lo de los sectores por un lado te impide que la hormiga avance en dirección y cuando tiene rastros en x y en -x (mal dicho, pero ya me entiendes xD), lo cual es bueno, por el otro tomar solo el máximo dentro del sector me parece "poco realista", un término medio por sectores + suma de vectores en cada sector creo que puede ser lo más chulo. ¿Qué opinas? Pero yo no usaría lo de la cercanía del alimento (bueno, si está a un radio de olfato entonces sí, pero no en plan gravitacional, porque entonces incluso sin rastros la hormiga tendiría a ir hacia allí y no es realista).

Si un segmento está en dos sectores, ¿qué propondrías?

Igualmente haré también la de las celdas que me parece que será mucho más rápida (no habrá que guardar ~ 10 * hormigas segmentos en todo momento ).

#30 claramente en el departamento de simulación de una empresa no se están por chorradas como esta y si algo ya está hecho se usa y no se reinventa la rueda xD, pero para practicar el pensamiento matemático, la modelización y todo esto creo que puede estar chulo, si te animas a participar ya sabes!

2 respuestas
Hipnos

#33

Realmente, aquí hay muchas opciones:

  • El olfato de algunos insectos tiene alcance de kilómetros, no me extrañaría nada que la limitación principal de las hormigas sea una mezcla entre demasiados rastros y distancia a recorrer.

  • Puedes hacer que haya hormigas "exploradoras", con mayor sensibilidad olfativa, mayor velocidad y la posibilidad de dejar rastros ascendentes según la cercanía al alimento. Algunas especies funcionan así.

  • No pensaba tomar el máximo de cada sector, sino una suma sectorial. La hormiga avanzará en una dirección aleatoria dentro del arco del sector con mayor suma.

  • Mi primer planteamiento era de fuentes de olor puntuales, no por segmentos. Lo que sí había pensado eran las trazas de otras hormigas: basta con coger el punto más cercano a la hormiga, o bien discretizar la traza y hacer que cada uno de los puntos emita olor (luego discernir el más intenso según distancia e intensidad en el punto origen).

1 respuesta
B

#34

  • De momento no incluiré igualmente un alcance tan grande, para que no salgan ya directamente apuntando a la fuente de comida más cercana (las primeras que salgan solo olerían comida ya que no habría rastro, así que irían directamente por el sector donde está la comida). IRL este problema no estaría porque habrá muchos más olores, pero aquí por infinitesimal que sea la mejora ya apuntaría hacia allí y no se vería (creo) tanto el efecto de las demás hormigas.

  • Lo de las hormigas exploradoras me gusta, pero iré poco a poco, lo dejaré para la versión 1.1 xD.

  • Cuando dices suma sectorial, ¿qué crees que sería mejor? Suma de vectores y la intensidad del vector suma, o directamente sumar intensidades? Por la desigualdad triangular evidentemente ||v1 + ... + vn|| <= ||v1|| + ... + ||vn||, pero las relaciones entre sectores pueden ser distintas. Además el vector suma puede también condicionar la distribución de probabilidad de la dirección a escoger. Dudo entre cuál de las dos sería más realista.

  • Personalmente me gustaría que todos tomáramos un formato igual para hacer lo mismo, como dije en #1, para de esta manera facilitar el I/O y la representación posterior. Escogimos hacerlo por segmentos (y yo lo haré por celdas también porque es fácil y quiero ver cómo queda), pero fue obviamente arbitrario. Tu propuesta tampoco cambiaría mucho el I/O (los rastros a la hora de "pintar" es lo único que se modificaría) así que si quieres puedes probarlo de esa manera.

Bueno y por supuesto, si hay algo que yo lo hago de una manera y cualquiera de vosotros pensáis en otra y queréis implementarla y comparar soluciones, creo que podría ser guay.

Siempre hay muchas opciones como bien dice Hipnos, pero tampoco se puede sobredimensionar y querer matar moscas (u hormigas, jeje) a cañonazos, si algo cuesta mucho más de añadir que las ventajas que puede suponer pues no vale la pena (IMHO), aunque esto ya es subjetivo y depende del tiempo y las ganas que tenga cada uno, claro. No creo que haya ninguna opción incorrecta!

Gracias por colaborar por cierto, sobretodo esvarianzza e Hipnos, y los otros que nos leéis a ver si os animáis un poco xD

1 respuesta
Hipnos

#35

Sobre el tema de las intensidades:

Quizá la principal pregunta es si quieres que haya intensidades negativas (i.e. rastros de peligro, o rastros que indican que un rastro anterior ya no conduce a comida). Si esto es así, pues sumas ||v1 + v2 + ... +vn||. Si no, pues realmente creo que el resultado sería similar.

Para mi, sin duda, lo más complejo sería modelar el nido en 3D. Habría que dimensionar muy bien el esfuerzo por hormiga, y establecer los rastros internos de olores del propio nido (ya que las hormigas, ciegas, deben saber dónde colocar la comida, los nuevos túneles y salidas, etc.). Por otro lado, no tengo ni idea del criterio excavador que tienen las hormigas, pero imagino que la posición de la cámara de las reinas o de los almacenes estarán en las partes inferiores.

El reto sería colocar una reina fecundada en un entorno, y a partir de ahí simular el crecimiento progresivo de la colonia, hasta su destrucción (ausencia de comida, catástrofes, ataques, etc. modelados por eventos aleatorios).

1 respuesta
Drhaegar

Tener en cuenta que la mayoría de hormigas cuando vuelve al hormiguero a avisar de que ha avistado comida lo hace en línea recta dejando un rastro que luego siguen (en mi campo he llegado a ver líneas de más de 7 metros completamente rectas).

#32 Optimizar eso en una sandbox con muchas hormigas y comida tiene que ser muy complicado por la cantidad de cálculos que tendría que hacer el procesador en cada golpe de reloj, pues habría que calcular con que intensidad siente cada hormiga para cada trozo de comida.

Lo mejor sería establecer un sistema de colisión entre olfato y olor, y si está dentro del rango calcular con que intensidad percibe el olor para hacer la suma de vectores.

2 respuestas
B

#36 jajaja pues y tan reto, te animo a que lo hagas si te apetece, yo como mero mortal de momento sólo voy a hacer que busquen comida, que en un par de semanas no alcanzo a más xD. Lo del hormiguero y la vida y muerte de nuestras pequeñas amigas lo dejaré para la versión 2.0 xDD.

Ahora en serio, prefiero ir haciendo cosillas pequeñas y limitadas (y un poco pedagógicas para el que, por ejemplo, no sepa generar un número aleatorio siguiendo cierta distribución) y ya ir aumentando el nivel, a empezar la casa por el tejado y meterme en camisa de once varas (y espantar al neófito). Lo que tú comentas podría ser interesante más adelante y se podrían juntar las dos partes.

#37 interesante, sabes si vuelven directamente (saben dónde está el hormiguero) o si simplemente encuentran el camino directo por pura acumulación? ¿Cómo harías el sistema de colisión? Es una de las cosas que más me traen de cabeza, porque no se me ocurre otra manera de saber qué segmentos están a menos distancia que el radio de olfato que no sea probándolos todos...

2 respuestas
Hipnos

#37

Volvemos a las preguntas: ¿Queremos un modelo realista, o un modelo computacionalmente eficiente? xD

El camino de la eficiencia es la agrupación por zonas, ignorando los cálculos de las fuentes de olor más alejadas.

Sin embargo, si tomamos que el olfato de todas las hormiga es igual, basta con generar un mapa vectorial a cada iteración para cualquier número de hormigas, donde en cada iteración cada punto tenga una tendencia a una dirección concreta. Las soluciones de campos son optimizables con cálculos matriciales, y se pueden procesar muy rápidamente mediante GPUs.

#38 Las hormigas cuentan los pasos desde su hormiguero. Hicieron experimentos donde les recortaron y alargaron sus patas lejos de su nido, y no sabían volver (unas se pasaban y otras buscaban antes de la cuenta). Son unos bichos muy curiosos.

1 2 respuestas
Drhaegar

#38 Pues ni idea de como llegan al hormiguero, puede ser que sea por sentido de la orientación o por el olor... pero ni idea.

Lo de la colisión depende de como quieras hacer el mapa, hay muchas formas de crear un sistema de colisiones y habría que ver cual es que más se ajusta.

#39 Pues no había caído en lo del mapa vectorial, posiblemente sea la mejor solución porque una vez creado solo hay que calcular la posición de cada hormiga en el mapa vectorial hasta que se actualice la cantidad de comida en la sandbox.

1 respuesta
B

#39 y desandan sus pasos? Interesante!

Lo que dices del mapa vectorial es también muy chulo, pero entonces si lo divides sectorialmente (y los sectores dependen del ángulo relativo de la hormiga), ¿se puede hacer aún? Me interesa mucho porque además se puede juntar con distintas topologías e incluso distintas geometrías (si las geodésicas no son las líneas rectas por ejemplo) :o , alguna referencia al respecto?

1 respuesta
Hipnos

#41 Hombre, la solución sectorial era un modelo simplificado en el caso de que quisieras modelar distintos tipos de hormigas (unas con más olfato que otras). Para realizar el campo vectorial, puedes hacerlo todo lo preciso que quieras, puesto que sólo harás el cálculo una vez para todas las hormigas.

for(campo iterado en i, j) { //Iteras para todo punto del campo
posibles_direcciones=obtener_direcciones(i,j) //Calculas todas las posibles direcciones y guardas su intesidad
campo[i,j]= direccion_del_modulo_maximo(posibles_direcciones) //Te quedas con la de módulo máximo
}

La pega es que, desde el mismo punto, TODAS las hormigas seguirán la misma ruta. Por eso veo un poco aburrida esta solución... Esto se puede lidiar de varias formas:

  1. Guardas también las direcciones que no sean la de mayor intensidad, y haces una distribución gaussiana de las hormigas que se dirigen a cada una.
  2. Modificas aleatoriamente la dirección de la hormiga en un valor pequeño (asumes error de percepción de la hormiga).
  3. Simulas más cosas, como una intensidad de olor variable en T (por motivos de dirección del viento, etc.)

Modelar se me da bastante bien, pero es que cualquier problema tiene miles de soluciones...

Esto me recuerda cierta anécdota:
1 1 respuesta
B

#42 hombre, me refería a lo de las matrices, no al for xD pero gracias de todos modos. Igualmente en cada paso con los rastros cambiaría el campo, y además la componente aleatoria tiene que estar, así como que cada hormiga tienda más a avanzar que a dar media vuelta. Pero ver los rastros como atractores y repulsores (de momento solo atractores) de un campo vectorial me parece interesante. Sí, cualquier problema tiene miles de soluciones xD pero no veo qué tiene que ver con que se nos de bien o mal. Es más alguna vez que estaba atascado con algún problema me ha ido bien comentarlo con gente que en principio no tiene ni idea del problema ni de matemáticas ni nada xD, salen ideas interesantes de todos lados. En fin, de momento voy a intentar lo que hemos comentado (alguna de las versiones) y lo dicho, si alguien se anima pues adelante! :D

1 1 respuesta
wineMan

Joer, como no entro no veo estas cosas. Hilo wapens Duronman style. Voy a ver si lo leo y me ilumino algo.
Qué grande eres, jodío.

1
ninjachu

#43 Mi conocimiento matemático en este aspecto es muy limitado, pero podriaís intentar dividir la complejidad del problema en uno más sencillo y luego aplicar un método de concurrencia aleatorio.

Ejemplo: Supongamos la hormiga como la mínima unidad, la cual busca comida en función de rastros aleatorios existentes (o ninguno, más difícil) y deja un rastro en su camino, si encuentra la comida vuelve al hormiguero por el mismo camino que tomado para ir (intentando acortarlo), por tanto vuelve a remarcar el camino duplicando el "peso del mismo".

Luego vais complicando el sistema añadiendo mas hormigas (unidades) con la misma funcionalidad de manera aleatoria.

Espero serviros de ayuda, ya que lo poco que puedo aportar son ligeros conocimientos de AI.

1 respuesta
grivcon

Me llama bastante la atención todas estas cosas, donde puedo encontrar algo sencillo para enterarme del asunto y empezar?

1 respuesta
Hipnos

Yo es que todavía no sé qué discutimos, porque está:

  • El modelado.
  • La implementación.
  • Las aplicaciones de las matemáticas en ambas.
  • Los procedimientos software para simular.
  • La inteligencia artificial detrás de todo.
  • La posible implementación como un juego.

Si por favor se me aclara, podré concretar más mis respuestas xD

1 respuesta
B

#45 de momento será por turnos, sí que es cierto que con programación concurrente puede ser muy guay también pero si ya nos (me) está costando así no quiero pensar de la otra manera. Además en MATLAB no sé cómo puedo hacerlo xD. De todas maneras lo que comentas es más o menos también mi idea! No hace falta saber muchas mates al menos para este, así que si te interesa anímate :)

#46 qué nivel tienes? Y qué tema te interesa más?

#47 ahora mismo estaríamos en fase de modelado/prototipado, pero bueno es un proyecto demasiado pequeño como para decir que tiene fases xD, la parte de matemáticas la iré metiendo conforme vayan saliendo dudas, no le veo sentido a explicar la zero-stability de un Runge-Kutta ahora por ejemplo y además ahuyentaría a la gente. Y de momento yo pasaré de la implementación como juego, claro que a quien le interese puede hacerlo! Me parece que está fuera de mis objetivos actuales y sería liarme en cosas que por ahora no me interesan tanto. (Aunque hacer juegos didácticos es un tema que me molaría)

¿Sabes qué molaría? No sé hasta qué punto estás metido en ello, pero si dominas del tema, podrías explicar un poco las fases de un proyecto de simulación, o cómo se divide normalmente, yo hasta ahora todos los proyectos en que he estado han sido bastante chapuzas xD.

1 respuesta
grivcon

#48 de simulación 0,000000. El tema en concreto ninguno, todo lo que sea sistemas de autómatas (hormigas, perros, personas...) diseñando e implementando una tarea me parece nuevo. Resumiendo, quiero adentrarme en IA, simulación de sistemas, autómatas pero no tengo ni pajolera idea un buen libro/pagina desde 0.

Jastro

que se hunde el barco! que pacha aqui :O

#51 te queremos igual :3

B

Disculpad las demoras, por motivos familiares no he podido hacer nada esta semana... Me pondré a ello ASAP.

1 1 respuesta
B

Bueno pues lo dicho, retomo la senda de la simulación xD, disculpad de nuevo la demora pero son cosas de la vida.

Creo que tiraré por lo de los sectores que comento Hipnos, me gustó la idea, serían unos 4 sectores: Frontal, laterales y trasero. Dispuestos en las diagonales de un hexágono regular. El tema ahora sería no tener que comprobar la distancia a todos los segmentos, ni si están en el sector que estoy mirando. Alguna sugerencia? #40 Tienes alguna referencia sobre colisiones?

En MATLAB usaré cells (parecido a listas), unas para hormigas y unas para segmentos. Una vez sepa una manera rápida de saber qué segmentos están dentro de un radio X, mirar las distancias a cada uno es pan comido.

El resultado final será una lista de puntos por los que pasará la hormiga, y eso me gustaría poder representarlo como una animación.

Hipnos

Si pasas el problema a 2D, la resolución de lo del radio se vuelve trivial: basta con colocar una máscara circular sobre la matriz de partículas olorosas.

Lo detallo:

Imaginemos el terreno como una matriz de 1000x1000.

Suponemos que la hormiga es capaz de percibir cualquier cosa en un radio de 50 celdas circular.
Creamos dicha malla circular, que tendrá siempre centro en cada hormiga.

Aplicamos la máscara a la matriz inicial, y nos quedan una serie de partículas olorosas dentro del área (o trozos de segmentos).

Iteramos para cada partícula encerrada, ponderando si queremos por la distancia y/o intensidad. Establecemos el ángulo del vector "d" y se asigna a uno de los sectores particulares.

La parte de las hormigas sí que lo dejaría como una lista normal, para poder iterar con comodidad. A cada una le puedes volver a asignar una lista de pasos, para luego poder realizar la animación.

Comparamos el sumatorio de los distintos sectores: obtenemos una nueva dirección (o no, y seguimos una aleatoria).

#54 ¿Con celda a qué te refieres? ¿Una posición en una matriz bidimensional?

Yo es que soy amante de discretizarlo todo... Al final, piensa que por mucho que operes en el continuo, Matlab SIEMPRE discretiza (aunque acaba siendo un mallado muy fino). Piensa que puedes discretizar todo lo que quieras, hacer la matriz de un millón por un millón (otra cuestión es que te quepa en tu RAM después xD).

#54 Pues entonces creo que vas bien. Échale rato a la codificación de cada celda, en vista a luego reutilizar esa misma matriz en otro tipo de simulaciones del problema.

Yo definiría un tipo nuevo para cada celda:

Bool ocupada
Bool esHormiga
Bool olorosa
Bool parteDeSegmento
Int intensidad
...
Int caducidad
Int varianzaOlor
Int comidaRestante
...
Bool volviendoANido
Int comidaCargada

Como puedes ver, hay muchas opciones dentro del posible objeto en cada celda. He puesto las que considero esenciales como las 5 primeras, pero es un problema abierto. La limitación de esto es que en cada celda sólo cabe una entidad, así que la hormiga tendría que pararse antes de llegar al objeto para no ser consumida por el vacío interdimensional de una celda ocupada (xD).

1 1 respuesta
B

#53 claro, es que no pensaba guardar los segmentos de esta manera. Pero esto que dices tú sería con celdas, si tienes una matriz de posiciones ya estás discretizando el espacio... Aunque puedo tener la lista de segmentos e irlos situando en celdas de manera "aproximada", ¿suena bien? Luego ya sería mirar en cada celda las posiciones exactas (yo creo que no cambiará mucho el resultado a hacerlo directamente con celdas pero es lo que discutimos en su momento con esvarianzza y quiero comprobarlo).

edit: Sí. Es decir tengo la matriz 1000x1000 y cada elemento de la matriz corresponde no a un punto en el plano sino a un cuadradito (una celda). Así, si en ese elemento de la matriz dice algo como 2359 sé que tengo que mirar los segmentos 2,3,5, y 9 (por inventarme mal y rápido una codificación xD), que estarán en ese cuadradito, si la máscara lo deja dentro del radio de la hormiga. No sé si me explico.

1 respuesta
LoRieN

¡Un post increíble!
Me ha interesado bastante el tema,pero no he tenido una asignatura específica de esto en la carrera.
¿Me dais algunas "directrices" para intentar ponerme al día sobre el asunto y seguir el hilo ?

No es que me suene a chino, es que quiero algo donde apoyarme xD

2 respuestas
Hipnos

#55 Coge Matlab y estudiate la forma de generar scripts, la estructura de los vectores y matrices y las funciones básicas del tipo "plot" y "stem".

El paso dos es intentar buscar aplicación a algunos métodos básicos, o factorizaciones (Cholesky, etc.). Entérate bien de las resoluciones con las que trabaja Matlab y su forma de operar.

Lo siguiente es proponerte algo, como Duronman, e intentar hacerlo.

1 respuesta
B

#55 me alegro de que te guste! Básicamente lo que te dice Hipnos es una muy buena manera de empezar. Si tienes algún proyecto que te gustaría mirar, podríamos hacerlo por aquí! Te recomiendo que al principio no te compliques con cosas muy difíciles matemáticamente.

Hay un libro que no me he leído así que no sé si está bien, que es el Mathematical Modelling, a lo mejor nos puede dar ideas de qué hacer.

BTW gente, voy progresando lento pero firme. Pegaría aquí el código pero es básicamente la parte aburrida de guardar los datos y generarlos (muy burdo todo xD)

1 respuesta
LoRieN

#56 Pues entonces, de momento centrarme en Matlab. Precisamente estoy últimamente liado con el Matlab así que voy a darle caña en esos aspectos. ¡ Muchas gracias !

#57 Pues voy a intimar con Matlab y intentaré ponerme con un proyecto sencillo matemáticamente. ¿De que autor es el libro que mencionas?

No os cortéis informando de vuestros avances o cualquier cosa que a mí y seguro que a más gente le interesa el tema

1 respuesta
B

#58 yo miré este http://books.google.es/books/about/An_Introduction_to_Mathematical_Modeling.html?id=adf515kSDOkC

También hay pdfs por google, los que he visto no me han desagradado.

Pero vaya, en coursera también hay cursos tipo "model thinking" (más sociales), y luego si te interesa un tema en concreto (por ejemplo a mí los sistemas dinámicos/teoría de bifurcaciones y las EDP/elementos finitos) ya tienes literatura para aburrir!

1 mes después
Hipnos

·. .·
["]/
-(-)-
/(_)\

1 respuesta