La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Curvas de Peano en el control de seguridad del aeropuerto

Posted by Carlos en noviembre 25, 2006

En los últimos años (justo a partir del 11-S) hemos podido ver cómo las medidas de seguridad en los aeropuertos se han ido haciendo cada vez más estrictas. Lo último ha sido la entrada en vigor de una nueva normativa que limita el tipo de productos que se pueden subir a bordo del avión, como líquidos, pastas, geles, etc. Técnicamente, todo es por nuestra seguridad, pero es innegable que la aplicación de las nuevas normas conlleva recorte de libertades, es propensa a abusos de autoridad, y puede hacerle a uno plantearse si no hay mucho de negocio en el asunto.

No voy a entrar en el trasfondo del tema, que ya ha sido ampliamente comentado, y que creo que está suficientemente claro (otra cosa es todo llegue a solucionarse en algún momento). Quería fijarme en un aspecto colateral que me llamó la atención mientras hacía una de esas interminables colas en los controles de seguridad de un aeropuerto (las matemáticas son excelentes para evadirse del hastío que ciertas situaciones provocan). Se trata de la disposición intrincada de la fila de personas a través de una especie de laberinto de cintas de seguridad. Lo más normal es encontrarse una especie de acordeón: uno empieza a hacer zigzag de izquierda a derecha, avanzando un poco cada vez que se llega a uno de los extremos del laberinto. ¿Es ésta la disposición más eficiente? Depende. Hay diferentes consideraciones que pueden tenerse en cuenta a la hora de organizar una cola de estas características. Vamos a fijarnos de momento en la longitud recorrida.

Supongamos que tenemos N personas en un área cuadrada de A m2, y que las disponemos de manera regular en la misma. Más o menos, esto es lo que tiende a suceder (la separación lateral suele ser un poco mayor de que frontal por el ancho de los pasillos delimitados, pero podemos ignorar esto de momento). La distancia D entre una persona y la que le sigue o precede en la fila sería

D=sqrt(A/N).

Si conforme la gente va entrando a la cola atraviesa esos pasillos en acordeón, pasando por esos puntos con dicha separación uniforme, la distancia L que cada persona recorre (una vez eliminados los elementos transitorios) sería L=N·D, o lo que es lo mismo

L=K sqrt(NA),

donde obviamente K=1 en este caso. ¿Podría hacerse más corta esta distancia? Sin duda. Para verlo, es útil recurrir a un problema muy bien conocido en el ámbito de la optimización combinatoria: el Problema del Viajante de Comercio (TSP, por sus siglas en inglés). El TSP consiste en buscar un camino de longitud mínima que pase por N ciudades y vuelva a la ciudad de partida. Esto último no es exactamente lo que sucede en la cola de un aeropuerto, pero no es demasiado preocupante: nos podemos imaginar que el punto de entrada a la cola está muy cerca del de salida, aunque haya que dar muchas vueltas antes de llegar a ésta. El TSP ha sido estudiado con enorme profundidad desde muy diferentes puntos de vista. En relación con lo que nos ocupa, se sabe por ejemplo que si se distribuyen N puntos al azar en un plano, la longitud del camino óptimo que los une viene dado por la expresión anterior, siendo K=0.725 (es un valor conjeturado; diferentes evaluaciones experimentales han dado valores entre 0.715 y 0.749). Esto ya supone una notable ventaja con respecto a lo anterior, pero hace falta determinar ese camino óptimo, lo cual es complejo si N es grande (pueden conseguirse soluciones quasi-óptimas eficientemente, pero vamos a dejar eso a un lado ahora).

Un enfoque más sistemático lo podemos encontrar en las curvas de rellenado de espacio (space-filling curves) o curvas de Peano, en honor de Giuseppe Peano, que fue quien primero las definió. Estas curvas cubren todo el plano (en realidad son generalizables a cualquier dimensionalidad, por lo que podemos cubrir un volumen, o cualquier hiperespacio que nos plazca), y son posibles gracias a que el segmento unidad de los números reales tiene la misma cardinalidad que cualquier espacio p-dimensional, como Cantor demostró. En los casos más intuitivos, podemos definir estas curvas de manera constructiva, partiendo de un segmento inicial, e iterando un cierto proceso de transformación sobre cada segmento de la curva, tal como se muestra a continuación:

3 iterations of the Peano curve, a space-filling curve

Como puede apreciarse, a medida que se va iterando el proceso se obtiene una curva cada vez más densa, que acaba por cubrir completamente el área deseada. Hay otras posibilidades, como la curva de Hilbert, o la curva de Sierpinski, entre otras muchas (aquí pueden verse diversos ejemplos). Norman y Moscato definieron una variante de la curva de Peano (a la que llamaron MPeano) en un artículo publicado en la revista Chaos, Solitons, and Fractals. Esta curva se caracteriza por un valor aproximado de K=0.659, y es además la solución óptima para la correspondiente instancia del TSP.

¿Por qué se recurre entonces al acordeón, si hay otras formas más compactas de disponer a la gente? Puede pensarse en varios motivos: es más complicado acotar los pasillos en este tipo de curvas, la gente puede desorientarse y sentirse incómoda si tiene que hacer muchos cambios de dirección, hay efectos finitos que pueden afectar a la posible ganancia en distancia, y sobre todo, ¿quién ha dicho que la prioridad de las mentes pensantes que organizan la seguridad de los aeropuertos es que andemos poco?

Anuncios

4 comentarios to “Curvas de Peano en el control de seguridad del aeropuerto”

  1. JJ said

    Qué mas da, si en realidad no se anda, sino que se está de pie… la prioridad debería ser que se procesara a la máxima cantidad de gente en la unidad temporal; y eso lo veo complicado.

  2. Carlos said

    Hombre, eventualmente se anda, si no vaya plan… Tienes razón en que la prioridad del aeropuerto es maximizar el throughput, que depende del tiempo que tarda un pasajero en recorrer el sistema, y del tiempo que se tarda en procesarlo en el punto de control. Normalmente esta última fase es el cuello de botella, pero no tiene por qué ser siempre así. Cada vez se estila más la cola única con varias máquinas paralelas al final, y en este caso el avance puede ser muy rápido. Por otra parte, el argumento de la longitud del recorrido es independiente de la velocidad de avance, y puede relacionarse también con el empaquetado eficiente de más gente.

  3. Juanlu said

    Gracias por tus artículos Carlos, me recuerdan a aquellas clases de ciencias del instituto en las que el profesor era capaz de despertarte la curiosidad por los fenómenos de la vida. Luego salías con la sensación de haber llenado algo el globo del conocimiento y eras más consciente de lo que desconocías en su periferia alentándote a seguir aprendiendo. Todo un placer leerte.

  4. Carlos said

    Muchas gracias Juanlu. Me honra la comparación. Aquí seguiremos, intentando entretenernos con la ciencia, y disfrutando del camino, que en estos temas es tan interesante como el destino.

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: