Spanish Algoritmo para calcular el camino mas corto.

[carlos7000]

Me han solicitado crear una aplicación para solucionar el siguiente problema.

Muchos pacientes y personal nuevo pierden citas y exámenes debido a la complejidad de una clínica. Aunque hay personal y avisos que señalan la ruta a las diferentes dependencias, no es posible tener un guía en cada esquina o pasillo, ni colocar un cartel en cada pared. Recientemente, una abuelita perdió una cita, porque le llevó una hora llegar al consultorio de cardiología. El complejo hospitalario es bastante grande, compuesto por varios edificios distribuidos en 2 cuadras. A veces, para ir de un lugar a otro, es necesario cruzar la calle. Un puente que conecta dos edificios o un túnel subterráneo que une otros dos edificios separados por la calle. Algunos edificios están conectados mediante un túnel subterráneo que atraviesa el sótano del parqueadero. Además, la altura de los edificios varía: uno tiene 3 pisos, otros 5 y uno de 10 pisos. Por ahora, los detalles exactos no son muy importantes.

En el complejo hospitalario encontramos parqueaderos, oficinas, consultorios, pasillos, elevadores, escaleras, restaurantes, habitaciones, unidades de cuidados intensivos, quirófanos, bodegas, cocina, salas de espera, lavandería y mucho más. Se trata de un verdadero laberinto. He pensado en crear un grafo (red de nodos) donde cada oficina, habitación, etc sea un nodo, y utilizar un algoritmo como el de Dijkstra para resolver el problema. Sin embargo, tengo muy pocos conocimientos sobre grafos. No estoy buscando el algoritmo más eficiente, rápido o que consuma menos recursos, solo el que sea mas sencillo de implementar en B4A.

Me gustaría escuchar sus ideas para abordar este problema utilizando B4A.

 

[William Lancee]

Un escenario simple.

Reservo una cita en línea con mi especialista en mi hospital. En la pantalla se muestra un código QR de confirmación.
Escaneo el QR con la aplicación GuideMe de mi teléfono.

Cuando llego a una de las diversas entradas del hospital, veo una estación azul de GuideMe con un código QR.
Enciendo la aplicación GuideMe en mi teléfono y escaneo el código QR en la estación.
Mi teléfono mostrará un conjunto detallado de instrucciones sobre cómo llegar desde esa estación de GuideMe a la ubicación de mi cita de destino.

En todo el hospital hay estaciones azules GuideMe (son placas QR baratas, pequeñas, simples y resistentes, no electrónicas).
Si me pierdo o simplemente quiero confirmar que voy en la dirección correcta, puedo actualizar mi aplicación GuideMe para obtener nuevas direcciones.

Notas:
La persona necesita tener un dispositivo.
La persona necesita llegar al hospital a tiempo.
La abuela aún puede faltar a su cita.

Complejidad:
Necesita un mapa 2D de varias capas del complejo completo. Esta es una empresa importante. El mapa debe estar actualizado.
¡Necesita un algoritmo que genere instrucciones para llegar desde cualquier estación de GuideMe a cualquier ubicación de destino!

 

[William Lancee]

Las siguientes son solo ideas a considerar, no recomendaciones.

Puede ser posible hacer toda la búsqueda de rutas en el propio dispositivo sin ninguna comunicación con un servidor central.
El mapa 2D multicapa del hospital se transforma en un gráfico conectado con nodos y bordes.
Cada nodo es una intersección de pasillos/túneles/puentes, cruces de carreteras, escaleras, puertas de ascensores además de todos los estatones QR y todas las ubicaciones objetivo.
Dos nodos están conectados con un borde si hay una ruta directa sin obstrucciones de un nodo al otro.

Cuando la aplicación basada en dispositivos necesita calcular una ruta desde una estación GuideMe hasta una ubicación de cita de destino, ocurre lo siguiente.

El algoritmo de optimización de colonias de hormigas (ver Wiki) encuentra una ruta corta a través del gráfico desde la estación GuideMe hasta una ubicación de cita de destino, con todas las descripciones de los nodos como instrucciones.
El problema se puede subdividir en tareas separadas, por ejemplo:
- encontrar una ruta desde donde estoy hasta una entrada al edificio A
- encuentre una ruta desde la entrada del edificio A hasta el ascensor más cercano al piso 3
- encuentre la ruta desde el ascensor en el piso 3 en el edificio A hasta la ubicación de destino

Esto debería ser lo suficientemente rápido como para hacerlo en tiempo real en el propio dispositivo.

La aplicación debe tener la información más reciente contenida en los gráficos.
Esto es crítico, pero difícil de lograr.
Los hospitales son conocidos por su construcción, reubicación de departamentos y personal, ubicaciones temporales, secciones restringidas, cierres y puertas cerradas con llave en varios momentos.

Las direcciones pueden ser texto o gráficos simples con flechas.

PD Trabajé toda mi vida en hospitales, y este proyecto me resulta muy interesante.

Una anécdota:
En medio de la noche, después de completar mi experimento en el laboratorio, di la vuelta equivocada en un pasillo semioscuro y terminé en la morgue.
Esto fue hace 56 años, pero lo recuerdo bien, incluido el olor a formaldehído.

[Tú eliges, pero creo que los miembros más allá de The Spanish Forum también pueden estar interesados]

 

[TILogistic]

Gracias @William Lancee admiro mucho tus publicaciones y codificación.

[Tú eliges, pero creo que los miembros más allá de The Spanish Forum también pueden estar interesados]

@carlos7000 esto te puede ayudar y puedes aplicar algoritmos .

IndoorMap

This is a wrap for this github project. IndoorMaps Author: DonManfred (wrapper) Version: 1 BitmapLayer Methods: Initialize (EventName As String, mapView As MapView, bitmap As Bitmap, location As PointF) IsInitialized As Boolean isAutoScale As Boolean Properties: AutoScale As Boolean [write...

www.b4x.com

 

[carlos7000]

[Tú eliges, pero creo que los miembros más allá de The Spanish Forum también pueden estar interesados]

Había considerado la idea, pero mi nivel de inglés es regular. Para participar en foros en inglés, me apoyo en un traductor, pero me he dado cuenta de que a veces entiendo bien la traducción y otras veces no expresa exactamente lo que quiero decir. Entiendo que es imposible traducir de manera precisa de un idioma a otro, pero en ocasiones la traducción se aleja bastante del texto original.

Aun así, es una excelente idea. Voy a publicarlo en el foro de inglés.

Muchas gracias por la sugerencia.

 

[carlos7000]

Las siguientes son solo ideas a considerar, no recomendaciones.

Puede ser posible hacer toda la búsqueda de rutas en el propio dispositivo sin ninguna comunicación con un servidor central.
El mapa 2D multicapa del hospital se transforma en un gráfico conectado con nodos y bordes.
Cada nodo es una intersección de pasillos/túneles/puentes, cruces de carreteras, escaleras, puertas de ascensores además de todos los estatones QR y todas las ubicaciones objetivo.
Dos nodos están conectados con un borde si hay una ruta directa sin obstrucciones de un nodo al otro.

Cuando la aplicación basada en dispositivos necesita calcular una ruta desde una estación GuideMe hasta una ubicación de cita de destino, ocurre lo siguiente.

El algoritmo de optimización de colonias de hormigas (ver Wiki) encuentra una ruta corta a través del gráfico desde la estación GuideMe hasta una ubicación de cita de destino, con todas las descripciones de los nodos como instrucciones.
El problema se puede subdividir en tareas separadas, por ejemplo:
- encontrar una ruta desde donde estoy hasta una entrada al edificio A
- encuentre una ruta desde la entrada del edificio A hasta el ascensor más cercano al piso 3
- encuentre la ruta desde el ascensor en el piso 3 en el edificio A hasta la ubicación de destino

Esto debería ser lo suficientemente rápido como para hacerlo en tiempo real en el propio dispositivo.

La aplicación debe tener la información más reciente contenida en los gráficos.
Esto es crítico, pero difícil de lograr.
Los hospitales son conocidos por su construcción, reubicación de departamentos y personal, ubicaciones temporales, secciones restringidas, cierres y puertas cerradas con llave en varios momentos.

Las direcciones pueden ser texto o gráficos simples con flechas.

PD Trabajé toda mi vida en hospitales, y este proyecto me resulta muy interesante.

Una anécdota:
En medio de la noche, después de completar mi experimento en el laboratorio, di la vuelta equivocada en un pasillo semioscuro y terminé en la morgue.
Esto fue hace 56 años, pero lo recuerdo bien, incluido el olor a formaldehído.

[Tú eliges, pero creo que los miembros más allá de The Spanish Forum también pueden estar interesados]

Voy a ir llevando registro de las diferentes sugerencias.

Muchas gracias por sus sugerencias.

 

[William Lancee]

El español no es mi idioma, así que he usado Google para traducir mi inglés al español.
Cuando hago clic en el botón traducir en el foro español, la traducción al inglés parece perfecta.

 

[edgar_ortiz]

La aplicación debe tener la información más reciente contenida en los gráficos.
Esto es crítico, pero difícil de lograr.
Los hospitales son conocidos por su construcción, reubicación de departamentos y personal, ubicaciones temporales, secciones restringidas, cierres y puertas cerradas con llave en varios momentos.

Para solucionar este problema, en la base de datos del telefono, debe de existir la fecha de ultima actualización, para revisar según la información del servidor y actualizarla cuando sea necesaria.

Saludos,

Edgar

P.D.:
Muy buena tu idea

 

[carlos7000]

El español no es mi idioma, así que he usado Google para traducir mi inglés al español.
Cuando hago clic en el botón traducir en el foro español, la traducción al inglés parece perfecta.

We are more or less the same.

Thank you very much for your help and suggestion.

Translated by Google

 

[roerGarcia]

¿Como va este tema?

Se me ocurre una alternativa: describir cada sitio de interes (consultorio, sala de espera, laboratorio) en terminos de pertenencia desde el nivel superior. (Edificio, Piso, "nivel"), de manera que el consultrio del Dr Erel se encuentra en el Edificio B, piso 3. Si la aplicacion puede captar el area destino en esos terminos, tal vez una busqueda amable con filtros, podria determinarse la ruta partiendo desde el "entry point" que por lo general seria una de las puertas de acceso donde podria informarse al paciente de si va por el camino correcto, tambien seria requerida la ruta desde el entry point hasta el destino tomandola de la base de datos.

Habia pensado tambien que en vez de un mapa 2d como mencionaban aqui antes se hiciera una matriz de puntos, cada punto un sitio especifico con la info de cercania, direccion, nivel. Pero me parece mas sencillo la primera que menciono aqui.

Saludos.

 

[carlos7000]

¿Como va este tema?

Se me ocurre una alternativa: describir cada sitio de interes (consultorio, sala de espera, laboratorio) en terminos de pertenencia desde el nivel superior. (Edificio, Piso, "nivel"), de manera que el consultrio del Dr Erel se encuentra en el Edificio B, piso 3. Si la aplicacion puede captar el area destino en esos terminos, tal vez una busqueda amable con filtros, podria determinarse la ruta partiendo desde el "entry point" que por lo general seria una de las puertas de acceso donde podria informarse al paciente de si va por el camino correcto, tambien seria requerida la ruta desde el entry point hasta el destino tomandola de la base de datos.

Habia pensado tambien que en vez de un mapa 2d como mencionaban aqui antes se hiciera una matriz de puntos, cada punto un sitio especifico con la info de cercania, direccion, nivel. Pero me parece mas sencillo la primera que menciono aqui.

Saludos.

Quisiera compartir que recientemente he estado dedicando tiempo al estudio de diversos algoritmos de búsqueda, entre ellos el algoritmo de Dijkstra. Durante mi investigación, me encontré con varios programas en distintos foros que trataban este tema. Si bien llevo mucho tiempo programando, noté que muchos de estos programas carecían de una documentación detallada. Aunque los nombres de las funciones y variables eran descriptivos en su mayoría, no proporcionaban la claridad necesaria para comprender su funcionamiento en profundidad.

Debido a esta situación, tomé la iniciativa de desarrollar mi propio algoritmo. Si bien reconozco que este podría no ser tan rápido ni eficiente como otros en el ámbito, logré construir una solución que aborda el problema de manera más comprensible. Es importante mencionar que, al enfrentar situaciones en las que el número de nodos es considerable, mi algoritmo tiende a ralentizarse significativamente.

Continúo mi estudio en el campo de los grafos con el objetivo de refinar y mejorar aún más mi algoritmo. Mi meta es alcanzar un punto en el que pueda abordar eficientemente incluso conjuntos de nodos más amplios y complejos.

 

[William Lancee]

No olvide que a menudo puede reorganizar gráficos complejos como una jerarquía de gráficos más simples.
Por ejemplo:
Nivel superior un gráfico de edificios (una docena de nodos)
Nivel Medio, para cada edificio un gráfico de pisos (una docena de nodos)
Nivel Inferior, para cada piso un gráfico de departamentos (una docena de nodos)
Nivel más bajo, para cada departamento un gráfico de oficinas (nodos de una dozona)
En cuyo caso, la tarea lleva cuatro veces el tiempo que se tarda en navegar por una docena de nodos.

 

[carlos7000]

No olvide que a menudo puede reorganizar gráficos complejos como una jerarquía de gráficos más simples.
Por ejemplo:
Nivel superior un gráfico de edificios (una docena de nodos)
Nivel Medio, para cada edificio un gráfico de pisos (una docena de nodos)
Nivel Inferior, para cada piso un gráfico de departamentos (una docena de nodos)
Nivel más bajo, para cada departamento un gráfico de oficinas (nodos de una dozona)
En cuyo caso, la tarea lleva cuatro veces el tiempo que se tarda en navegar por una docena de nodos.

Es una gran sugerencia. Voy a tratar de implementarlo.

Muchas gracias.

 

[geminw]

Hola, hace ya unos años me plantearon el mismo problema y aquí lo encuentro nuevamente. En este momento creo que es posible hacerlo combinando las tecnologías actuales. Hace unos días hice un posteo de una implementacion del algoritmo de Dijkstra que resuelve una cuadricula, que imagino puede ser superpuesta a un plano del lugar.

Por otro lado para la identificación de cada elemento de la cuadricula, utilizaría un dispositivo bluetooth BLE, que emite un beacon que lo identifica. Esto se puede encontrar comercialmente como tags bluetooth para encontrar llaves, mascotas, etc o implementar un dispositivo propio con un ESP32.

Cada rectángulo de la cuadrícula podría abarcar alrededor de 20 metros x 20 metros (que esta dentro del alcance de bluetooth) y luego utilizar la lectura de la potencia recibida mediante una app, para guiar a la persona hasta el destino.

De esta manera leyendo el beacon de mayor potencia recibido, podemos establecer el inicio del algoritmo de Dijkstra (alojado en un servidor), mientras que el destino lo selecciona la persona, mediante una aplicación. Así, se ingresan los datos a la cuadricula y nos devuelve la secuencia del recorrido a realizar. Luego mediante la potencia de los beacons nos guía hacia el destino.

Sería necesario una base de datos que relacione los ID de los beacons con el lugar donde se encuentran, las personas que trabajan en el sector y los sectores del hospital como rayos, quirófanos, estacionamiento, etc. Si el lugar tiene varios pisos, cada piso puede tener su propia cuadricula.

Otra ventaja de la cuadricula, es que se pueden cambiar de lugar los obstáculos y así calcular el nuevo camino. La base de datos que relaciona los ID de los beacons con las cuadriculas y las personas o sectores del edificio pueden ser cambiadas y todo funcionaría en forma dinámica.

Esta es mi idea de cómo debería funcionar, espero poder aportar algo a la solución de este problema que es muy interesante.

Saludos!