Tesis de Licenciatura

Modelos y algoritmos de optimización combinatoria para planificación de rutas en regatas de barcos de vela

Tesistas

Director

Federico E. Martínez

Dr. Javier Marenco

[email protected]

lu 17/06

Gonzalo Sainz‒Trápaga [email protected]

lu 454/06

Diciembre de 2010 Departamento de Computación Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires

[email protected]

Co‒director

Dr. Tomás Tetzlaff [email protected]

Resumen Los barcos de vela compiten en eventos denominados “regatas”, cuyo objetivo consiste generalmente en recorrer un circuito determinado en el menor tiempo posible. Aunque existen regatas de duraciones que van desde menos de una hora hasta varios meses, en todos lo casos interviene fuertemente el planeamiento estrat´egico: la velocidad de las embarcaciones est´ a determinada en gran medida por las condiciones meteorol´ ogicas. Las herramientas computacionales existentes para toma de decisiones de estrategia en regatas est´ an fuertemente orientadas a las regatas de larga distancia. Bas´ andose en un pron´ ostico meteorol´ ogico y en una predicci´ on num´erica del comportamiento de un barco, pueden indicar a los navegantes las rutas m´ as veloces para la situaci´ on pronosticada. Sin embargo, no hacen consideraciones sobre la fiabilidad del pron´ ostico ni ning´ un tipo de optimizaci´ on estoc´ astica. Las regatas de corta distancia, por su parte, transcurren en extensiones de tiempo y espacio que est´ an fuera del alcance de los pron´ osticos; los fen´ omenos dominantes que condicionan la estrategia se originan en las turbulencias atmosf´ericas. En este contexto, las herramientas existentes no tienen utilidad pr´ actica. En esta tesis se abord´ o el problema de las regatas de corta distancia, buscando desarrollar herramientas que ayuden a los regatistas a tomar decisiones en funci´ on de mediciones realizadas en tiempo real por instrumentos de navegaci´ on instalados en el barco. Con este fin, desarrollamos un modelo de optimizaci´ on combinatoria teniendo en cuenta las caracter´ısticas propias de las regatas de corta distancia que se desprecian en los modelos de gran escala. Propusimos a su vez un algoritmo eficiente para la optimizaci´ on de rutas en este modelo con informaci´ on completa, y una serie de heur´ısticas inspiradas en conocimiento experto del dominio del problema. A partir de un modelo de simulaci´ on de condiciones meteorol´ ogicas implementado para tal fin, contrastamos el rendimiento de las heur´ısticas. ´ Estas logran, en condiciones favorables y bajo informaci´ on incompleta, ubicarse a menos de 2 % de las rutas o ´ptimas realizando s´ olo procesamiento en tiempo real. Abstract In sailboat racing, boats try to go over a circuit in the shortest possible amount of time. Although sailboat race durations can be as short as half an hour or as long as half a year, in all cases strategic planning is of the upmost importance: the speed of the boats over the water is mostly determined by the weather conditions they find along their path. Existing computer tools for strategic decision–making are highly biased towards long distance races. Based on weather forecasts and an accurate prediction of sailboat performance, these tools help sailors find the fastest routes for the expected conditions. However, not much is done in the way of dealing with the inherent imperfections that are present in forecasts. There are no stochastic optimization tools in the market. On the other hand, short distance racing takes place in short spans of time and space that forecasting tools cannot predict; the phenomenons that have the highest amount of influence on strategic decisions are caused by atmospheric turbulence, which no available weather model takes into account. In this context, existing tools have no practical application. In this thesis we focus on short distance racing, in an attemt to develop tools for decision– making that take advantage of real–time weather data made available by on–board weather sensors and electronics. For this purpose, we developed a combinatorial optimization model that accounts for the specific characteristics of short distance racing that large–scale models disregard. At the same time, we propose an efficient algorithm for route optimization under complete information, as well as heuristic methods inspired in the knowledge of experts in the field of sailboat references. Using a weather simulation model that we created for this purpose, we can analyze the results obtained by our heuristic methods in realistic setups. In favorable conditions, the routes generated in real-time by our algorithms are less than 2 % away from the optimal ones.

´Indice 1

Introducci´ on

3

1.1 El mundo de la vela 1.1.1 Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Embarcaciones de vela . . . . . . . . . . . . . . . . . . . 1.1.2.1 ¿C´ omo hace un velero para navegar contra el viento? 1.1.2.2 Predicciones de velocidad . . . . . . . . . . . . . . . 1.1.3 Regatas de vela . . . . . . . . . . . . . . . . . . . . . . . 1.1.3.1 ¿C´ omo se gana una regata? . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 3 3 5 6 9 10

1.2 Estado del arte 1.2.1 La ventaja estrat´egica . . . . . . . . . 1.2.2 Herramientas existentes . . . . . . . . 1.2.3 Limitaciones caracter´ısticas . . . . . . 1.2.3.1 Distintas escalas de optimizaci´on 1.2.3.2 El agua . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

11 11 12 14 15 17

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1.3 Resumen del trabajo

2

3

18

El modelo

20

2.1 La predicci´ on de velocidad 2.1.1 Velocidad bajo corriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20 21

2.2 Modelado de la cancha 2.2.1 El ´ area de inter´es . . 2.2.2 El grafo de rutas . . . 2.2.2.1 Las maniobras . 2.2.2.2 C´ alculo de costos

25 25 26 27 32

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Algoritmo Exacto 3.1 C´ omputo de la ruta ´ optima 3.1.1 Camino m´ınimo en grafos independientes del tiempo 3.1.1.1 Algoritmo A∗ . . . . . . . . . . . . . . . . . . . . 3.1.2 Camino m´ınimo en grafos dependientes del tiempo . . 3.1.2.1 Camino m´ınimo en grafos FIFO . . . . . . . . . 3.1.3 Heur´ısticas propuestas para A∗ . . . . . . . . . . . . .

35 . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

35 35 35 36 38 39

3.1.3.1 Heur´ıstica basada en distancia cartesiana . . . . . . . . . . . . . . . . . . . 3.1.3.2 Heur´ıstica basada en VMC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Algoritmo final para rutas ´ optimas . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Implementaci´ on

4

5

41

Heur´ısticas

44

4.1 ¿Por qu´ e desarrollar heur´ısticas?

44

4.2 Framework para heur´ısticas

45

4.3 Criterios de decisi´ on 4.3.1 Criterio de mayor VMG ponderado . . . . . . 4.3.2 Criterio de mayor VMG ponderado y distancia 4.3.3 Criterios asim´etricos . . . . . . . . . . . . . . . 4.3.4 Criterios de viento promedio . . . . . . . . . .

46 46 48 49 49

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Experimentaci´ on 5.1 El 5.1.1 5.1.2 5.1.3 5.1.4

6

39 40 41

modelo experimental Calidad de los escenarios a utilizar . Obtenci´ on de los datos . . . . . . . El modelo de simulaci´ on . . . . . . La corriente y el barco . . . . . . .

53 . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

53 53 54 55 59

5.2 Heur´ısticas para A*

60

5.3 Comportamiento del modelo 5.3.1 Cantidad de nodos por lado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Cantidad de cuadrantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Cantidad de tiempos de cambio . . . . . . . . . . . . . . . . . . . . . . . . . . .

63 63 66 66

5.4 Heur´ısticas 5.4.1 Modelo para experimentaci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1.1 Optimizaci´ on de los par´ametros . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1.2 Comparaci´ on de las heur´ısticas . . . . . . . . . . . . . . . . . . . . . . . . .

68 68 68 70

Conclusiones

79

6.1 Balance del trabajo

79

6.2 Trabajos futuros

79

Mart´ınez, Sainz–Tr´ apaga

P´agina 1 de 82

Agradecimientos A Javier Marenco, que acept´ o con ganas dirigir esta tesis sobre un tema bastante extra˜ no, y siempre estuvo disponible para asistirnos (y tranquilizarnos) en todo lo que necesitamos. A Alberto Enguix, que nos abri´ o las puertas de su casa para enterarse de qu´e est´abamos haciendo, y nos ayud´ o con la mejor onda para que avanz´aramos con nuestro trabajo en la zona gris de la meteorolog´ıa a peque˜ na escala. A Andrew Philpott, cuya investigaci´on y publicaciones nos permitieron no empezar de cero con esta historia de ruteo de veleros. A Pablo Jacovkis, que nos dijo que s´ı, que seguramente pod´ıamos hacer una tesis sobre esto. A Tom´ as Tetzlaff, por su colaboraci´ on con el trabajo. A Tate de empopado.com, que se interes´o por nuestro trabajo y nos facilit´ o cantidades de datos que finalmente no pudimos usar. A Mar´ıa Eugenia Dillon, que corri´ o simulaciones meteorol´ogicas de alta resoluci´on para nosotros. A nuestros compa˜ neros: Checho, Metegol, Gonza Rubio, Victoria, Page, Marta, Emilio, Santi, que hicieron de estos 5 a˜ nos un per´ıodo inolvidable, a´ un en los momentos m´as ´asperos en que viv´ıamos en los laboratorios y dorm´ıamos tan poco. A todos los profesores y ayudantes extraordinarios que conocimos a lo largo de todos estos a˜ nos, que con su trabajo y dedicaci´ on nos inspiran d´ıa a d´ıa. A los que nos olvidamos de nombrar, que seguramente son varios. Y finalmente a 40 millones de argentinos que sostienen esta Universidad, y que nos permiten a unos pocos afortunados acceder a una educaci´on superior p´ ublica, gratuita y de primer nivel.

Agradecimientos de Gonzalo A mi Mam´ a (a la que no le gusta que le diga “vieja”), que me llev´o a una colonia de vacaciones donde me sub´ı por primera vez a un Optimist, que me tuvo paciencia todos estos a˜ nos y se preocup´ o por cada detalle1 . A mi viejo, por su incondicionalidad. Por su inter´es en lo que sea en que ando metido, y por unos 300 desayunos antes de entrar a clase que nos valieron el “¿Lo de siempre? ” no en una, sino en varias cafeter´ıas. A mi hermana Mariana, que me explic´o las fracciones cortando un alfajor de chocolate, y me dijo que en el Pabell´ on 1 hab´ıa gente como yo. Y a mi cu˜ nado, que aunque lo niegue encajar´ıa bien en el Pabell´ on 1. A Natal´ı, que me ense˜ n´ o a pedir disculpas y a reirme de m´ı mismo, y me amans´o a lo largo de estos a˜ nos. Gracias de parte m´ıa y de todos los que tienen que tratar conmigo. 1 ¡S´ olo 3 minutos atr´ as acabo de recibir un mail de ella con un link a la p´ agina de una imprenta donde me pueden imprimir la tesis!

Mart´ınez, Sainz–Tr´ apaga

P´agina 2 de 82

A mi familia. Y a mis amigos, que ya son familia, por su amistad. A Fede, por una lecci´ on de 5 a˜ nos sobre la humildad, la dedicaci´on y el esfuerzo. A los que se fueron, por sus ense˜ nanzas. A los que intentan superarse, por ser una fuente de inspiraci´on.

Agradecimientos de Federico Afortunadamente son muchas las personas a las que tengo que agradecer, ya que son muchos los que de una u otra forma hicieron cosas por m´ı. Primero y antes que nada, dar gracias a Dios, por estar conmigo en cada paso que doy y por haber puesto en mi camino a aquellas personas que han sido mi soporte y compa˜ n´ıa durante toda mi carrera. Agradecer a mis viejos, que me apoyaron, me bancaron, estuvieron siempre, sobre todo en los momentos dif´ıciles, que los tuvimos que pasar. Sin duda, no podr´ıa haber llegado a donde llegu´e si no fuera por ellos, y por su esfuerzo constante. Son un ejemplo y un orgullo para m´ı. No puedo dejar de agradecerle a mi hermana Estafan´ıa (o Rudy) porque ella tambi´en me banc´ o mucho durante toda la carrera, ¡¿en cuantos parciales la habr´e vuelto loca con mis nervios?! A mis abuelos tambi´en debo dedicarles un p´arrafo. Su constante apoyo y consejo fueron fundamentales para que hoy sea lo que soy. Sabri se gan´ o el cielo con la paciencia que me tuvo todo este tiempo. ¡Peluca gracias por tu amor, tu compa˜ nia y tu comprensi´ on! Le agradezco a GomoX por su amistad, sin duda una de las mejores cosas que me llevo de la facultad. Sos una excelente persona, y un mejor amigo. A Emi por ser tan buen amigo, a mi madrina que hace mucho por m´ı, y a muchos m´as que el espacio me impide nombrar, ¡Gracias!

Mart´ınez, Sainz–Tr´ apaga

P´agina 3 de 82

Cap´ıtulo 1

Introducci´ on 1.1. 1.1.1.

El mundo de la vela Historia

En 1848 la compa˜ n´ıa de joyer´ıa londinense Garrard & Co forj´ o una enorme jarra de plata que fue bautizada entonces como “la copa de las 100 guineas”, haciendo referencia a su valor monetario. Tres a˜ nos m´ as tarde, Henry William Paget, primer marqu´es de Anglesey, compr´ o la jarra y la don´ o al Royal Yacht Squadron como premio para su regata alrededor de la isla de Wight que tendr´ıa lugar en 1851. A mediados del siglo XIX, Inglaterra era la naci´on m´as industrializada del mundo y la Royal Navy era poco menos que la joya de la corona. Sin embargo, la flota inglesa fue derrotada por la u ´nica embarcaci´ on norteamericana que particip´o en la regata: la goleta Am´erica. En un evento de car´ acter prof´etico, el peque˜ no, moderno y liviano barco americano se impuso a la pesada flota inglesa hiriendo as´ı el orgullo de la primera potencia mundial. Tras esta victoria el trofeo fue rebautizado “Copa Am´erica”, en honor al barco triunfador. Hoy, m´ as de 160 a˜ nos despu´es de que la jarra fuera forjada, la Copa Am´erica se sigue disputando: se trata del trofeo deportivo m´ as antiguo que a´ un se compite en la actualidad. Ya no con goletas y bergantines de madera portando velas de algod´on egipcio, sino Figura 1.1: La Copa Am´erica con dise˜ nos ultramodernos construidos con laminados compuestos, verdaderas obras de ingenier´ıa comparables a las de la industria aeroespacial. Sin embargo, el esp´ıritu del deporte se mantiene intacto. Equipos de todo el mundo compiten, impulsados u ´nicamente por el viento, en carrera hacia el hist´orico trofeo.

1.1.2.

Embarcaciones de vela

La caracter´ıstica primordial de los veh´ıculos a vela es que obtienen la energ´ıa necesaria para su movimiento a partir del viento. Si bien este trabajo se enfoca mayormente en embarcaciones, la gran mayor´ıa de los conceptos se transfieren de forma an´aloga a otro tipo de veh´ıculos e´olicos como los iceboats o karts a vela. Estos u ´ltimos tienen la ventaja de desplazarse sobre superficies s´olidas, que por ofrecer en general una menor resistencia al avance que el agua sobre la que navegan los veleros, permiten que desarrollen velocidades bastante superiores.

Mart´ınez, Sainz–Tr´ apaga

(a) La goleta Am´ erica

P´agina 4 de 82

(b) El trimar´ an Oracle BMW

Figura 1.2: Los ganadores de la Copa Am´erica en 1851 y 2010 Numerosos avances tecnol´ ogicos desde la ´epoca de las fragatas permiten a las embarcaciones modernas navegar en circunstancias que antes se consideraban imposibles con un rendimiento sorprendente. Tanto veh´ıculos terrestres como marinos logran con la tecnolog´ıa actual dos hitos fundamentales: Pueden avanzar en direcci´ on opuesta al viento, y Pueden navegar m´ as r´ apido que el viento que los propulsa. Estas dos cualidades provienen de las propiedades aerodin´ amicas de las velas modernas. Intuitivamente, la idea b´ asica que viene a la mente es que las velas de un barco se comportan como un paraca´ıdas: al retener el viento y frenarlo, producen una fuerza de arrastre que la embarcaci´ on puede utilizar para desplazarse. Sin embargo resulta bastante claro que, a partir de esta idea, ser´ıa imposible que una embarcaci´on se desplace en direcci´ on opuesta al viento, ya que cualquier empuje que se obtenga de frenar una corriente de aire solo puede estar orientado en la direcci´on de dicha corriente. En efecto, las velas modernas tienen la capacidad de adquirir un comportamiento aerodin´amico comparable al del ala de un avi´ on. As´ı, desarrollan una fuerza de succi´ on que permite a los veh´ıculos a vela desplazarse en contra del viento. Sin embargo, al igual que el ala de un avi´ on, deben mantener un ´angulo de incidencia apropiado respecto de la corriente de aire para evitar que se desarrollen turbulencias (situaci´on que en la jerga aeron´ autica se denomina “entrar en p´erdida”).

Figura 1.3: Un velero moderno

Mart´ınez, Sainz–Tr´ apaga

P´agina 5 de 82

(a) Velero vs. ala de avi´ on F-22

(b) Velero vs. misil Tomahawk

Figura 1.4: Comparaci´on entre ap´endices de veleros y aeronaves La situaci´ on que se produce bajo el agua es similar a la de las velas. La parte sumergida de un velero tiene tambi´en ap´endices hidrodin´amicos que son una parte vital de sus cualidades n´auticas. Como se observa en la Figura 1.4, las similitudes entre los perfiles aero e hidrodin´amicos de un velero y las alas de un avi´ on son innegables.

1.1.2.1.

¿C´ omo hace un velero para navegar contra el viento?

Las velas de una embarcaci´ on moderna, a diferencia de las alas de un avi´on, pueden funcionar en 2 reg´ımenes. El primero es el que corresponde al paraca´ıdas ya mencionado, donde las velas no hacen sino intentar “detener” el viento, tomando as´ı parte de su energ´ıa. Este r´egimen se conoce como r´egimen turbulento. El segundo corresponde al comportamiento propio de un ala, y se denomina r´egimen laminar. Es precisamente este u ´ltimo el que le permite a un velero desplazarse contra el viento, as´ı como le permite a un avi´on vencer la gravedad.

(a) R´ egimen Turbulento

(b) R´ egimen Laminar

(c) “Proa al viento”

Figura 1.5: Distintos modos de funcionamiento del plano v´elico Para mantener un r´egimen laminar, que es el de mayor eficiencia, es necesario que el ´angulo de incidencia del viento sobre las velas sea suficientemente chico. Si las velas se colocan perpendiculares

Mart´ınez, Sainz–Tr´ apaga

P´agina 6 de 82

al viento, como se observa en la Figura 1.5a, es inevitable que las mismas entren en p´erdida y se produzca una turbulencia ya que el flujo de aire no puede mantenerse adherido a las mismas. Por otra parte, si el ´ angulo de incidencia del viento sobre las velas es demasiado chico, la succi´on producida ser´ a demasiado peque˜ na para sostener su forma y estas flamear´an como una bandera (Figura 1.5c). En raz´ on de estas limitaciones, un velero moderno puede navegar contra el viento hasta un ´ngulo de incidencia de unos 40o . Si el timonel de una embarcaci´on intenta navegar a un ´angulo de a incidencia menor, sus velas flamear´ an y la embarcaci´on se detendr´a por completo. Por el contrario, si bien el r´egimen turbulento no es ´ optimo desde un punto de vista aerodin´amico, es posible navegar directamente a favor del viento sin problemas 2 . Sin embargo, estos 40o de aproximaci´on al viento son suficientes para alcanzar cualquier destino mediante la t´ecnica que se denomina bordejeada (o, m´as coloquialmente, tirar bordes). La misma consiste en describir un recorrido de zig-zag con la embarcaci´on, avanzando progresivamente en contra del viento. As´ı, colocando las velas alternativamente de un lado y de otro de la embarcaci´on se navega en direcciones sim´etricas respecto del viento. La maniobra que consiste en reorientar el barco de una direcci´on (“borde”) a la otra en este zig-zag se denomina virar, y ser´a de particular inter´es para nuestro trabajo. Las situaciones ilustradas anteriormente son estereot´ıpicas: hay una buena parte de los reg´ımenes que son mixtos (es decir, parcialmente turbulentos y parcial´ mente laminares). Estos corresponden a los ´angulos de incidencia intermedios que se encuentran entre los 180o y los 40o exhibidos en la Figura 1.5. Estas situaciones intermedias son en general las que permiten obtener una mayor velocidad, lo que redunda en algunas situaciones curiosas. Por ejemplo, en muchos barcos resulta m´as r´apido hacer una suerte de bordejeada para navegar no solo contra el viento ¡Sino tambi´en a favor! Figura 1.6: Velero bordejeando 1.1.2.2.

Predicciones de velocidad

A pesar de los rasgos comunes que comenzamos a discutir, hay muchas diferencias entre una embarcaci´ on y otra. En el contexto de las carreras de barcos (regatas), sin duda una cuesti´on esencial es la velocidad. Con la tecnificaci´on progresiva del dise˜ no naval, se desarrollaron modelos num´ericos complejos de predicci´ on de velocidad para veleros que se conocen en el ambiente como vpps (Velocity Prediction Programs). 2 Este tipo de navegaci´ on es en general lenta e inestable. La expresi´ on com´ un que dice que algo va “viento en popa” no est´ a bien fundada desde el punto de vista n´ autico.

Mart´ınez, Sainz–Tr´ apaga

P´agina 7 de 82

Los mismos intentan responder una pregunta aparentemente sencilla: ¿Qu´e velocidad desarrollar´ a una embarcaci´ on? Para esto, se valen de algunos datos esenciales, en particular: Las caracter´ısticas f´ısicas del barco (peso, longitud, superficie v´elica, etc.), Las condiciones meteorol´ ogicas (intensidad, direcci´on del viento, tama˜ no de las olas, etc.), y La direcci´ on en la que se desea navegar, Es evidente que esta pregunta es muy relevante para el dise˜ nador de una embarcaci´on de regata. Sin embargo, resulta muy dif´ıcil de responder. En primer lugar, la mec´anica de fluidos computacional, herramienta primordial en el estudio de estos procesos, es un problema complejo en todas sus escalas. En segunda instancia, la cantidad de variables que afectan significativamente el comportamiento de una embarcaci´ on de vela es inmensa, lo que dificulta aun m´as la simulaci´on num´erica. Por u ´ltimo, las embarcaciones a vela funcionan a merced del viento y las olas, variables que son pr´ acticamente imposibles de controlar en la escala necesaria. En particular, t´ uneles de viento y tanques de prueba nunca funcionan de manera combinada. Sin ir muy lejos, reci´en con el advenimiento del gps fue posible hacer una medici´on medianamente fiable de la velocidad de un barco en aguas abiertas. Antes resultaba esencialmente imposible. Tengamos en cuenta que las velocidades en tierra se pueden medir con precisi´on ¡Desde la invenci´ on del cron´ ometro! A pesar de la inmensa dificultad, con el correr de los a˜ nos se desarrollaron varios sistemas de predicci´ on de velocidad que se comportan razonablemente bien. En gran medida, la motivaci´on detr´ as de estos desarrollos est´ a en la creaci´on de sistemas de handicap para permitir que compitan entre s´ı veleros distintos. En base a la predicci´on de un vpp se puede establecer una serie de compensaciones que permita, hasta un punto, nivelar barcos m´as lentos con otros m´as r´apidos. Sin embargo, dada la gran complejidad del problema a atacar, estas f´ormulas de medici´on parecen estar condenadas al fracaso: una vez que una regla de handicap se torna popular, los ingenieros navales comienzan a descubrir y explotar sus falencias, dise˜ nando barcos espec´ıficamente para tal fin. Por lo tanto, muchas veces se recurre a handicaps asignados “a ojo” (en general a puertas cerradas): “La Santa Mar´ıa recorre la misma distancia que La Ni˜ na en 10 % menos de tiempo”. Es el caso de las f´ ormulas phrf y irc. La primera f´ ormula de medici´ on popular con fundamentos cient´ıficos fue el International Measurement System (ims) que surgi´ o en 1985 a partir de la investigaci´on realizada en el mit por Kerwin y Newman [21]. La misma consta de un vpp, que entrega una predicci´on completa de la velocidad de cada barco en condiciones predefinidas, a partir de una serie de mediciones del mismo. Si bien ims tambi´en fue v´ıctima de la ingenier´ıa, por sus s´olidos fundamentos cient´ıficos se reedit´ o en los u ´ltimos a˜ nos (con actualizaciones varias) como la renovada f´ormula Offshore Racing Congress (orc). Sin lugar a dudas un gran aporte de la f´ormula ims fue poner a disposici´on del navegante com´ un la salida de un vpp de primera l´ınea, informaci´on que por lo general estaba reservada a los grandes estudios de dise˜ no. Dicha informaci´ on son las llamadas curvas polares caracter´ısticas de una embarcaci´ on.

Mart´ınez, Sainz–Tr´ apaga

P´agina 8 de 82

0º

45º

315º

2

270º

225º

4

6

8

10

12

90º

135º

180º

Figura 1.7: Curva polar de un velero clase Farr 36 con 18 nudos de viento

La Figura 1.7 exhibe la curva polar caracter´ıstica de un velero de regata de 36 pies que navega con un viento de 18 nudos de intensidad3 . La velocidad del barco se representa en forma radial, mientras que el ´ angulo de incidencia del viento sobre el barco est´a representado en la coordenada angular. Como era de esperarse, este barco no puede navegar directamente en contra del viento: con un ´ angulo de incidencia de 0o , su predicci´on de velocidad es de 0 kts. M´as a´ un, todos los angulos entre 0o y 28o (y los ´ ´ angulos sim´etricos, entre 0o y 332o ) le est´an “vedados”. Esta es la zona en que las velas del velero flamean. Sin embargo, si el timonel orienta el barco de forma tal que el viento incida sobre el mismo con un ´ angulo de 45o , podr´ a desarrollar casi 8 kts de velocidad. Lo mismo ocurre con un ´angulo de incidencia de 315o : este es el borde complementario en la situaci´on de bordejeada de la Figura 1.6. En general, las curvas polares de las embarcaciones sim´etricas son sim´etricas dado que para un mismo ´ angulo de incidencia, el lado por el que incida el viento resulta indistinto. Este barco adem´ as tiene la posibilidad de mejorar su velocidad en la direcci´on del viento (es decir, con un ´ angulo de incidencia de 180o ) haciendo una nueva bordejeada. Como se observa en 31

nudo = 1 kt (knot) = 1 milla n´ autica por hora = 1.852 Km/h

Mart´ınez, Sainz–Tr´ apaga

P´agina 9 de 82

la curva polar, navegando directamente con un ´angulo de 180o la velocidad ser´a de apenas 8 kts, mientras que si se realizan dos bordes con ´angulos de 155o y 205o respectivamente, la velocidad resultante en la direcci´ on deseada ser´ a bastante superior (alrededor de 11 kts). Esta velocidad resultante se conoce como Velocity Made Good (vmg), y es un concepto fundamental en navegaci´on a vela4 . En efecto, la posibilidad que tienen los veleros de desplazarse m´as r´apido en la direcci´on deseada haciendo una bordejeada en lugar de navegar en l´ınea recta es el punto de partida para nuestra investigaci´ on. Un vpp provee por lo general un conjunto de curvas, correspondiendo cada una de ellas a una intensidad de viento particular. Cabe aclarar que si bien las consideraciones num´ericas efectuadas corresponden a un viento de 18 kts, las conclusiones se verifican para la mayor´ıa de los barcos en la mayor´ıa de las condiciones de viento, variando de forma cuantitativa pero no cualitativa.

1.1.3.

Regatas de vela

Las competencias entre barcos de vela se agrupan esencialmente en dos categor´ıas. El primer tipo de competencia es lo que se conoce como “regata de marcas fijas”. Como su nombre lo indica, el objetivo de los participantes es recorrer un circuito que se encuentra establecido por puntos cuya ubicaci´ on se conoce previamente a la largada de la regata. Por ejemplo, la regata Cape Town - R´ıo de Janeiro une las dos ciudades que le dan su nombre, y el objetivo de los competidores es llegar de una a la otra. Dentro de esta categor´ıa caen todas las regatas de larga distancia y muchas regatas costeras. El segundo tipo se denomina “regata entre boyas” y se disputa en un circuito fijado expresamente para tal fin mediante la colocaci´ on de boyas u otro tipo de marcas, por lo general flotantes. La diferencia principal es que dichas marcas se establecen en posiciones que var´ıan en funci´on de las condiciones meteorol´ ogicas. La idea es que los barcos se vean obligados a navegar en rumbos particulares respecto del viento reinante, en lugar de hacerlo en rumbos determinados por la posici´ on de marcas fijas. Dentro de esta categor´ıa est´an todas las competencias ol´ımpicas, y en general la gran mayor´ıa de las de corta distancia. Algunos recorridos t´ıpicos que se plantean en este tipo de regatas son: Barlovento - Sotavento5 : Las embarcaciones navegan primero en direcci´on opuesta al viento y luego en la direcci´ on del mismo, por alguna cantidad de “vueltas” alrededor de las boyas (por lo general 2 o 3 veces). Tri´ angulo Ol´ımpico: Las embarcaciones navegan primero a barlovento, luego dos tramos (“piernas”) con el viento incidiendo sobre ellas a unos 135o , luego nuevamente a barlovento, sotavento y nuevamente barlovento para terminar. La Figura 1.8 ejemplifica la disposici´on de las marcas (boyas y lanchas) que determinan el recorrido de una regata tipo Barlovento - Sotavento de 4 tramos en dos condiciones de viento diferentes. Los organizadores de la regata son responsables de colocar las marcas de forma tan precisa como les sea posible, aunque las condiciones meteorol´ogicas adversas o cambiantes pueden dificultar la tarea. 4 El

concepto de vmg se detalla en la Figura 2.2 denomina barlovento a la direcci´ on desde la que proviene el viento, y sotavento a la direcci´ on en la que ´ este se dirige. El concepto es an´ alogo al de “r´ıo arriba” y “r´ıo abajo”, solo que respecto de la corriente de aire. 5 Se

Mart´ınez, Sainz–Tr´ apaga

P´agina 10 de 82

N

(a) Con viento del Norte

N

(b) Con viento del Sudeste

Figura 1.8: Regata Barlovento - Sotavento de 4 piernas en distintas condiciones de viento 1.1.3.1.

¿C´ omo se gana una regata?

En una regata de primer nivel, los participantes necesitan combinar una serie de cualidades para poder lograr buenos resultados. En primer lugar, el requisito m´ as evidente es tener un barco r´ apido. Sin embargo, en qu´e consiste un barco r´ apido depende fuertemente de la competencia. En una regata con un sistema de handicap (como se describi´ o en 1.1.2.2), es vital que la f´ormula de c´alculo no sobrestime la velocidad del barco, ya que esto implicar´ıa una penalizaci´on. En una regata de monotipos (barcos id´enticos), es importante que dentro de los l´ımites del reglamento la embarcaci´on sea tan r´apida como sea posible. A su vez, las velas deber´ıan tener formas muy eficientes, y el conjunto deber´ıa ser tan liviano como se permita. Este es trabajo del dise˜ nador y del armador del barco. Por otro lado, la tripulaci´ on debe utilizar los ajustes disponibles a bordo para obtener la configuraci´on ´optima de las velas y del aparejo para lograr la mayor velocidad. En segunda instancia, la tripulaci´ on debe ser capaz de maniobrar eficientemente, realizando tareas tales como viradas, giros alrededor de boyas y cambios de velas en el menor tiempo posible y minimizando la p´erdida de rendimiento del barco durante las mismas. Para lograr esto ser´ a necesario un entrenamiento completo, puesto que la coordinaci´on resulta tan fundamental como la aptitud f´ısica. En tercer lugar, todas las situaciones problem´aticas en una regata son regidas por un extenso reglamento de competencia, as´ı como por un reglamento naval b´asico (respectivamente, el Reglamento de Regatas a Vela de la isaf y el Reglamento Internacional para la Prevenci´on de Abordajes). La aplicaci´ on de este reglamento para obtener ventajas respecto de otros barcos dentro de los l´ımites establecidos se denomina t´ actica, y es de particular importancia en las regatas de tipo match-race 6 . 6 Regata

en que s´ olo participan dos embarcaciones

Mart´ınez, Sainz–Tr´ apaga

P´agina 11 de 82

Por u ´ltimo, la estrategia es fundamental. Se entiende por estrategia a la toma de decisiones sobre el recorrido que debe realizar el barco para completar la regata en el menor tiempo posible. Como se advirti´ o anteriormente, en la gran mayor´ıa de las regatas las rutas directas entre las marcas no son ´ optimas o no son factibles. Si a esto sumamos la naturaleza impredecible de los fen´ omenos meteorol´ ogicos que determinan el viento, se desprende que las decisiones estrat´egicas son sumamente complejas y probabil´ısticas. Involucran numerosas observaciones y estimaciones de variables muchas veces sutiles frente a condiciones cambiantes, as´ı como una buena habilidad para cuantificar y evaluar riesgos. Las aptitudes necesarias para llevar a cabo todas estas tareas provienen de ´ ambitos sumamente dis´ımiles. No en vano la navegaci´on a vela ha recibido los apodos m´ as llamativos, desde “ajedrez sobre agua” hasta, lisa y llanamente, “el deporte m´as dif´ıcil del mundo”7 . Nuestro trabajo se enfoca en el problema de la estrategia. Propondremos la aplicaci´on de t´ecnicas de optimizaci´ on combinatoria para asistir a los responsables de la toma de decisiones sobre las rutas a seguir.

1.2. 1.2.1.

Estado del arte La ventaja estrat´ egica

En una embarcaci´ on de regatas de tama˜ no suficiente, un miembro de la tripulaci´on ser´a encargado de tomar las decisiones respecto de la ruta a seguir. Dependiendo del tipo de regata, deber´an considerarse una serie de factores para realizar esta elecci´on. Por lo pronto, si las aguas a sortear presentan obst´aculos, el estratega deber´a considerarlos en su planteo. Estos obst´ aculos incluyen barcos hundidos, islas, piedras, zonas de escasa profundidad u otro tipo de escollos. En general, la informaci´on sobre los mismos se encuentra contenida en las cartas n´ auticas. Hoy por hoy, los dispositivos gps suelen incluir un plotter que puede mostrar una carta digital al usuario, as´ı como notificarlo en caso de que su ruta se aproxime a un obst´aculo. Alternativamente, se puede recurrir a una carta n´autica tradicional de papel sobre la que se traza la ruta de la embarcaci´ on. Estos aspectos son relevantes tanto en la navegaci´on de regata como cuando se realiza una traves´ıa. Sea cual sea el prop´ osito de la navegaci´on, todo barco debe lograr sortear los obst´aculos que encuentra en su camino sirvi´endose de la cartograf´ıa y las boyas de se˜ nalizaci´on que pudiera encontrar. El manejo de este tipo de elementos es requisito para la obtenci´on de la habilitaci´on pertinente, as´ı como aprender a respetar las se˜ nales de tr´ansito es necesario para obtener un permiso de conducir. Sin embargo, un estratega que desea ganar una regata debe considerar cuestiones mucho m´as sutiles. Como se mencion´ o antes, la variabilidad propia del viento, en conjunto con la gran incidencia que tiene este u ´ltimo sobre la velocidad del barco, resulta de vital importancia al momento de planear una ruta de navegaci´ on. Examinemos las situaciones presentadas en la Figura 1.9. En ambos casos se trata de dos embarcaciones id´enticas navegando en direcci´on contraria a la del viento, y teniendo que recurrir 7 Seguramente

el autor de esta caracterizaci´ on era un eximio navegante.

Mart´ınez, Sainz–Tr´ apaga

(a) Con viento constante

P´agina 12 de 82

(b) Con viento “curvo”

Figura 1.9: Rutas alternativas en una navegaci´on hacia barlovento por ende a una bordejeada. Como se observa en la Figura 1.9a, en condiciones de viento constante (tanto en el espacio como en el tiempo), dos embarcaciones que navegan en direcciones sim´etricas desde la l´ınea de partida no logran ventajas entre s´ı a pesar de haber recorrido rutas sustancialmente distintas. Por supuesto, esto est´ a supeditado a que ambas utilicen los rumbos de m´aximo vmg hacia barlovento como se describi´ o en 1.1.2.2. Por otra parte, en la Figura 1.9b se observa una situaci´on conocida como “viento curvo”, en la que la direcci´ on del viento var´ıa seg´ un la posici´on dentro de la cancha de regatas. Esta situaci´on puede producirse en una variedad de escenarios. El m´as simple es la proximidad de la costa o de alg´ un otro obst´ aculo cuya presencia afecta la direcci´on del viento, pero vientos de origen t´ermico8 suelen presentar tambi´en esta caracter´ıstica en proximidades de la costa. Dado que los veleros mantienen un ´ angulo constante respecto del viento (el que les proporciona un mayor vmg), sus trayectorias resultan tambi´en curvas, y de esta curvatura una de las embarcaciones obtiene un beneficio sustancial, posicion´ andose por delante de la otra. Existe una tercera situaci´ on9 , que corresponde a una variaci´on del viento ya no en el espacio sino en el tiempo. Si cuando los veleros se encuentran en la mitad de la navegaci´on el viento cambia su direcci´ on en toda la extensi´ on de la cancha de regatas, por el hecho de estar en posiciones diferentes uno de ellos se ver´ a aventajado sobre el otro. Algo similar ocurre con la intensidad del viento, que puede variar tanto en el tiempo como en el espacio.

1.2.2.

Herramientas existentes

Como se vi´ o en el apartado anterior, se puede obtener una ventaja (en muchos casos decisiva) si se logran predecir correctamente los cambios en las condiciones meteorol´ogicas. En particular, para cada ubicaci´ on dentro de una cancha de regatas durante el lapso en que transcurra la competencia, 8 Los

vientos t´ ermicos son los que se originan por la circulaci´ on convectiva del aire causada por una diferencia de temperatura entre superficies contiguas, por lo general el mar y su costa lindante. La “brisa de mar” que se observa regularmente en las playas es de este tipo. Este fen´ omeno se explica con mayor detalle en 1.2.3.1. 9 Esta situaci´ on es posiblemente la m´ as com´ un de las tres, pero resulta la m´ as dif´ıcil de representar en papel.

Mart´ınez, Sainz–Tr´ apaga

P´agina 13 de 82

deben considerarse tres factores: La intensidad y la direcci´ on del viento La intensidad y la direcci´ on de la corriente El tama˜ no del oleaje A partir de una predicci´ on fiable de estos tres par´ametros, con la ayuda de un vpp pueden obtenerse las velocidades de una embarcaci´on a lo largo de una ruta, y con ellas, el tiempo necesario para recorrerla. M´ as a´ un, teniendo la forma de establecer el costo de una ruta (lo que en nuestra ´ area de inter´es corresponde al tiempo necesario para recorrerla), con el tiempo de c´omputo suficiente puede obtenerse una ruta ´ optima para las condiciones previstas. Si bien esto presenta una utilidad evidente en regatas, el desarrollo de aplicaciones de ruteo meteorol´ogico (“weather routing”) comenz´ o por el transporte de cargas. Los buques de carga, a pesar de no ser propulsados por el viento, se ven afectados de todos modos por las condiciones meteorol´ ogicas que encuentran en sus rutas. El impacto de las olas puede, en funci´ on de su tama˜ no, disminuir la velocidad de los barcos o poner en juego su estabilidad. La integridad estructural de los sistemas de sujeci´on de carga tambi´en se exige m´as en condiciones de mar agitado. Estos factores tienen una incidencia medible sobre la duraci´on de los trayectos, los consumos de combustible y las probabilidades de falla mec´anica o estructural de los buques. En el contexto de una flota grande, los costos se amplifican y realizar una optimizaci´on de rutas se vuelve conveniente, si no necesario para competir en un mercado global.

(a) Navegaci´ on con marejada

(b) Da˜ nos a la carga

Figura 1.10: Efectos de las condiciones meteorol´ogicas sobre buques a motor En los inicios de estas tecnolog´ıas, las rutas se optimizaban en una oficina especialmente dispuesta en tierra para tal fin, que ten´ıa acceso al poder de c´omputo requerido y a la informaci´on meteorol´ ogica pertinente. Stoter argument´o que esta tarea deb´ıa, en la medida de lo posible, realizarse a bordo puesto que los tradeoffs involucrados en las decisiones de ruteo solo pod´ıan ser evaluados adecuadamente por el comandante de la embarcaci´on [32]. Hoy por hoy, la tecnolog´ıa inform´ atica hizo de esta propuesta una realidad, y la herramienta se transfiri´o a las embarcaciones de vela en competencia, as´ı como m´ as adelante a las de placer. Actualmente una embarcaci´ on que compite en regatas de larga distancia de buen nivel utiliza necesariamente un software de optimizaci´on de rutas que se alimenta de modelos meteorol´ogicos de diferentes escalas. El Global Forecast System (gfs) que ejecuta diariamente la National Oceanic and Atmospheric Administration (noaa) provee un pron´ostico de hasta 16 d´ıas de anticipaci´on.

Mart´ınez, Sainz–Tr´ apaga

P´agina 14 de 82

El modelo que utiliza gfs subdivide la superficie del globo en una ret´ıcula de 35 Km de lado, y su atm´ osfera en 64 capas verticales, de las que predice la evoluci´on cada 3 horas para las primeras 180 horas, y luego cada 12 horas hasta completar los 16 d´ıas. De toda esta informaci´on, las capas de menor altura son las que resultan de inter´es para un navegante. El pron´ ostico del que se sirve un software de optimizaci´on de rutas se carga generalmente de una versi´ on resumida de la salida de gfs, en la que se consideran solamente las capas y zonas de inter´es. As´ı, se produce un archivo grib (Gridded Binary) que muestra la intensidad y direcci´on del viento para cada sector de una ret´ıcula a intervalos de tiempo discretos. Esta ret´ıcula corresponde a una ubicaci´ on geogr´ afica particular, as´ı como a un momento dado.

Figura 1.11: Datos de viento del modelo gfs para parte del Atl´antico Sur

Armado de este pron´ ostico y de una predicci´on de performance del barco en cuesti´on, un software de optimizaci´ on de rutas puede calcular una ruta ´optima para la embarcaci´on. Productos comerciales que realizan esta tarea y est´ an orientados a competencias de veleros son Expedition[33], Deckman[4] y Adrena[1], utilizados por numerosos competidores.

1.2.3.

Limitaciones caracter´ısticas

Cualquier modelo meteorol´ ogico tiene una limitaci´on inherente: sus predicciones son, como mucho, una buena aproximaci´ on. Por esta raz´on, la utilidad de las herramientas inform´aticas

Mart´ınez, Sainz–Tr´ apaga

P´agina 15 de 82

est´ a relacionada directamente con la capacidad de las mismas de obtener resultados valiosos, que a su vez depende en gran medida de la calidad de los pron´osticos. El problema es grave en la medida en que los criterios de optimalidad utilizados para la selecci´on de rutas, as´ı como los m´etodos utilizados, no tienen en cuenta ninguna noci´on de riesgo frente a cambios inesperados en el pron´ ostico. La naturaleza discreta de las t´ecnicas empeora a´ un m´as la situaci´ on. As´ı, un cambio menor en las condiciones meteorol´ogicas puede tener consecuencias muy graves sobre el costo total de la ruta utilizada. Es posible realizar optimizaciones robustas frente a estas discrepancias entre las predicciones y la realidad. La aplicaci´ on de t´ecnicas de optimizaci´on estoc´astica a ruteo de embarcaciones fue abordada por Philpott y Mason en [25], pero no tenemos conocimiento de que este tipo de algoritmos se utilice en ning´ un software comercial.

1.2.3.1.

Distintas escalas de optimizaci´ on

Sin embargo, existe una problem´ atica fundamental con el ruteo basado en pron´osticos. De los factores meteorol´ ogicos de inter´es para el c´alculo de rutas, la intensidad y direcci´on del viento son sin duda los m´ as importantes. Deteng´ amonos un momento sobre ´este. El viento se desarrolla a escala global por la existencia y desplazamiento de centros de alta y baja presi´ on (lo que se conoce como viento de escala sin´ optica), y a escala local por fen´omenos t´ermicos costeros o bien por la formaci´on de nubes de tormenta localizadas. Si bien modelos de circulaci´ on global como gfs pueden predecir de forma bastante certera los vientos sin´opticos con varios d´ıas de anticipaci´ on, los fen´ omenos costeros son mucho m´as complejos y dependientes de sutilezas geogr´ aficas.

(a) Convecci´ on en una ciudad costera

(b) Brisa de mar resultante

Figura 1.12: Formaci´on de una brisa de mar La “brisa de mar” caracter´ıstica de ciudades costeras se origina por el calentamiento de un suelo de baja capacidad t´ermica (como el hormig´on) que alimenta un proceso convectivo. Este proceso se ilustra en la Figura 1.12. Vientos de estas caracter´ısticas no se observan en las predicciones de los modelos globales como gfs ya que dependen de cuestiones muy espec´ıficas de la zona (como

Mart´ınez, Sainz–Tr´ apaga

P´agina 16 de 82

por ejemplo, la composici´ on de los suelos costeros y el nivel de radiaci´on solar recibido cada hora), que no son tenidas en cuenta. Existen modelos m´ as detallados que pueden realizar este tipo de predicciones para algunas regiones del mundo. Algunas regatas de gran convocatoria producen una demanda suficiente para pron´ osticos de alta resoluci´ on de las ´ areas a recorrer. No obstante, la gran mayor´ıa de los modelos de circulaci´ on atmosf´erica para predicci´on de vientos consideran al viento de superficie como una condici´ on de borde compleja y se abstienen de modelarlo. Por supuesto, la din´ amica compleja del aire en superficie resulta a su vez inmanejable computacionalmente incluso para modelos regionales o de menor escala. M´as a´ un, el viento superficial en el que los veleros se desplazan presenta caracter´ısticas como r´afagas o peque˜ nas variaciones de direcci´ on, que se originan en fen´ omenos de turbulencia en la circulaci´on del aire. A´ un si se dispusiera del poder de c´ omputo suficiente, los fen´omenos turbulentos son inherentemente impredecibles. Esto no invalida de ning´ un modo la utilizaci´on de modelos num´ericos de pron´ostico meteorol´ ogico como punto de partida para la optimizaci´on de rutas. No hay m´as que observar el historial de resultados obtenidos por navegantes que utilizaron este tipo de herramientas en regatas de largo aliento para probar su efectividad pr´actica. Sin embargo, la utilidad de este tipo de herramientas disminuye a medida que las competencias son de menor distancia, ya que los fen´omenos meteorol´ ogicos que las dominan ser´ an de menor escala y por lo tanto, menos predecibles. As´ı, un software de optimizaci´ on de rutas basado en pron´osticos es indispensable para el navegante oce´ anico, u ´til para quien compite en regatas costeras de media distancia, y no se utiliza jam´ as en regatas entre boyas como las de la Figura 1.8. Esto no responde u ´nicamente a problemas de capacidad de c´ omputo: las estrategias a utilizar para ganar una regata de 2 horas no son las mismas que para una regata de 30 d´ıas. En una regata de algunas horas, ser´an los navegantes que mejor reaccionen a los cambios de viento que perciban en su barco los que puedan tomar ventaja sobre el resto. En una regata oce´ anica, la mayor´ıa de las veces ser´ a una decisi´on de ruteo la que condicione el resultado (por ejemplo, navegar por el sur o el norte de una isla a sortear). Es f´acil trazar un paralelismo con una situaci´ on m´ as estudiada de estrategias frente a incertidumbre: las inversiones en mercados financieros. Las regatas de larga distancia funcionan como las inversiones a largo plazo. En base a una estimaci´on m´as o menos formal de las fluctuaciones que espera que se produzcan, un inversor puede comprar acciones que espera que tengan una tendencia alcista por un per´ıodo extenso. Por ejemplo, quien conf´ıe en la pol´ıtica de desarrollo industrial de Brasil podr´ a comprar un paquete accionario con activos en industrias de ese pa´ıs, con la intenci´on de conservarlas por varios a˜ nos. Las regatas entre boyas funcionan como inversiones a corto plazo (lo que en finanzas se conoce como micro trading). En estas situaciones, los inversores siguen muy de cerca las tendencias de sus acciones, comprando cuando consideran que se alcanz´ o un m´ınimo, y vendiendo cuan-

Figura 1.13: Cotizaci´on accionaria

Mart´ınez, Sainz–Tr´ apaga

P´agina 17 de 82

do consideran que se alcanz´ o un m´ aximo. El intervalo sobre el que se consideran estos m´aximos y m´ınimos depender´ a de cada inversor y de su afici´on o aversi´on al riesgo. Este tipo de fluctuaci´on es inherentemente impredecible: los vencedores son los que reaccionan m´as r´apido, raz´on por la que este tipo de trading se lleva a cabo generalmente de forma autom´atica. Por ejemplo, si bien la cotizaci´ on accionaria en la Figura 1.13 denota una tendencia global a la baja (flecha roja), hay varios intervalos de crecimiento a lo largo del per´ıodo. Qui´en compre y venda durante el per´ıodo abarcado por la flecha verde podr´a obtener un beneficio de esa inversi´on. Los dos tipos de inversi´ on descriptos no se diferencian solo por su escala temporal: las estrategias a utilizar son esencialmente distintas. Lo mismo ocurre con las rutas a utilizar en regatas. Esto no significa que una variaci´ on de escala sin´optica no pueda inclinar la balanza en una regata de corta distancia, ni que una competencia oce´ anica no pueda ganarse por peque˜ nos borneos10 : simplemente no es lo que ocurre en la enorme mayor´ıa de los casos. En funci´ on de esta limitaci´ on de los modelos tradicionales para optimizar estrategias en regatas de corta distancia, pr´ acticamente todos los modelos de optimizaci´on est´an orientados a grandes distancias. Por esta raz´ on, desprecian sistem´aticamente el costo de las viradas, que en regatas de corta distancia puede ser significativo.

1.2.3.2.

El agua

Nos enfocamos hasta aqu´ı en c´ omo el viento afecta a las embarcaciones en su navegaci´on. La corriente que pueda existir en el agua navegada puede resultar del mismo modo un factor determinante, as´ı como las olas que se produzcan. En esencia, la corriente puede ser modelada de forma an´aloga al viento y contemplada a su vez por los algoritmos de ruteo. En muchos casos la corriente tiene su origen en mareas meteorol´ogicas o astron´omicas. En general, ambos tipos de marea pueden predecirse con mayor precisi´on que el viento. Al igual que en el caso de este u ´ltimo, existen pron´osticos comerciales de alta resoluci´on para zonas de inter´es particular.

Figura 1.14: Pron´ ostico de corriente

Las olas, a su vez, pueden deducirse con bastante confiabilidad a partir de informaci´on de viento, corrientes y caracter´ısticas del lugar a analizar (como por ejemplo, la profundidad del espejo de agua).

Nos conformaremos en este punto con aclarar que la corriente deber´a necesariamente ser tenida en cuenta para realizar un modelo apropiado de optimizaci´on de rutas. Veremos m´as adelante c´omo se encar´ o este problema. 10 Borneo:

variaci´ on en la direcci´ on del viento

Mart´ınez, Sainz–Tr´ apaga

1.3.

P´agina 18 de 82

Resumen del trabajo

El objetivo de nuestro trabajo es desarrollar t´ecnicas que ayuden al estratega a cargo de una embarcaci´ on a tomar decisiones apropiadas cuando las situaciones no son aptas para la optimizaci´on basada en pron´ osticos, en particular regatas costeras de corta duraci´on. As´ı, nos proponemos ayudar a los regatistas a tomar decisiones m´ as informadas en cuanto a las rutas que deben utilizar, a partir del an´ alisis en tiempo real de la informaci´on de los instrumentos del barco. Los m´etodos obtenidos ser´ an necesariamente heur´ısticos: la informaci´on inherentemente incompleta que el navegante puede obtener proviene de los instrumentos de su embarcaci´on, y no incluye datos meteorol´ ogicos m´ as que sobre el punto en que se encuentra el barco, tanto en el tiempo como en el espacio. Para ello, construimos en primer lugar un modelo como los incluidos en los paquetes comerciales, con la sofisticaci´ on adicional de que permite contemplar los costos de las viradas (como fuera aclarado en su momento, en regatas de corta distancia ´estos no son despreciables). El mismo nos sirve de benchmark para evaluar nuestras heur´ısticas. A continuaci´ on, desarrollamos una serie de heur´ısticas basadas en un relevamiento de la literatura no acad´emica, un trabajo de campo en contacto con estrategas que compiten regularmente en regatas de corta distancia y la experiencia previa con la que contamos. Las mismas pueden compararse contra los resultados ´ optimos obtenidos por el modelo de optimizaci´on, con la salvedad de que estas u ´ltimas no tienen a su disposici´on la informaci´on completa sino u ´nicamente la del lugar donde se encuentran. Por u ´ltimo, desarrollamos un generador de escenarios simulados para realizar las pruebas de nuestras heur´ısticas en condiciones veros´ımiles, dada la imposibilidad pr´actica de realizar mediciones en un entorno real. Para ello entrevistamos a un experto local en meteorolog´ıa de peque˜ na escala aplicada a regatas. Gracias a las simulaciones realizadas, pudimos optimizar los par´ametros de nuestras heur´ısticas y evaluar su rendimiento en comparaci´ on con las rutas ´optimas. Logramos obtener resultados muy alentadores utilizando informaci´ on incompleta. Esta tesis se organiza de la siguiente manera: El Cap´ıtulo 1 es esta introducci´ on, que pretende establer los conceptos b´asicos de navegaci´on a vela y de la competencia en regatas, as´ı como las posibles ventajas de utilizar un sistema de estrategia computacional, y las limitaciones de los productos existentes. El Cap´ıtulo 2 ahonda en el modelo de grafos que planteamos para el problema de optimizaci´on de rutas de veleros, incluyendo particularidades como el c´alculo de los costos de navegaci´on en distintas condiciones de viento y corriente. El Cap´ıtulo 3 describe la construcci´on de un algoritmo eficiente de caminos m´ınimos para el c´ alculo de rutas ´ optimas en el modelo descripto previamente, bajo la hip´otesis de que se conoce toda la informaci´ on meteorol´ogica de la situaci´on que se desea analizar. El Cap´ıtulo 4 motiva y describe una serie de heur´ısticas que propusimos a partir del an´alisis del problema, el conocimiento del dominio y la discusi´on con navegantes experimentados.

Mart´ınez, Sainz–Tr´ apaga

P´agina 19 de 82

El Cap´ıtulo 5 detalla el modelo experimental de simulaci´on que construimos para generar escenarios donde ejecutar nuestros algoritmos, as´ı como los resultados de los experimentos realizados a partir de estos u ´ltimos. El Cap´ıtulo 6 corresponde a las conclusiones, donde se detallan adem´as investigaciones que podr´ıan realizarse en el futuro.

Mart´ınez, Sainz–Tr´ apaga

P´agina 20 de 82

Cap´ıtulo 2

El modelo 2.1.

La predicci´ on de velocidad

Antes de plantear un modelo capaz de optimizar las rutas para una embarcaci´on, es necesario establecer de qu´e manera se proceder´ a para predecir la velocidad de un barco en condiciones dadas. C´ omo se discuti´ o en la Secci´ on 1.1.2.2, un vpp entrega la predicci´on de performance de una embarcaci´ on en forma de un conjunto de curvas polares caracter´ısticas como la de la Figura 1.7. Dichas curvas polares son a su vez resumidas en forma de una tabla con algunos valores significativos que deben ser interpolados en software para obtener datos completos. Como vimos anteriormente, de la lectura directa de la curva polar para una intensidad de viento determinada, se desprende la velocidad que se espera del barco en esa condici´on. As´ı, en la Figura 2.1a se observa como se interpreta la curva polar: representa la isocrona 11 para un tiempo de una hora.

0º

0º

45º

2

4

6

8

(a) Velocidad

10

45º

12

90º

2

4

6

8

10

12

90º

(b) Velocity Made Good to Course

Figura 2.1: M´etricas alternativas de velocidad

Asimismo, hay otras dos nociones de velocidad que resultan particularmente relevantes para la navegaci´ on a vela y que se derivan de la caracterizaci´on anterior. La primera es el concepto conocido como Velocity Made Good to Course (vmc) que corresponde a maximizar la proyecci´on del vector velocidad del barco sobre la direcci´on deseada. Esta u ´ltima m´etrica corresponde a la Figura 2.1b. La segunda es la llamada Velocity Made Good (vmg) que mencionamos en la Secci´on 1.1.2.2. El 11 Curva que une todos los puntos alcanzables en un intervalo de tiempo dado. Corresponde a la curva de nivel de la funci´ on “m´ınimo tiempo necesario para alcanzar el punto P ”.

Mart´ınez, Sainz–Tr´ apaga

P´agina 21 de 82

vmg es la velocidad que puede desarrollar una embarcaci´on en una direcci´on dada, con la relajaci´on adicional de que no necesariamente debe navegar en l´ınea recta. As´ı, el barco tiene la posibilidad de bordejear, y el vmg es la velocidad resultante de dicha bordejeada. El vmg est´a dado por la frontera de la c´ apsula convexa del conjunto delimitado por la curva polar [26]. La Figura 2.2 ilustra este concepto. En nuestra implementaci´ on, utilizamos curvas polares de referencia producidas por el vpp de ims [21], que se encuentran disponibles en forma de tabla con las velocidades esperadas para varios ´ angulos de navegaci´ on respecto del viento, y para varias intensidades de este u ´ltimo. Estos valores son interpolados linealmente para tener mayor precisi´ on en las predicciones.

2

4

6

8

10

135º

2.1.1.

Velocidad bajo corriente

Se denomina “corriente” al movimiento del agua en que el barco se desplaza. Como se discuti´o hasta el momento, la estimaci´ on de la velocidad de un velero bajo condiciones dadas de viento, incluso sin corriente, es un tema complejo. Sin embargo, resulta a priori muy simple estimar la velocidad de un velero que es u ´nicamente arrastrado por la corriente: su velocidad es precisamente la de esta u ´ltima, tanto en direcci´ on como en intensidad. Al igual que el viento, la corriente puede modelarse apropiadamente con un vector que la represente. Una simple suma de vectores permite entonces aproximar la posici´ on esperada de una embarcaci´ on tras un cierto per´ıodo de tiempo sometida a una corriente.

180º

Figura 2.2: Velocity Made Good

B'

B

El problema primordial con esta caracterizaci´on es que no responde a la pregunta que es pertinente para nuestro modelo: ¿Dados un viento y una corA riente constantes, qu´e tiempo le insume a un barco navegar desde un punto A hasta un punto B? Efectivamente, la suma vectorial s´ olo nos indica donde estar´ a un barco que en ausencia de corriente habr´ıa alcanzado un punto dado en cierta cantidad de tiemFigura 2.3: Impacto de la corriente po. Esto corresponde a la situaci´ on de la Figura 2.3, donde la corriente desplaza a un barco que normalmente hubiera llegado de A a B hacia un tercer punto B’. M´ as a´ un: este modelo no es m´ as que una aproximaci´on porque presupone que la velocidad que confieren a la embarcaci´ on el viento y la corriente son estrictamente independientes. Lamentablemente, esta suposici´ on no es correcta. En todo nuestro trabajo, consideramos que tanto viento como corriente son medidos desde un punto de referencia fijo a la tierra o al fondo de un espejo de agua de inter´es. Sin embargo, el viento que percibe una embarcaci´on que navega puede ser sus-

Mart´ınez, Sainz–Tr´ apaga

P´agina 22 de 82

tancialmente distinto, ya que es necesario adem´as tomar en cuenta la velocidad del propio barco. El viento medido por un anem´ ometro12 de a bordo se denomina viento aparente (VA ), y puede ser significativamente distinto de aquel que se mide desde un punto de referencia fijo (el llamado viento real VR ), tanto en direcci´ on como en intensidad. La Figura 2.4 ilustra la diferencia que existe entre viento real (en verde) y viento aparente (en azul). El viento aparente VA es el que capturan los instrumentos del barco. A su vez, el ´angulo α es el ´angulo de incidencia del viento sobre el barco que debe utilizarse como entrada para consultar la velocidad esperada en las curvas polares caracter´ısticas.

Figura 2.4: Viento aparente

Figura 2.5: Viento de navegaci´ on

12 Instrumento

Asimismo, dado que la corriente afecta la velocidad de navegaci´on del barco, modifica a su vez la direcci´on e intensidad del viento en el que ´este navega. As´ı, un barco que se encuentra en un d´ıa de ausencia total de viento sobre un canal cuya corriente es de 5 kt percibir´a un viento de velocidad igual a la de la corriente, y direcci´on exactamente opuesta13 . Por lo tanto, si se desea utilizar la predicci´on polar de velocidad de un barco, ser´a necesario antes de consultar la curva corregir tanto la velocidad como la intensidad del viento que percibe ´este, as´ı como adicionar la velocidad que le imprime la corriente a la embarcaci´on de forma directa. Este nuevo viento corregido corresponde a una medici´on hecha desde un punto de referencia que se encuentra a la deriva (es arrastrado por la corriente), y es mencionado en pocas oportunidades por la literatura n´autica. Suponemos que esta omisi´on se debe al hecho de que en contextos t´ıpicos, la informaci´on de viento que se utiliza a bordo proviene de los instrumentos del barco, y por lo tanto ya incluye la modificaci´on que se produce por causa de la corriente. Sin embargo, en el contexto de ruteo ´optimo trabajaremos con un sistema de referencia fijo en la superficie terrestre, y por lo tanto nos resultar´a necesaria la diferenciaci´on. Rushall llama a este viento sailing wind [29], traduciremos esta nomenclatura como viento de navegaci´ on (VN ).

que mide la velocidad del viento. es una nueva simplificaci´ on, puesto que presupone que la fricci´ on entre el agua y el aire es despreciable, pero es una aproximaci´ on razonable. 13 Esto

Mart´ınez, Sainz–Tr´ apaga

P´agina 23 de 82

La Figura 2.5 ilustra el viento de navegaci´on VN y su derivaci´on, a saber VN = VR − C. A su vez, este cambio de viento afecta el ´ angulo de incidencia del viento sobre la embarcaci´on, y ahora debe utilizarse α0 en lugar de α como dato de consulta para predicci´on de velocidad de las curvas polares. Como mencionamos antes, la raz´ on primordial de tener en cuenta la corriente es poder predecir con exactitud cu´ al es el menor tiempo que insume el barco de inter´es para navegar entre dos puntos A y B de coordenadas conocidas bajo condiciones meteorol´ogicas homog´eneas. Esta predicci´on es esencial para el modelo que presentaremos a continuaci´on. Para proveer al modelo de una predicci´on u ´til, generamos un nuevo conjunto de curvas polares que incluyen todas las variaciones introducidas por la corriente (la velocidad del barco, la velocidad del viento y la direcci´ on del viento). Para llevar a cabo esta tarea se calcula en primer lugar el viento de navegaci´ on, se obtiene la curva polar caracter´ıstica para ese viento y luego se aplica una traslaci´ on en el plano por el vector de corriente. Esta transformaci´on refleja el incremento de velocidad que la corriente proporciona al barco sobre el sistema de referencia terrestre. La traslaci´ on del pol´ıgono polar introduce un problema. Como toda funci´on polar continua, su curva representativa debe contener a un conjunto star shaped y el origen debe estar contenido en el kernel del pol´ıgono14 . Esto puede no ocurrir: bajo los efectos de la corriente, es posible que haya dos o m´as maneras diferentes de navegar en una misma direcci´on, lo cual introduce una ambig¨ uedad. Afortunadamente, las consultas a responder involucran la velocidad m´ axima que alcanza el barco en una direcci´ on dada, con lo cual en caso de haber varias opciones simplemente se considerar´a la de mayor magnitud. La Figura 2.6 exhibe la diferencia en la predicci´on de velocidad. La curva rosa corresponde a la curva entregada por el vpp, que considera u ´nicamente el viento (que en este caso sopla desde la direcci´ on 0o a 10 kts), mientras que la de color azul claro corresponde a la curva modificada por la corriente. Esta segunda curva corresponde a VN : un viento levemente m´as intenso (10.45 kts) y con una orientaci´ on algo distinta (343o ). Adem´as, la curva sufre la traslaci´on producto de la velocidad que la corriente imprime directamente al barco. En raz´on de ello, la curva polar celeste est´ a desplazada en la direcci´ on de dicha corriente. Sin embargo, al no cumplir la curva celeste con el criterio geom´etrico descripto unas l´ıneas atr´as, debe ser ajustada logrando as´ı la curva azul final. N´ otese que en presencia de corriente sustancial, la caracterizaci´on nos indica que la embarcaci´on es capaz de navegar directamente en la direcci´on opuesta a VR , sin necesidad de bordejear. Sin embargo, no podr´ a hacerlo directamente en contra de VN , que es el que se percibe sobre el agua. Provistos de esta caracterizaci´ on adaptada, disponemos entonces de una predicci´on apropiada de la velocidad del barco en cualquier direcci´on bajo condiciones homog´eneas de viento y corriente, lo cual nos servir´ a de punto de partida para nuestro modelo. 14 Un conjunto S es star shaped si en ´ el existe un punto P tal que para todo punto Q dentro del conjunto, el segmento que une P y Q est´ a contenido en el conjunto. El kernel de S es el conjunto S ∗ ⊆ S de todos los puntos P que verifican esto u ´ ltimo.

Mart´ınez, Sainz–Tr´ apaga

P´agina 24 de 82

10 kts de viento, sin corriente 10 kts de viento, 3 kts de corriente (trasladado) 10 kts de viento, 3 kts de corriente (final)

0° 14 12

315°

45° 10 8 6 4 2

270°

90°

225°

135°

180°

Figura 2.6: Predicciones de velocidad de un Farr 36 con 10 nudos de viento

Mart´ınez, Sainz–Tr´ apaga

2.2.

P´agina 25 de 82

Modelado de la cancha

2.2.1.

El ´ area de inter´ es

En base a lo discutido anteriormente, proponemos un modelo discreto de la navegaci´on de un velero sobre un espacio de agua, con condiciones igualmente discretas de viento y corriente. As´ı, considerando intervalos de condiciones uniformes, podemos utilizar las herramientas descriptas en la secci´ on anterior para computar las velocidades esperadas del barco en cada intervalo. Luego, a partir del conocimiento de cada intervalo podremos caracterizar la navegaci´on sobre cualquier ruta. Para modelar el problema dividimos la superficie navegable en una grilla cuadrada de A × A sectores. Cada sector de dicha grilla (de aqu´ı en m´as, “cuadrante”) tiene condiciones uniformes de viento y corriente: en cualquier punto del mismo, direcci´on e intensidad tanto del viento como de la corriente son constantes. Si suponemos que cada cuadrante tiene un lado de alrededor de 50 metros, la suposici´ on resulta razonable para las velocidades e intervalos de tiempo a considerar. Discretizaciones del ´ area a navegar son discutidas en la literatura [24, 26], y se utilizan por lo general en los softwares de optimizaci´ on de rutas a gran escala. En particular, si consideramos que un velero similar al ilustrado en la Figura 1.7 se desplaza a velocidades que usualmente oscilan entre 5 y 15 kts, resulta que el tiempo esperado para recorrer una distancia de 50 metros es de entre 7 y 20 segundos. Dado que una pierna15 convencional puede insumir entre 15 y 25 minutos, y que la cuesti´on de mayor inter´es ser´a d´onde deber´an realizarse las viradas, la discretizaci´ on propuesta presenta numerosas oportunidades para llevar a cabo estas maniobras, muchas m´ as de las que se suelen utilizar en la pr´actica. Identificaremos a los cuadrantes por un par ordenado (i, j), siendo el cuadrante inferior izquierdo el que corresponde al par (0, 0), incrementando el ´ındice i hacia la derecha y el ´ındice j hacia arriba, hasta asignar el par (A, A) a la esquina superior derecha. Una vez caracterizada as´ı la superficie de agua a modelar, se podr´ an establecer puntos arbitrarios dentro de dicha ´area como origen y destinos de la ruta. Dado que la cancha no necesariamente tiene forma cuadrada, sino que puede presentar irregularidades varias (islas, zonas de baja profundidad, costa, etc.), es posible establecer cuadrantes inv´ alidos que se ven excluidos del ´ area de navegaci´on. Esto se ejemplifica en la Figura 2.7. Si bien cada cuadrante presenta condiciones homog´eneas de viento y corriente, ambos factores podr´ an cambiar a lo largo del tiempo. Para ello, consideraremos una discretizaci´on de esta tercera dimensi´ on, por lo que consideraremos al viento como una funci´on Viento: (N≤A × N≤A × R>0 ) → (R × R). Consideraremos que tanto la intensidad como la direcci´on del viento cambian a intervalos discretos, de modo que entre dos momentos de cambio dados, el viento en un cuadrante ser´a constante. Es decir, existe un conjunto T de tiempos {t0 = 0, t1 , ...., tn , tn+1 = ∞}, tal que en el intervalo [ti , ti+1 ) el viento no var´ıa. Esto corresponde a decir que para cada t dentro del intervalo estudiado, el viento solo depende del cuadrante de la cancha. M´as formalmente: ∀t, i, j/tk ≤ t < tk+1 , V iento(i, j, t) = V iento(i, j, tk ) 15 Pierna:

tramo del recorrido de una regata

Mart´ınez, Sainz–Tr´ apaga

(a) Cancha de regatas

P´agina 26 de 82

(b) Cuadrantes asociados para A = 10

Figura 2.7: Discretizaci´ on en cuadrantes para una regata en Punta del Este La corriente se considerar´ a de forma an´aloga al viento, ya que como se discuti´o en la Secci´on 2.1.1, puede ser modelada con un vector en R2 . Si bien utilizaremos una discretizaci´on del plano id´entica tanto para corrientes como para vientos, no es necesario que los intervalos temporales de cambio de viento y de corriente sean compatibles. Esta situaci´on puede resolverse f´acilmente modificando los intervalos y obteniendo as´ı funciones de viento y corriente id´enticas a las originales pero cuyos intervalos de cambio s´ı son compatibles entre s´ı.

2.2.2.

El grafo de rutas

Dado que nuestro objetivo al modelar la cancha es evaluar los costos de navegaci´on de un velero sobre la misma para luego poder optimizar su ruta, asociaremos a la discretizaci´on descripta en la secci´ on anterior un grafo dirigido. Cada nodo del grafo tendr´a asociada una posici´on en el plano considerado, y los costos de los arcos corresponder´an al tiempo que le insume al velero navegar entre esas dos posiciones. Adem´ as, se restringen las posiciones de los nodos a los contornos de los cuadrantes. En principio, dado que las condiciones dentro de cada cuadrante son homog´eneas, esta restricci´on resulta razonable. As´ı, se considera un tercer par´ametro n para el modelo que establece cu´antos nodos se disponen sobre cada lado de cada cuadrante. Por las ubicaciones de los nodos sobre los bordes de dichos cuadrantes, resulta que un mismo nodo puede hallarse en contacto con m´as de uno de ellos. Los nodos se identifican con un par ordenado (u, v), an´alogamente a lo descripto antes para los cuadrantes de la discretizaci´ on del ´ area navegable. Es importante notar que el par´ ametro establece la cantidad de nodos por lado de cada cuadrante, pero no directamente la cantidad de nodos del grafo, ya que ´esta depende de la discretizaci´ on. Dada una discretizaci´ on de la cancha en A × A cuadrantes, la cantidad de nodos total es (A + 1)(1 + A(n − 1)) + (n − 2)A(A + 1)) ∈ O(A2 n)

Mart´ınez, Sainz–Tr´ apaga

P´agina 27 de 82

Utilizaremos adem´ as dos nodos distinguidos, inicial y final, que corresponden a los puntos de partida y destino de la ruta que deseamos considerar en nuestro modelo. Los nodos del grafo hasta aqu´ı descriptos se pueden observar en la Figura 2.8. Final

Nodo (12, 12)

Nodo (0, 12)

Nodo (12, 6)

Nodo (0, 0) Nodo (9, 0) Inicial

Figura 2.8: Nodos sobre la discretizaci´on de un ´area para A = 4 y n = 4

2.2.2.1.

Las maniobras

Consideramos en una primera aproximaci´on establecer un arco entre dos nodos del mismo cuadrante si, seg´ un la caracterizaci´ on polar de la embarcaci´on, es posible navegar directamente entre ellos teniendo en cuenta el viento y la corriente reinantes dentro del cuadrante en cuesti´on. Si bien esta idea es v´ alida, un camino dentro de este grafo no modela correctamente las rutas de inter´es para nuestro trabajo ya que no involucra ning´ un costo para las viradas. Como se hab´ıa anticipado en la Secci´ on 1.2.3.1, para regatas de corta distancia el costo de las mismas no resulta despreciable, por lo que el modelo no es apropiado. Recordemos: una virada es la maniobra en la que un barco de vela cambia su direcci´on de navegaci´ on (y la orientaci´ on de sus velas) para que el viento deje de incidir por uno de los lados del barco y pase a incidir sobre el otro. Esta maniobra es la base de la bordejeada que permite a un velero navegar contra el viento, y fue presentada en la Figura 1.6. Observemos esto con mayor detalle en la Figura 2.9a.

Mart´ınez, Sainz–Tr´ apaga

P´agina 28 de 82

(a) Viradas

(b) Trasluchadas

Figura 2.9: Distintos tipos de maniobras que realizan los veleros En dicha figura los discos azules representan a la tripulaci´on de la embarcaci´on, y las l´ıneas negras a sus velas. Como se observa, ambos deben cambiar su posici´on en la embarcaci´on para adecuarse al cambio en el ´ angulo de incidencia del viento sobre la misma. Esta movilizaci´on de personas, as´ı como el tiempo en que las velas no trabajan correctamente durante la maniobra afecta negativamente la velocidad del barco. La virada ocurre cuando el velero gira de modo a presentar su parte delantera (proa) al viento y seguir su camino hasta establecerse con el viento por su otro lateral. Una segunda maniobra, la trasluchada, ocurre cuando el velero gira de modo a presentar su parte trasera (popa) al viento. En funci´ on de si las velas pasan de izquierda a derecha o viceversa, tanto viradas como trasluchadas ofrecen dos variantes sim´etricas que se observan en las figuras. En la jerga n´ autica, se dice que un barco que navega con sus velas sobre el lado izquierdo de la embarcaci´ on navega con amuras a estribor, mientras que si lo hace con sus velas sobre el lado derecho navega con amuras a babor. Por ejemplo, en la Figura 2.9a, el barco de la izquierda navega inicialmente con amuras a estribor, y luego de la virada contin´ ua con amuras a babor. An´ alogamente, en la Figura 2.9b, el barco de la izquierda navega primero con amuras a estribor y luego de la trasluchada pasa a tener amuras a babor. En resumidas cuentas, viradas y trasluchadas son maniobras que permiten a un velero cambiar de amura.

Ceñida

Popa

Amuras a estribor

Amuras a babor

Figura 2.10: Tipos de navegaci´on

Mart´ınez, Sainz–Tr´ apaga

(ce˜ nida,estribor)

P´agina 29 de 82

(ce˜ nida, babor)

(popa, babor)

(popa, estribor)

Figura 2.11: Ejemplo de arcos para un grupo de nodos hermanos seg´ un su tipo de navegaci´on Tanto viradas como trasluchadas tienen un costo temporal que se deduce de la p´erdida de velocidad que provocan. Nuestro modelo debe considerar estos costos. Planteamos entonces un refinamiento: consideramos que en cada posici´on donde antes exist´ıa un u ´nico nodo, ahora existir´an cuatro, que representan cuatro tipos de navegaci´on. Un tipo de navegaci´on se define por su amura (babor o estribor) y su “rumbo”. El rumbo, que en este caso puede ser simplemente popa o ce˜ nida 16 , no es m´ as que una categorizaci´ on de los ´angulos de incidencia del viento sobre el barco que denota si ´este navega mayormente contra el viento o a favor de ´este, como se ejemplifica en la Figura 2.10. As´ı, en cada coordenada (x, y) habr´a en el nuevo modelo cuatro nodos en lugar de uno u ´nico. Diremos que estos nodos que ocupan una misma coordenada en el plano son nodos hermanos. En este nuevo modelo, existir´ a un arco entre nodos u y v si ese arco exist´ıa en el anterior ambos nodos comparten su tipo de navegaci´ on. La Figura 2.11 ilustra la disposici´on de los arcos para nodos hermanos de los distintos tipos de navegaci´on propuestos. A su vez, se agregar´ an arcos entre nodos hermanos ilustrando las maniobras que el barco puede realizar para cambiar de un tipo de navegaci´on a otro. Esto se ilustra en la Figura 2.12. Cabe destacar que se introducen aqu´ı dos seudomaniobras llamadas “orzada” y “derivada” que sirven para garantizar la correctitud del modelo. Dichas maniobras tienen un costo artificial cuyo objetivo es garantizar que el pasaje entre dos nodos vecinos se haga por el camino directo en el grafo. Si miramos la Figura 2.10, observamos que se puede pasar de un rumbo de ce˜ nida al otro (es decir, es una ce˜ nida con amuras a estribor a una ce˜ nida con amuras a babor) realizando una virada. Sin embargo, tambi´en es posible hacerlo mediante una trasluchada, pasando primero por el rumbo de popa con amuras a estribor, haciendo una trasluchada seguida del rumbo de popa con amuras a babor, y finalmente alcanzando la ce˜ nida con amuras a babor. Este camino indirecto tiene en la pr´ actica un costo bastante superior a la de realizar la virada. Sin embargo, el costo de una trasluchada es caracter´ısticamente inferior al de una virada. De darle un peso nulo a los arcos que se bautizaron “orzada” y “derivada”, ser´ıa m´as conveniente en el grafo realizar siempre una trasluchada, lo cual no es fiel a la realidad. Se introducen entonces estas seudomaniobras que se denominan seg´ un su nombre n´ autico correspondiente.17 16 Se

denomina ce˜ nida a la configuraci´ on de una embarcaci´ on que le permite navegar contra el viento. la pr´ actica un pasaje de una popa a la ce˜ nida de la misma amura tiene efectivamente un costo, aunque por lo general se considera despreciable. Sin embargo, una sucesi´ on de cambios de rumbo s´ı tiene un costo considerable. En efecto, las penalizaciones en regatas por lo general consisten en giros de 360o o 720o . 17 En

Mart´ınez, Sainz–Tr´ apaga

P´agina 30 de 82

Virada

(Ceñida, Estribor)

(Ceñida, Babor) Virada

Orzada

Orzada

Derivada

(Popa, Estribor)

Derivada

Trasluchada

(Popa, Babor)

Trasluchada

Figura 2.12: Nodos asociados a cada tipo de navegaci´on y sus transiciones Sea angulosamurap ,rumboq = [αdesde , αhasta ) el rango de ´angulos asignado al tipo de navegaci´on (amurap , rumboq ), y sea vectorDeNavegacion(u, v) el vector correspondiente a la navegaci´on entre u y v: (u.x − v.x, u.y − v.y). Entonces, en un instante dado t, existir´a un arco entre dos nodos u y v de tipo de navegaci´ on (amurap , rumboq ) incluidos en el cuadrante (i, j) si y solo si: anguloDeIncidencia(viento(i, j, t), vectorDeNavegacion(u, v)) ∈ angulosamurap ,rumboq Aqu´ı anguloDeIncidencia es una funci´on que calcula el ´angulo entre dos vectores, en este caso el vector que modela la direcci´ on del viento y el que modela la direcci´on de navegaci´on del barco. Este ´ angulo es el ´ angulo α mencionado en la Secci´on 2.1.1. Establecimos posteriormente que la cantidad de rumbos distintos sea parametrizable, a fin de permitir discretizaciones m´ as granulares del espacio de ´angulos de navegaci´on. Esto permite en principio la reducci´ on de costos espurios causados por las seudomaniobras, ya que el costo de cada una de ellas puede ser menor. Para ello, se divide cada amura uniformemente entre la cantidad de rumbos distintos. En la Figura 2.13 se aprecia un ejemplo con 4 rumbos por amura. Las seudomaniobras deben extenderse consecuentemente para garantizar el comportamiento correcto de las maniobras como se describi´ o previamente. Como se ilustra en la Figura 2.14, el grafo resultante puede razonarse de forma tridimensional. As´ı, cada tipo de navegaci´ on puede considerarse en un plano y las maniobras conectan los distintos planos entre s´ı. Por ejemplo, una virada permite desplazarse en el grafo desde el plano asociado a (ce˜ nida, babor) al plano de (ce˜ nida, estribor). Dentro de cada plano, los arcos corresponden solo a rumbos dentro del tipo de navegaci´ on correspondiente.

Mart´ınez, Sainz–Tr´ apaga

P´agina 31 de 82

Virada

Virada

Amuras a Babor

Amuras a Estribor

Trasluchada

Trasluchada

Figura 2.13: Nodos para 4 rumbos distintos por amura

Ejes de maniobra Ejes de navegación

(Ceñida, Estribor)

(Ceñida, Babor)

(Popa, Babor)

(Popa, Estribor)

Figura 2.14: Vista tridimensional del grafo del modelo

Mart´ınez, Sainz–Tr´ apaga

2.2.2.2.

P´agina 32 de 82

C´ alculo de costos

Arcos de navegaci´ on Dado que tanto viento como corriente pueden cambiar a lo largo del tiempo, los arcos que inciden sobre un nodo tambi´en resultar´an variables. No s´olo puede modificarse su costo, sino que arcos pueden aparecer o desaparecer en funci´on de si el barco puede navegar de forma directa entre los nodos involucrados para el viento que reina en ese instante. En todo momento, el costo asociado a cada arco se corresponde con el tiempo necesario para recorrer la distancia cartesiana que separa las coordenadas asociadas a los nodos, navegando con la velocidad que predicen las curvas polares caracter´ısticas del barco, con el viento y la corriente asociados a ese cuadrante en ese instante. Consideremos u, v nodos no hermanos de un cuadrante c en el tiempo t. Sea velocidad(u, v, c, t) la velocidad predicha por la curva polar del barco para navegar en la direcci´on que une u con v en las condiciones que corresponden al cuadrante c en el instante t. Luego, el costo de navegar desde u hasta v (y por lo tanto el costo asociado al arco) se obtiene como:

Costo(u, v, c, t) =

A

 

ku−vk velocidad(u,v,c,t)

velocidad(u, v, c, t) > 0



∞

velocidad(u, v, c, t) = 0

B

Es de destacarse que el cuadrante es un par´ametro del costo, ya que dos nodos no hermanos pueden compartir m´as de un cuadrante, lo que se ilustra en la Figura 2.15. En ella se observa que todos los nodos ubicados sobre el borde de un cuadrante comparten entre s´ı los dos cuadrantes que divide dicho borde, y con ellos dos condiciones de viento y marea que eventualmente podr´ıan diferir.

Figura 2.15: Cuadrante compartido

El hecho de que dos nodos est´en unidos por dos o m´as arcos, que por estar asociados a distintos cuadrantes tengan costos diferentes, es un problema causado por la discretizaci´on. Para salvar este problema podemos redefinir la funci´ on de costo para que reduzca esos arcos a uno u ´nico, al que le corresponder´ a el costo m´ınimo de navegaci´on. As´ı, se definir´ıa de la siguiente manera:

Costo(u, v, t) =

m´ın

Costo(u, v, c, t)

c:cuadrante/u∈c∧v∈c

En el caso de dos nodos que no comparten ning´ un cuadrante se les asigna un costo infinito18 , ya que no nos interesa navegar entre ellos. Si alguno de los dos es uno de los nodos distinguidos (inicial o final ), el costo entre ellos ser´a 0 si el otro corresponde respectivamente a uno de los or´ıgenes o destinos de la ruta. 18 Por

el uso que se le va a dar al modelo, un arco de costo infinito es equivalente a la ausencia de un arco.

Mart´ınez, Sainz–Tr´ apaga

P´agina 33 de 82

Arcos de maniobra Consideremos ahora el caso de los nodos hermanos. Entre ellos, los arcos tienen un valor que representa el costo asociado a cada maniobra, que en principio es caracter´ıstico del barco y por lo tanto es un par´ ametro del modelo. Si bien nuestro modelo permite definir una cantidad arbitraria de tipos de navegaci´ on como se coment´o en la Secci´on 2.2.2.1, nosotros optamos por utilizar s´olo 4, con lo que resulta necesario especificar los par´ametros costovirada , costotrasluchada , costoderivada y costoorzada . Como se detall´ o oportunamente, los costos de las seudomaniobras deben ser tales que las maniobras directas siempre resulten menos costosas que una secuencia alternativa de varias maniobras. Se parte siempre de la base de que costovirada > costotrasluchada . Adem´as, para este caso se deber´ıa cumplir que costoderivada +costotrasluchada +costoorzada > costovirada , ya que de lo contrario nunca ser´ıa conveniente realizar una virada. Cuando se utilizan m´ as tipos de navegaci´on, dicha igualdad debe seguir siendo v´alida para obtener un modelo correcto. Una forma sencilla de obtener una asignaci´on de costos de maniobra v´ alida consiste en segmentar las seudomaniobras, distribuyendo uniformemente entre los nuevos arcos los costos originales asignados a orzada y derivada. En cualquier caso, dados dos nodos hermanos u y v definimos el costo del arco que los une como el costo de la maniobra necesaria para pasar de uno al otro, o ∞ en caso de no haber una maniobra que nos permita llegar directamente de uno al otro. Por ejemplo, no se puede pasar de un nodo de tipo (ce˜ nida,estribor) a uno de tipo (popa,babor) en una sola maniobra.

Costo(u, v) =

  costomaniobrau,v 

∞

Existe una maniobra para pasar de u a v En otro caso

Por u ´ltimo, el nodo inicial que se exhibi´o en la Figura 2.8 se conecta con los nodos cuya posici´on est´e asociada al punto de partida de la ruta a considerar con arcos de costo nulo. Si bien en muchas instancias se considerar´ a un u ´nico punto de partida, la mayor´ıa de las regatas cuentan con una l´ınea de partida. El nodo inicial permite modelar que un subconjunto cualquiera de nodos es un punto de partida v´ alido. Una situaci´ on an´aloga ocurre con una eventual l´ınea de llegada y el nodo final.

Resumen Resumiendo, la funci´ on de costos dentro del grafo de nuestro modelo resultar´ıa: Costo(u, v, t) = costomaniobrau,v si u y v son dos nodos hermanos unidos por una maniobra Costo(u, v, t) = ∞ si u y v son hermanos pero no est´an unidos por una maniobra. Costo(u, v, t) = 0 si u es el nodo inicial y v esta en la l´ınea de salida. Costo(u, v, t) = 0 si v es el nodo final y u esta en la l´ınea de llegada. Costo(u, v, t) = m´ınc:cuadrante /u∈c∧v∈c Costo(u, v, c, t) si u y v no son hermanos y comparten por lo menos un cuadrante. Costo(u, v, t) = ∞ en otro caso.

Mart´ınez, Sainz–Tr´ apaga

P´agina 34 de 82

Utilizando esta definici´ on surge que un camino dirigido entre los nodos inicial y final representa una ruta posible entre un conjunto de puntos de partida y uno de puntos de llegada, cuyo costo modela el tiempo de navegaci´ on esperado entre los mismos e incluyendo los costos insumidos en la realizaci´ on de maniobras. Veremos en el pr´oximo cap´ıtulo como implementar un algoritmo que encuentre rutas ´ optimas en este modelo.

Mart´ınez, Sainz–Tr´ apaga

P´agina 35 de 82

Cap´ıtulo 3

Algoritmo Exacto 3.1.

C´ omputo de la ruta ´ optima

El modelo presentado nos permite representar todas las rutas posibles entre los puntos de origen y destino recorriendo un ´ area navegable dada. Nos interesa entonces determinar la ruta de menor duraci´ on, que corresponde al camino m´ınimo entre el nodo inicial y el nodo final. Para ello debemos generalizar la definici´on tradicional de camino en grafos para que tenga en cuenta la variable temporal. As´ı, dado un camino X = u1 , ..., un , definimos su costo de la siguiente manera: Si X = u1 , u2 , Costo(X) = Costo(u1 , u2 , 0) Si X = u1 , ...., un n > 2, Costo(X) = Costo(X 0 ) + Costo(un−1 , un , Costo X 0 )). | {z } X0

A continuaci´ on examinaremos los algoritmos utilizados para resolver este problema.

3.1.1.

Camino m´ınimo en grafos independientes del tiempo

El problema de camino m´ınimo en grafos es un problema muy estudiado. Dado un grafo G(V, E), con una funci´ on de costoPw : V × V → R, se desea hallar el camino P entre dos nodos u ∈ V y v ∈ V que minimiza on single-source single-destination (ui ,uj )∈P W (ui , uj ). Esta es la versi´ (origen y destino u ´nicos), pero existen otras variantes, como por ejemplo buscar los caminos m´as cortos entre todo par de nodos de G. Si w es tal que w(ui , uj ) ≥ 0 se puede resolver el problema mediante el algoritmo de Dijkstra [5]. Dicho procedimiento se ilustra en el Algoritmo 3.1. Este algoritmo puede implementarse con una complejidad O(|E| + |V | ∗ log(|V |)) utilizando una cola de prioridad implementada sobre Fibonacci Heaps para obtener el nodo de menor costo en cada iteraci´on [14].

3.1.1.1.

Algoritmo A∗

El algoritmo A∗ es una extensi´ on del algoritmo de Dijkstra. Fue planteado por Peter Hart, Nils Nilsson, y Bertram Raphael en 1968 [17, 18]. Este algoritmo utiliza una funci´on heur´ıstica h(v) que se suma al costo de llegar al nodo, para de esta manera guiar el orden de exploraci´on de los nodos en el algoritmo. As´ı, en cada iteraci´on no se elige el nodo de menor costo sino el nodo que minimiza la suma de ´este y el valor de h.

Mart´ınez, Sainz–Tr´ apaga

P´agina 36 de 82

Algoritmo 3.1 C´ alculo del camino m´ınimo entre nodos u y v en G(V, E) con funci´on de peso w 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:

∀x ∈ V : costosx = ∞ ∀x ∈ V : predecesorx = null fijos = {u} costosu = 0 Mientras v 6∈ fijos hacer costoMinimo = m´ın({costosy /y ∈ V ∧ y 6∈ fijos}) Sea x ∈ V / costox = costoMinimo fijos = fijos ∪{x} Para cada y adyacente a x/y 6∈ fijos hacer Si costoy > costox +w(x, y) entonces costoy = costox +w(x, y) predecesory = x Fin si Fin para Fin mientras En el contexto de A∗ , decimos que la heur´ıstica h(v) es: Admisible si no sobrestima la distancia hacia el objetivo Consistente si ∀u, v ∈ V : h(v) ≤ w(v, u) + h(u)

Si h es admisible y consistente seg´ un esas definiciones, A∗ es equivalente al algoritmo de Dijkstra dado que ambos encuentran el camino m´ınimo. Sin embargo, y pesar de que ambos algoritmos tienen el mismo orden de complejidad, A∗ suele tener un tiempo de ejecuci´on considerablemente menor ya que la heur´ıstica puede brindarle informaci´on adicional al procedimiento para guiar la b´ usqueda de manera m´ as inteligente.

3.1.2.

Camino m´ınimo en grafos dependientes del tiempo

En base a las definiciones antes planteadas debemos proponer un algoritmo que pueda determinar el camino m´ınimo en nuestro modelo, en el que tanto la existencia como el costo de los arcos est´ an condicionados por el tiempo. Definamos en primer lugar la propiedad fifo para grafos dependientes del tiempo. Sea Gt (V, E, wt ) un grafo dependiente del tiempo, con V el conjunto de nodos de Gt , E los arcos y wt la funci´on de costo dependiente del tiempo. Diremos que Gt cumple la propiedad fifo (First In, First Out) si y solo si todos sus arcos (u, v) cumplen que: ∀t1 , t2 ∈ R>0 , t1 ≤ t2 ⇒ t1 +wt (u, v, t1 ) ≤ t2 +wt (u, v, t2 ) Informalmente, un grafo dependiente del tiempo es fifo si siempre resulta conveniente llegar m´as temprano a un nodo que llegar m´ as tarde, o en el peor de los casos es equivalente. El grafo de nuestro modelo no cumple la propiedad fifo, ya que al cambiar el viento con el tiempo nada impide que en un instante t0 sea imposible navegar entre dos nodos u y v (ya sea porque no hay viento, o porque el viento no es favorable) pero que m´as tarde la situaci´on cambie. Esta situaci´ on se ilustra en la Figura 3.1: un velero que llega en el instante t0 no puede navegar entre los nodos unidos por la flecha punteada ya que no hay ning´ un arco que se lo permita. Sin embargo, de haber llegado m´ as tarde podr´ıa haber encontrado un viento distinto que s´ı se lo hubiera permitido.

Mart´ınez, Sainz–Tr´ apaga

P´agina 37 de 82

(a) t = t0

(b) t = t0 + ∆t

Figura 3.1: Cambio en los arcos del grafo seg´ un el viento Esto representa un problema para nuestro modelo: el algoritmo de Dijkstra (incluidas sus variantes como A∗ ) no es correcto sin la condici´on fifo. Observemos el ejemplo de la Figura 3.2. Para desplazarse del nodo u al nodo v hay que pasar por el nodo w. Si se aplica el algoritmo de Dijkstra, se intentar´ a llegar lo antes posible a cada nodo. Llegamos entonces al nodo w en t = 10. Para abandonar el nodo w y llegar a v, debemos “pagar” un costo de 1000, para un total de 1010. Sin embargo, exist´ıa un camino m´ as corto: ir hasta w pasando por z y pagando un costo de 50, para luego pasar a v con un costo de 1. As´ı, el total ser´ıa de 51.

v

v 1000 w

1 30

10

z

20

w

30

10

z

20

u

u

(a) t = 0

(b) t = 50

Figura 3.2: Grafo dependiente del tiempo no-fifo

Lo que ocurre es que el algoritmo de Dijkstra utiliza la subestructura ´optima del problema de camino m´ınimo, que aprovecha mediante programaci´on din´amica. Sin embargo, en grafos dependientes del tiempo no-fifo, el problema no presenta subestructura ´optima: un camino m´ınimo entre dos nodos puede contener caminos sub´ optimos entre nodos intermedios. Por lo tanto, el algoritmo no funciona correctamente. En efecto, el problema de hallar un camino m´ınimo en un grafo no-fifo es np-hard [23, 30]. Sin embargo, Orda y Rom probaron que introduciendo la posibilidad de esperas en los nodos, el grafo se puede transformar en fifo en tiempo polinomial [22]. La espera, como su nombre lo indica, consiste en permanecer en un nodo por un tiempo arbitrario en lugar de estar obligado

Mart´ınez, Sainz–Tr´ apaga

P´agina 38 de 82

a abandonarlo inmediatamente. Formalmente, se considera que para cada nodo v y todo tiempo r ∈ R>0 se agrega un arco (v, v) con costo r. Nuestro modelo inicial no contemplaba la posibilidad de esperar. Sin embargo, la opci´on es l´ıcita: nada proh´ıbe que durante una regata, sus participantes se detengan (por lo general, anclando) a la espera de mejores condiciones de viento o corriente. En la pr´actica no es algo que se realice com´ unmente, pero puede ser de vital importancia si el viento calma completamente y la corriente aleja a los participantes de su destino. Dado que incluir la posibilidad de espera no s´olo redunda en un modelo m´ as completo, sino que adem´as reduce la optimizaci´on a un problema polinomial, optamos por incluir la posibilidad de “arrojar el ancla” y esperar en los nodos. Para transformar un grafo no-fifo en uno que s´ı cumpla con la propiedad, construimos una funci´ on w0 para el costo de los arcos, que se define de la siguiente manera: w0 (u, v, t) = m´ın(w(t + ∆, u, v) + ∆) ∆≥0

El nuevo costo en un tiempo dado es el menor de los costos de transici´on sumado al costo de esperar para realizar dicha transici´ on. Con esta nueva definici´on, vuelve a ser cierto que es conveniente llegar lo mas r´ apido posible a cada nodo, ya que cualquier ventaja que se pod´ıa tener llegando despu´es, se puede lograr esperando. Recordando la Figura 3.2, al llegar al nodo w el costo del arco que incide en v es: m´ın( 0 + 1000 , 40 + 1) | {z } | {z } no esperar esperar

Esto nos deja un costo de 41, que sumado al costo de llegar a w (que era 10) nos permite obtener un costo total de 51, que era el costo m´ınimo. Notemos que el camino es distinto: recorremos ahora u, w, v esperando en w, mientras que antes era necesario transitar por el nodo z. Es por esto que, para realizar la transformaci´ on que hace del grafo uno fifo, es importante que en el contexto del problema modelado la espera sea v´ alida. En nuestro caso, podemos definir Costo0 (u, v, t), seg´ un lo planteado anteriormente, como: Costo0 (u, v, t) =

m´ın (Costo(u, v, ti ) + (ti − t))

ti ∈T,ti ≥t

Con esta nueva definici´ on, es posible resolver el problema utilizando una variante del algoritmo de Dijkstra, que analizaremos a continuaci´on.

3.1.2.1.

Camino m´ınimo en grafos FIFO

Como se mencionara antes, bajo la hip´otesis fifo existe un algoritmo para hallar el camino m´ınimo en tiempo polinomial. El mismo fue propuesto por Dreyfus y es una generalizaci´on directa para el algoritmo de Dijkstra [7]. Curiosamente, Dreyfus lo propuso como una soluci´on general, sin notar que s´ olo funcionaba para grafos con la propiedad fifo. Sus resultados fueron luego discutidos en otros estudios [16, 20, 22].

Mart´ınez, Sainz–Tr´ apaga

P´agina 39 de 82

A su vez, se puede generalizar el algoritmo A∗ de la misma manera. La extensi´on es inmediata si se utiliza una heur´ıstica h(v) consistente y admisible. Un ejemplo de esto puede verse en el trabajo de Kanoulas et al [19]. M´ as a´ un, tambi´en es posible considerar una heur´ıstica dependiente del tiempo h(v, t) [36].

3.1.3.

Heur´ısticas propuestas para A∗

Necesitamos para nuestro uso heur´ısticas que permitan estimar el costo necesario para llegar desde un nodo u cualquiera al nodo final en el grafo de nuestro modelo. Propondremos a continuaci´ on dos heur´ısticas que fueron utilizadas en nuestra implementaci´on de A∗ .

3.1.3.1.

Heur´ıstica basada en distancia cartesiana

La primera heur´ıstica que consideramos utiliza la distancia euclidiana entre u y alguno de los nodos adyacentes al nodo final 19 . Llamemos v al nodo vecino al nodo final. Para obtener el tiempo, se divide la distancia kv − uk por la mayor velocidad que el barco puede lograr en cualquier direcci´ on, para cualquiera de los vientos que se puedan producir en la cancha. Si se tomara la velocidad caracter´ıstica en la direcci´on entre u y v, la heur´ıstica no ser´ıa admisible ya que podr´ıa subestimar la distancia total. Esto se debe a que los tiempos de navegaci´on en el plano no cumplen la desigualdad triangular, puesto que las velocidades de los barcos est´an muy lejos de ser uniformes dependiendo de su direcci´on. Formalmente, definimos: he (v) =

kv − uk maxVel

Siendo maxVel la velocidad m´ axima que puede desarrollar el velero en cualquier direcci´on, cuadrante y tiempo. Intuitivamente, esta heur´ıstica resulta muy susceptible a outliers de viento, ya que alcanzar´ıa con que en alg´ un cuadrante haya un viento muy alto para que el valor de maxVel aumente bruscamente y la heur´ıstica subestime demasiado el tiempo total, reduciendo su efectividad. Por otro lado, el valor de la velocidad efectiva de navegaci´on suele ser mucho menor al de la m´axima velocidad posible, en funci´ on de la gran disparidad que existe entre las velocidades de un rumbo y otro. Dado que la efectividad de la heur´ıstica utilizada por A∗ aumenta mientras mejor sea la aproximaci´on de la misma al costo real, no deber´ıan esperarse grandes mejoras con una cota tan gruesa. Por estas razones, no confi´ abamos en que esta heur´ıstica nos permitiera obtener muy buenos resultados en la pr´ actica. Heur´ısticas de este tipo se utilizan en otros trabajos para problemas de ruteo [19], pero las caracter´ısticas particulares de nuestro problema (m´as precisamente, la gran variaci´on de velocidad que existe entre una direcci´ on y otra) dificultan su funcionamiento. 19 Recordemos

que tanto el nodo inicial como el final no tienen asociadas coordenadas en el plano, son u ´tiles simplemente para la construcci´ on del modelo.

Mart´ınez, Sainz–Tr´ apaga

3.1.3.2.

P´agina 40 de 82

Heur´ıstica basada en VMC

Como dijimos, la heur´ıstica anterior es bastante gen´erica y utiliza muy poca informaci´on del dominio del problema a tratar. En principio, si volvemos sobre una curva polar como la de la Figura 1.7, salta a la vista el origen del problema: algunos ´angulos respecto del viento tienen velocidades muy superiores a otros. As´ı, tomar la velocidad m´axima como estimaci´on de la velocidad del barco (en la cuenta anterior referida a maxVel introduce un error muy sustancial. Lo deseable ser´ıa entonces tener en cuenta la direcci´ on en la que la embarcaci´on desea desplazarse en lugar de tomar el m´ aximo para todas las direcciones. El problema con esto ya fue anunciado antes: la desigualdad triangular no es v´alida en la navegaci´ on a vela, puesto que es usual que rutas m´as largas en distancia necesiten menos tiempo para ser recorridas. Buscamos entonces relajar la noci´on detr´as de la desigualdad triangular para obtener una cota m´ as fina, pero manteniendo la admisibilidad de la misma. As´ı, partimos de la idea de que para avanzar desde un punto a otro del grafo necesariamente habr´ a que atravesar una cierta cantidad de filas de la grilla del modelo. Como cada cuadrante tiene condiciones homog´eneas, podemos evaluar, sobre un intervalo de tiempo, cual es la manera m´as r´ apida de atravesar cualquiera de los cuadrantes que integran una fila a partir del vmc (introducido en la Figura 2.1b). As´ı obtendremos una cota inferior del tiempo necesario para atravesar cada fila entre el punto de origen y el de destino, que corresponde a los di en la Figura 3.3. Final

Inicial

Figura 3.3: Explicaci´on de la heur´ıstica de VMC

Mart´ınez, Sainz–Tr´ apaga

P´agina 41 de 82

Pn Adem´ as, es cierto que D ≥ i=0 di , con lo cual podemos deducir una cota admisible del tiempo necesario para realizar la ruta completa. Eso se debe a que independientemente de la ruta elegida, para pasar de una fila a otra necesariamente hay que atravesar uno de sus cuadrantes. El tiempo necesario para cruzar un cuadrante de esta manera, se puede acotar dividiendo la altura del cuadrante (en metros) por el vmc en la direcci´on perpendicular a la fila (que corresponde a la m´ axima velocidad proyectada sobre esa direcci´on que puede alcanzar el velero). Recordemos que a los cuadrantes se les asignaba una tupla (fila, columna) que indicaba su posici´on en la grilla. Si tomamos una grilla con A cuadrantes de altura, definimos entonces: hVMC0o (v)

=

A X

tiempoFila(i)

i=f ila(v)

Donde: tiempoFila(i) es el menor tiempo en el que se puede cruzar el cuadrante i (es decir, el alto del cuadrante divido por la mayor velocidad que se puede lograr hacia arriba, considerando todos los cuadrantes de la fila en todos los instantes). La fila de un nodo es el m´ aximo de las filas de sus cuadrantes La fila de un cuadrante es la fila que le corresponde en la grilla Un razonamiento similar se puede hacer para las columnas de la grilla modelada, e incluso ambas opciones pueden combinarse. Sin embargo, la experimentaci´on mostr´o que el vmc horizontal sol´ıa subestimar demasiado el tiempo y por lo tanto no presentaba ventajas sustanciales. Intentamos aprovechar las dos opciones utilizando la velocidad resultante de combinar el vmc vertical con el horizontal, pero nuevamente en la experimentaci´on no funcion´o muy bien. Suponemos que la subestimaci´ on propia del vmc horizontal es tan grande que desmejora el resultado obtenido por la vertical. Finalmente decidimos aprovechar ambos c´alculos tomando la cota m´as fina de las dos: hVMC = m´ax(hVMC0o , hVMC90o )

3.1.4.

Algoritmo final para rutas o ´ptimas

Tras la presentaci´ on de los distintos algoritmos para la obtenci´on de caminos m´ınimos, estamos en condiciones de introducir el seudoc´ odigo del algoritmo que utilizamos para obtener el camino m´ınimo en el grafo del modelo, que se corresponde con la ruta ´optima para la regata. El c´odigo correspondiente es el Algoritmo 3.2.

3.2.

Implementaci´ on

Las implementaciones relativas al modelo se realizaron en c++ ya que busc´abamos lograr un buen rendimiento. Todas las implementaciones de grafos y objetos de geometr´ıa computacional fueron construidas por nosotros para adaptarlas al m´aximo a las necesidades particulares del problema.

Mart´ınez, Sainz–Tr´ apaga

P´agina 42 de 82

Algoritmo 3.2 C´ alculo del camino m´ınimo entre u y v usando A∗ con heur´ıstica h(v) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:

∀x ∈ V : costosx = ∞ ∀x ∈ V : predecesorx = N U LL fijos = {u} costosu = 0 tiempo = 0 Mientras v 6∈ fijos hacer costoMinimo = m´ın({costosy +h(y)/y ∈ V ∧ y 6∈ fijos}) Sea x ∈ V / costox +h(x) = costoMinimo fijos = fijos ∪{x} Para cada y adyacente a x/y 6∈ fijos hacer Si costoy > costox + Costo(x, y, costox ) entonces costoy = costox + Costo(x, y, costox ) predecesory = x Fin si Fin para Fin mientras

El primer inconveniente de implementaci´on fue la estructura de datos asociada al grafo. Una primera versi´ on constru´ıa el grafo en memoria utilizando listas de adyacencia. Sin embargo, con el aumento de la resoluci´ on y el consiguiente incremento en la cantidad de arcos, r´apidamente tuvimos que descartar esta alternativa por limitaciones en la cantidad de memoria necesaria. Resultaba adem´ as bastante ineficiente construir un grafo completo en memoria dado que el buen comportamiento de nuestra implementaci´on de A∗ hac´ıa necesario recorrer solo una porci´on muy reducida del mismo. En u ´ltima instancia optamos por generar las listas de adyacencia din´amicamente s´olo a medida que se iba realizando la exploraci´ on del grafo, eliminando posteriormente la informaci´on ya utilizada para asegurar un uso reducido de recursos. Para guardar informaci´ on de los nodos se utiliz´o una propiedad: si n > 1 es la cantidad de nodos por lado y (x, y) las coordenadas de un nodo, entonces x ≡ 0 m´od (n − 1) ∨ y ≡ 0 m´od (n − 1). En base a ´esta se desarroll´ o una funci´ on de numeraci´on de los nodos que permite almacenar los mismos en vectores en memoria, sin necesidad de implementaciones m´as costosas y lentas de diccionarios. Finalmente se utilizaron intensivamente cach´es en memoria para reutilizar tantos c´alculos como fuera posible. En muchos casos, los escenarios presentan un alto grado de redundancia que permite que las t´ecnicas de memorizaci´ on brinden beneficios sustanciales. La implementaci´ on de curvas polares que se utiliza para calcular los pesos de los arcos ten´ıa inicialmente una implementaci´ on vectorial que ofrec´ıa una resoluci´on arbitraria para los ´angulos de navegaci´ on en base a los puntos ingresados a partir de la predicci´on del vpp. M´as adelante decidimos hacer un muestreo de dichas curvas con una resoluci´on de 1o que por las caracter´ısticas t´ıpicas de las mismas result´ o ser m´ as que suficiente, y nos permiti´o mejorar bastante el rendimiento del algoritmo en general. Dado que en la implementaci´on definitiva los arcos se computan din´amicamente, la evaluaci´ on de sus costos se torna una operaci´on cr´ıtica. Al igual que en varias secciones del c´ odigo del grafo, se utiliz´o un cach´e de polares. En la medida en que los algoritmos de b´ usqueda exploran el grafo de forma ordenada, es de esperarse que se reali-

Mart´ınez, Sainz–Tr´ apaga

P´agina 43 de 82

cen numerosas consultas para unas mismas condiciones de viento y corriente (ya que todos los arcos de un mismo cuadrante comparten estas condiciones). Esta optimizaci´on result´o particularmente efectiva.

Figura 3.4: Aplicaci´on para an´alisis de curvas polares

Utilizamos extensivamente Python para construir herramientas de visualizaci´on y evaluaci´on de los resultados. Realizamos tambi´en bindings para Python de la implementaci´on de las curvas polares, y con ellas una aplicaci´ on independiente para consultas y an´alisis de dichas curvas para cualquier viento y corriente, as´ı como de c´alculo de las curvas de vmc y vmg asociadas.

Mart´ınez, Sainz–Tr´ apaga

P´agina 44 de 82

Cap´ıtulo 4

Heur´ısticas 4.1.

¿Por qu´ e desarrollar heur´ısticas?

El modelo exacto descripto en el cap´ıtulo anterior nos permite, dada una descripci´on completa de un escenario del problema, optimizar la ruta de navegaci´on de un velero a partir de su predicci´on polar de velocidad. La descripci´ on debe ser abarcativa: para poder calcular la ruta ´optima, se necesitan conocer tanto el viento como la corriente en toda la extensi´on del ´area de inter´es, as´ı como su evoluci´ on a lo largo de un per´ıodo de tiempo apropiado. Sin embargo, como se discuti´ o en la Secci´on 1.2.3, la presunci´on de que un navegante dispone de informaci´ on tan detallada no es veros´ımil. Si bien se puede considerar que un pron´ostico a gran escala como gfs es fiable y completo, su resoluci´on espaciotemporal s´olo permite su uso en c´ omputos de rutas para regatas de larga distancia. Como hab´ıamos anticipado, el centro de nuestra atenci´ on son las regatas cortas, y para las mismas los pron´osticos son casi siempre irrelevantes. En este contexto, la u ´nica informaci´on que el regatista tiene a su alcance es la que le proveen los instrumentos instalados a bordo de su barco. Algunas de las mediciones que una embarcaci´on de regatas adquiere en tiempo real son la direcci´on e intensidad del viento (mediante un anem´ometro y una veleta), la direcci´ on y velocidad del barco respecto del agua (mediante un comp´ as magn´etico y una corredera20 ), la direcci´ on y velocidad del barco respecto de la tierra (con un gps) y la temperatura y profundidad del agua en que navega (con una sonda ecoica), entre otros. Figura 4.1: Instrumental de un vo70 La mayor´ıa de los instrumentos modernos utilizan el est´ andar de datos nmea 0183 (por las siglas de National Marine Electronics Association) y por lo tanto pueden intercambiar informaci´on entre s´ı, o enviarla a un sistema inform´atico convencional. Esto permite que un software analice estos datos en tiempo real. Sin embargo, esta informaci´on es claramente insuficiente para construir rutas ´ optimas en nuestro modelo: todos los datos son lecturas en tiempo real (lo que implica un desconocimiento de su evoluci´ on futura), y a su vez todos ellos conciernen a la ubicaci´on geogr´afica del barco (lo que redunda en el desconocimiento de las condiciones en otros lugares). A´ un as´ı, es posible utilizar la informaci´on que se adquiere durante la navegaci´on para tomar decisiones estrat´egicas, en particular para regatas de corta distancia. La evidencia de esto es emp´ırica: los navegantes que obtienen buenos resultados en competencias de corta distancia solo disponen de esta informaci´ on, al igual que los dem´as competidores. 20 Instrumento

que mide la velocidad del agua bajo el casco del barco con una peque˜ na h´ elice sumergida.

Mart´ınez, Sainz–Tr´ apaga

P´agina 45 de 82

Nuestro objetivo es desarrollar un algoritmo que pueda servirse de esta informaci´on acotada para tomar decisiones heur´ısticas, permiti´endole hacer una aproximaci´on razonable a las rutas ´optimas que podr´ıan computarse si la informaci´on completa estuviera disponible. Para ello, nos servimos del algoritmo exacto presentado en el cap´ıtulo anterior como benchmark para el rendimiento de los m´etodos aproximados. Si bien es ambicioso suponer que las rutas resultantes de algoritmos heur´ısticos puedan ser utilizadas en forma directa, s´ı es razonable esperar que sirvan como informaci´on para el tripulante a cargo de la estrategia, ofreci´endole informaci´on adicional para ayudarlo en la toma de decisiones.

4.2.

Framework para heur´ısticas

Decidimos centrarnos para el desarrollo de heur´ısticas en las condiciones de competencia m´as usuales para regatas de corta distancia: los recorridos entre boyas introducidos en la Secci´on 1.1.3. Para esto, recurrimos a nuestro conocimiento del dominio, discusiones con expertos regatistas y a la literatura no acad´emica que utilizan los mismos[2, 15, 29]. En este tipo de regatas, la cuesti´ on m´as desafiante desde el punto de vista estrat´egico es en qu´e momento de una pierna deber´ an realizarse las maniobras (ya sean viradas o trasluchadas) para aprovechar mejor el viento disponible. Una primera aproximaci´on al problema revela que como regla general siempre debe navegarse en rumbos de vmg. Si bien el concepto de vmg se discuti´ o en la Secci´ on 2.1, ahondaremos un poco m´ as en ´el a partir de la Figura 4.2. En ella, un velero navega en una bordejeada contra el viento. Los rumbos de mayor vmg est´ an indicados en la figura con puntos azules. Se observa intuitivamente que son precisamente esos rumbos los que maximizan la velocidad ´ en direcci´ on opuesta al viento. Angulos m´as abiertos o m´ as cerrados para cada borde redundar´ıan en una velocidad resultante menor en la direcci´on en que se desea avanzar. La curva azul es la polar de vmg, que como se mencionara oportunamente no es m´ as que la c´ apsula convexa de la curva polar de velocidad.

0º

45º

2

4

6

8

La elecci´ on de navegar u ´nicamente en rumbos de mayor vmg reduce significativamente el espacio de b´ usqueda que deben considerar nuestras Figura 4.2: Rumbos de vmg heur´ısticas. A partir de esta suposici´ on, para todo tipo de navegaci´ on habr´ a que decidir a lo sumo entre dos opciones, que corresponden a los bordes alternativos de las bordejeadas. Esto no es solo una simplificaci´ on para nuestro modelo, sino que se condice muy bien con la realidad de una regata. En todo momento, una u ´nica pregunta flota en la cabeza de un estratega: ¿viro o no viro? As´ı, proponemos un armaz´ on general para la construcci´on de heur´ısticas que ser´a com´ un a todas nuestras propuestas. Recorriendo el grafo, se elegir´a en cada nodo hacia d´onde se desea avanzar en

Mart´ınez, Sainz–Tr´ apaga

P´agina 46 de 82

el paso siguiente mediante un criterio. Ser´a este criterio lo que diferencie a una heur´ıstica de otra. Las opciones que se presenten a los criterios corresponder´an u ´nicamente a los rumbos de mayor vmg. El m´etodo general com´ un a todas las heur´ısticas se describe en el Algoritmo 4.1. Cabe aclarar que en las navegaciones que no requieren de una bordejeada para ser recorridas en tiempo m´ınimo, el rumbo de mayor vmg ser´a u ´nico y corresponder´a al rumbo directo. Algoritmo 4.1 Elecci´ on del pr´ oximo movimiento en una heur´ıstica 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:

dir = (xfinal , yfinal ) − (xactual , yactual ) Para cada cuadrante donde est´ a el nodo actual hacer calcular la velocidad actual en direcci´on dir con el viento y la marea del cuadrante hacer lo mismo pero obteniendo el vmg Si el vmg y la velocidad coinciden entonces obtener el nodo candidato intersecando la recta que pasa por el nodo con direccion=dir Si no obtener los rumbos de mayor vmg obtener los nodos candidatos intersecando los rumbos de mayor vmg con el cuadrante Fin si Fin para aplicar el criterio propio de la heur´ıstica a los candidatos para elegir el pr´oximo punto Si seguir desde el nodo elegido requiere hacer una maniobra entonces maniobrar y continuar desde este nodo Si no pasar al nodo candidato y continuar Fin si

La condici´ on de la l´ınea 5 modela la situaci´on en que el rumbo hacia el destino final no requiere una bordejeada: en este caso vmg y velocidad coinciden, por lo que se puede navegar directamente hacia el objetivo final y no es necesario tomar ninguna decisi´on. Por otra parte, la condici´ on de la l´ınea 13 modela la posibilidad de que tras decidir llevar a cabo una maniobra, no resulte conveniente avanzar hacia otro nodo como se hab´ıa planeado cuando se decidi´ o ejecutarla. Este “arrepentimiento” cobra sentido en la medida en que las maniobras insumen una cantidad de tiempo: durante la ejecuci´on de una, las condiciones meteorol´ogicas pueden cambiar y hacer que lo m´ as conveniente sea realizar una nueva maniobra en lugar de apegarse a la idea original. En base a este framework general, propondremos a continuaci´on varios criterios de decisi´on.

4.3. 4.3.1.

Criterios de decisi´ on Criterio de mayor VMG ponderado

A partir de lo establecido algunas l´ıneas atr´as, podemos plantear una primera idea: si partimos de la base de que siempre es deseable utilizar uno de los rumbos de mayor vmg para maximizar esta m´etrica, podemos ir a´ un m´ as all´ a y elegir, cuando haya opciones, aquella que se caracterice por tener un mayor vmg. As´ı elegiremos entre dos bordes aquel cuya proyecci´on sobre la direcci´on

Mart´ınez, Sainz–Tr´ apaga

P´agina 47 de 82

deseada nos da una mayor velocidad hacia el destino. Se trata de lo representado en la Figura 4.3. Esta heur´ıstica es muy utilizada en la pr´actica por los navegantes que cuentan con un gps con la capacidad de computar el vmg hacia el destino. La direcci´ on en que se desea navegar corresponde a la flecha negra en la ilustraci´ on. La curva polar presenta en la regi´ on intersecada por esta direcci´ on una concavidad, lo que redunda en la posibilidad de obtener la velocidad ´ optima realizando una bordejeada. Los bordes entre los que hay que optar fueron representados en color celeste: son los rumbos de mayor vmg. La proyecci´ on de los mismos sobre la direcci´ on deseada fue indicada con las l´ıneas rojas punteadas. En esta situaci´ on, el borde m´ as conveniente parece ser el de la izquierda, puesto que se acerca m´ as a la direcci´ on en que se desea navegar. Se deduce de aqu´ı que si se desea navegar en forma exactamente opuesta a la direcci´ on del viento, el vmg de ambos bordes ser´ a id´entico. En ese caso se puede elegir de forma arbitraria o aleatoria alguna de las opciones, puesto que el criterio planteado no ofrece informaci´ on.

0º

45º

2

4

6

8

Figura 4.3: Comparaci´on de vmg

Sin embargo se presenta una situaci´on problem´atica. Analicemos un caso bajo la hip´otesis de que el viento es constante. La direcci´ on en la que se desea navegar es por definici´on la que conduce directamente al objetivo final. Este u ´ltimo a su vez se encuentra inm´ ovil, a diferencia del velero, y por lo tanto la direcci´on deseada va variando en la medida en que el punto en que se encuentra el velero se modifica. Supongamos que resulta en este punto m´as conveniente elegir el borde izquierdo. A medida que el velero avanza con ese borde, la diferencia de vmg a favor de esta decisi´on disminuye paulatinamente, hasta llegar a un punto de indiferencia cuando el velero se encuentra exactamente a sotavento (“viento abajo”) del punto de destino. En este punto resulta conveniente virar, puesto que el vmg del borde opuesto ser´a  m´as grande. Sin embargo, al tomar este otro borde se produce el fen´omeno inverso: el borde contrario comienza paulatinamente a aumentar su valuaci´on. El problema aparece si  es muy chico: casi inmediatamente, volver´a a ser conveniente el borde izquierdo. As´ı, el velero comenzar´a una r´apida sucesi´ on de viradas que si bien lo conducir´a al destino, lo obligar´ a a pagar un costo muy grande por realizar tantas maniobras. Lo comentado se refleja en la Figura 4.4. Figura 4.4: Viradas excesivas

Para resolver esta situaci´on introducimos un coeficiente cv (coeficiente de virada) de modo a condicionar la virada. Ahora no

Mart´ınez, Sainz–Tr´ apaga

P´agina 48 de 82

ser´ a suficiente que el otro borde sea mejor que el actual en t´erminos absolutos: deber´ıa superarlo en una proporci´ on mayor que cv . As´ı, el criterio resultante es el descripto en el Algoritmo 4.2, que llamamos Criterio de vmg ponderado (Criterio p). Algoritmo 4.2 Criterio p Par´ ametros: candidatos: Conjunto de nodos candidatos a ser el siguiente nodo visitado Par´ ametros: actual: nodo actual 1: sinVirar = elegir de entre los candidatos aquellos que no requieran virar 2: maxSinVirar = elegir de entre los candidatos en sinVirar el que maximice el VMG 3: virar = elegir de entre los candidatos aquellos que requieran virar 4: maxVirando = elegir de entre los candidatos en virar el que maximice el VMG 5: Si VMG(maxVirando) > VMG(maxSinVirar ) ∗ cv entonces 6: elegir maxVirando 7: Si no 8: elegir maxSinVirar 9: Fin si

4.3.2.

Criterio de mayor VMG ponderado y distancia Si bien resolvimos un problema con el criterio de mayor vmg en el inciso anterior, el resultado de la introducci´on del coeficiente cv acarrea otra debilidad. La relaci´on entre el vmg de un borde y el otro est´a dada mayormente por el ´angulo entre el viento y la direcci´on al destino. Si mantenemos la hip´otesis de viento constante, la sucesi´on de bordes que seleccionar´a la heur´ıstica producir´a tramos cada vez m´as cortos entre las viradas a medida que la embarcaci´on se aproxima al destino, como se observa en la Figura 4.5. Una vez m´as, por la reducci´on de la longitud de cada borde se cae en viradas innecesarias que implican un costo adicional. Si bien es razonable que a medida que el destino se aproxima los bordes se reduzcan paulatinamente, es necesario acotar esta reducci´on para no pagar costos extraordinarios.

Figura 4.5: Bordes de largo decreciente

As´ı, introducimos un segundo coeficiente cd (coeficiente de distancia) que penaliza la decisi´on de virar seg´ un el criterio estipulado anteriormente en funci´on de la distancia al destino. De esta manera, mientras m´as cerca est´e el barco de llegar a su objetivo, mayor resistencia tendr´a a tomar la decisi´on de virar. Una opci´on similar fue presentada por Stelzer y Pr¨oll en [31]. Este criterio se denomina Criterio de vmg ponderado y distancia (Criterio pd) y se define en el Algoritmo 4.3.

En la l´ınea 6 se utiliza la operaci´ on m´aximo para permitir que el cv sea menor que 1. Si no se cd hiciera esta salvedad, cuando la distancia al destino fuera muy grande el t´ermino distancia tomar´ıa un valor muy chico que redundar´ıa en un coeficiente global inferior a 1. La implicaci´on de esto ser´ıa que el barco buscar´ıa virar constantemente, no logrando ning´ un progreso hacia su objetivo.

Mart´ınez, Sainz–Tr´ apaga

P´agina 49 de 82

Algoritmo 4.3 Criterio pd Par´ ametros: candidatos: Conjunto de nodos candidatos a ser el siguiente nodo visitado Par´ ametros: actual: nodo actual 1: sinVirar = elegir de entre los candidatos aquellos que no requieran virar 2: maxSinVirar = elegir de entre los candidatos en sinVirar el que maximice el VMG 3: virar = elegir de entre los candidatos aquellos que requieran virar 4: maxVirando = elegir de entre los candidatos en virar el que maximice el VMG 5: distancia = kposllegada − posactual k cd )) entonces 6: Si VMG(maxVirando) > VMG(maxSinVirar ) ∗ m´ ax(1, (cv + distancia 7: elegir maxVirando 8: Si no 9: elegir maxSinVirar 10: Fin si

4.3.3.

Criterios asim´ etricos

Tras reunirnos con expertos en meteorolog´ıa para regatas[9] decidimos incorporar variantes asim´etricas de las heur´ısticas propuestas hasta el momento. En ellas, los coeficientes cv y cd toman valores diferenciados seg´ un la amura en que se encuentre navegando el barco. Estas variantes intentan permitir que las heur´ısticas tomen en cuenta la asimetr´ıa inherente a las variaciones de viento como rachas y borneos que tienen origen en la fuerza de Coriolis. Esta cuesti´on se examina en profundidad en la Secci´ on 5.1.3. A los efectos de implementar el criterio, la u ´nica diferencia es que se desdobla cada par´ametro en dos variantes (estribor y babor) que corresponden a las amuras hom´onimas. Luego, en funci´on de la situaci´ on en que se encuentra el barco se toma uno u otro valor para cada par´ametro. Los Algoritmos 4.4 y 4.5 corresponden a las versiones asim´etricas de los presentados en las secciones anteriores. Las mismas se denominan respectivamente Criterio pa y Criterio pda. Los nuevos par´ ametros que resultan de la escisi´on de cv y cd se nombran cvb , cve , cdb y cde .

4.3.4.

Criterios de viento promedio

Si bien el vmg en direcci´ on al destino parece una buena indicaci´on de la “calidad” de un borde, recordando la discusi´ on de la Secci´ on 3.1.3.2 podemos considerar que la verdadera dificultad en una bordejeada en contra del viento reside en avanzar en la direcci´on opuesta a la que ´este se dirige. Se puede formular una idea an´ aloga para la navegaci´on en popa. As´ı, formulamos heur´ısticas que tengan en cuenta para su objetivo el avance respecto de la direcci´ on en que sopla el viento adem´as del destino final al que se dirige la embarcaci´on. En muchos casos, a´ un cuando la competencia se realice entre boyas, errores en la colocaci´on de las mismas pueden hacer que la navegaci´ on que te´oricamente es contra el viento presente en cambio diferencias de varios grados en la pr´ actica. La idea de que a´ un cuando se desee navegar hacia una boya ubicada incorrectamente lo importante ser´ a navegar contra el viento es relativamente popular. Tacktick, fabricante ingl´es de compases magn´eticos digitales para navegaci´ on a vela, presenta en sus dispositivos una valoraci´on del rumbo

Mart´ınez, Sainz–Tr´ apaga

P´agina 50 de 82

Algoritmo 4.4 Criterio pa Par´ ametros: candidatos: Conjunto de nodos candidatos a ser el siguiente nodo visitado Par´ ametros: actual: nodo actual 1: sinVirar = elegir de entre los candidatos aquellos que no requieran virar 2: maxSinVirar = elegir de entre los candidatos en sinVirar el que maximice el VMG 3: virar = elegir de entre los candidatos aquellos que requieran virar 4: maxVirando = elegir de entre los candidatos en virar el que maximice el VMG 5: Si la amura de navegaci´ on actual es babor entonces 6: cv = cvb 7: Si no 8: {la amura es estribor} 9: cv = cve 10: Fin si 11: Si VMG(maxVirando) > VMG(maxSinVirar ) ∗ cv entonces 12: elegir maxVirando 13: Si no 14: elegir maxSinVirar 15: Fin si

Algoritmo 4.5 Criterio pda Par´ ametros: candidatos:Conjunto de nodos candidatos a ser el siguiente nodo visitado Par´ ametros: actual: nodo actual 1: sinVirar = elegir de entre los candidatos aquellos que no requieran virar 2: maxSinVirar = elegir de entre los candidatos en sinVirar el que maximice el VMG 3: virar = elegir de entre los candidatos aquellos que requieran virar 4: maxVirando = elegir de entre los candidatos en virar el que maximice el VMG 5: Si la amura de navegaci´ on actual es babor entonces 6: cv = cvb 7: cd = cdb 8: Si no 9: {la amura es estribor} 10: cv = cve 11: cd = cde 12: Fin si cd )) entonces 13: Si VMG(maxVirando) > VMG(maxSinVirar ) ∗ m´ ax(1, (cv + distancia 14: elegir maxVirando 15: Si no 16: elegir maxSinVirar 17: Fin si

Mart´ınez, Sainz–Tr´ apaga

P´agina 51 de 82

actual del barco en funci´ on del rumbo promedio que se mantuvo en ese borde durante el u ´ltimo per´ıodo. Este promedio incorpora las fluctuaciones del viento (ya que ´estas afectan directamente el rumbo del barco). El comp´ as sugiere virar cuando el rumbo actual del barco se encuentra por debajo del promedio en este borde. El libro de Rushall [29] presenta una idea similar para condiciones de viento oscilante: “The winning strategy in swinging conditions: tack when headed below the mean! 21 ”. En High Performance Sailing, Frank Bethwaite propone una idea parecida [2]. Consideramos entonces criterios que tendr´an como entrada adicional la direcci´on promedio del viento. Si bien nosotros proporcionaremos manualmente a los criterios de esta informaci´on, es relativamente trivial para un software ejecut´andose con instrumentos de a bordo realizar el c´alculo de forma aut´ onoma a partir de las lecturas de la veleta electr´onica. En efecto, el comp´as Tacktick propone a sus usuarios que ingresen dicha informaci´on mediante la observaci´on de las condiciones durante un per´ıodo anterior a la regata.

D

F

D

S

S

(a) Boya Ficticia

(b) Distancia Infinita

Figura 4.6: Heur´ısticas de viento promedio

Proponemos dos interpretaciones. En primer lugar introduciremos una boya ficticia en nuestro modelo que est´ a colocada en la posici´ on ideal respecto del viento promedio observado. En este criterio, la distancia al destino se considera respecto de la boya real, pero el vmg se calcula a partir del rumbo hacia la boya ficticia. Este criterio se denomina “de viento promedio y boya ficticia” (Criterio vpbf). El mismo se ilustra en la Figura 4.6a. Por u ´ltimo, en lugar de considerar una boya ficticia a distancia similar al destino real, consideraremos que la misma se encuentra a distancia infinita. Esto corresponde a evaluar el vmc de cada borde como m´etrica del mismo, lo que equivale a la proyecci´on de la velocidad de cada bordem, ya 21 “La estrategia ganadora en condiciones de viento oscilante: cuando el rumbo de este borde est´ e por debajo del promedio, ¡vira!”

Mart´ınez, Sainz–Tr´ apaga

P´agina 52 de 82

no en direcci´ on al punto de destino, sino en la direcci´on opuesta al viento promedio. Este criterio “de viento promedio y boya infinita” (Criterio vpi) corresponde a la Figura 4.6b. Decidimos implementar y evaluar ambos criterios. Notemos que son similares a los anteriores, con la diferencia de que se maximiza el vmg en otra direcci´on, modificando as´ı el objetivo de los bordes. Las consideraciones realizadas sobre los coeficientes de virada y distancia son id´enticas a las realizadas para las heur´ısticas anteriores, por lo que las implementaciones de estos criterios utilizan par´ ametros asim´etricos como se describe en la Secci´on 4.3.3.

Mart´ınez, Sainz–Tr´ apaga

P´agina 53 de 82

Cap´ıtulo 5

Experimentaci´ on 5.1.

El modelo experimental

Partiendo de la descripci´ on de las heur´ısticas introducidas en la secci´on anterior, surge la necesidad de evaluar su comportamiento. Estas heur´ısticas manejan un subconjunto de la informaci´ on necesaria para el c´ alculo de rutas ´optimas, que se corresponde con los datos que pueden ser obtenidos por el instrumental instalable a bordo. Nuestra propuesta experimental consiste en proveer al algoritmo exacto de la Secci´ on 3.1.4 de toda la informaci´on acerca de una regata para permitirle calcular una ruta ´ optima, y a continuaci´on ejecutar las heur´ısticas con el subconjunto de los datos que podr´ıan haber medido en tiempo real en la cancha de regatas. As´ı podremos analizar de forma contrastada las virtudes y defectos de las aproximaciones realizadas por estas u ´ltimas. Recordemos lo discutido en la Secci´on 1.2.3.1 sobre las caracter´ısticas del viento a distintas escalas. El sistema circulatorio global de la atm´osfera de la tierra se comporta de forma bastante predecible a corto plazo: centros de alta y baja presi´on se desplazan produciendo vientos cuya direcci´ on e intensidad puede ser calculada por modelos num´ericos. A mediana escala, fen´omenos t´ermicos como el ejemplificado en la Figura 1.12a pueden introducir modificaciones importantes sobre la predicci´ on de un modelo global. Finalmente, a peque˜ na escala, la turbulencia producida por los fen´ omenos de mayor tama˜ no gobierna las fluctuaciones locales en la direcci´on e intensidad del viento.

5.1.1.

Calidad de los escenarios a utilizar

Por el enfoque elegido, las heur´ısticas se dise˜ naron pensando en regatas gobernadas por situaciones que entran en esta u ´ltima categor´ıa. Si bien nuestro modelo es independiente de la escala a la que se utilice, evaluar el comportamiento de las heur´ısticas frente a pron´osticos de gran escala (como la Figura 1.11) carecer´ıa de sentido. Necesitamos por lo tanto escenarios de prueba de gran resoluci´ on, tanto espacial como temporal. En general, una regata entre boyas para embarcaciones de quilla tiene piernas de entre 1 y 3 Km, dependiendo del tama˜ no de los barcos que compitan. A su vez, el tiempo necesario para que los barcos naveguen estos tramos puede variar dependiendo del viento y de su performance, pero el orden de magnitud de los mismos es de unos 15 a 30 minutos. Dado que en una ce˜ nida es usual que los competidores realicen 5 o 6 viradas, nuestro modelo deber´a usar una discretizaci´on suficientemente fina como para que la ubicaci´on en el tiempo y en el espacio de estas maniobras no se vea restringida artificialmente por la baja resoluci´on del modelo. Asimismo, el par´ametro n del modelo deber´ıa ser suficientemente grande para no acotar demasiado los ´angulos de navegaci´on que pueden elegir los barcos. Recordemos que el par´ametro n fue descripto en la Secci´on 2.2.2, y corresponde a la cantidad de nodos que se emplazan sobre el lado de cada cuadrante de la grilla. Recordemos adem´ as que cada uno de estos nodos se multiplica por la cantidad de tipos de navegaci´ on que considera el modelo (ver Secci´on 2.2.2.1) al construir el grafo.

Mart´ınez, Sainz–Tr´ apaga

P´agina 54 de 82

En base a estimaciones de este tipo, decidimos utilizar las siguientes caracter´ısticas para nuestros escenarios de prueba: Tramos a navegar de 2500 metros Par´ ametro A = 50 (para un total de 50 × 50 cuadrantes en la grilla) Par´ ametro n = 30 Intervalo de variaci´ on del tiempo de 25 segundos Una discretizaci´ on de 50 × 50 cuadrantes, con n = 30 nodos sobre el lado de cada cuadrante permite a los barcos elegir sus rumbos con una granularidad de poco m´as de 1o , recorriendo arcos de menos de 70 metros de longitud. En base a la experiencia en regatas, ambas granularidades son relativamente finas en comparaci´ on a lo que puede controlarse en la pr´actica. En particular, es muy dif´ıcil que el timonel de un barco pueda conducirlo con una precisi´on de 1o .

5.1.2.

Obtenci´ on de los datos

Las resoluciones involucradas en nuestros escenarios eliminan la posibilidad de utilizar directamente mediciones meteorol´ ogicas reales. Para ello, ser´ıa necesario disponer de una grilla de 250 anem´ ometros y veletas electr´ onicas capaces de registrar los datos, distribuidos uniformemente sobre un espejo de agua de m´ as de 6Km2 , y a distancia suficiente de la costa como para que la presencia de la misma no interfiera con las mediciones. Por tratarse de instrumentos de medici´on caros y sensibles, nos es imposible acceder a datos de este tipo, y dudamos de la existencia de alguna instalaci´ on de estas caracter´ısticas. Resolvimos entonces recurrir a la generaci´on de escenarios de regata con las caracter´ısticas deseadas, intentando aproximarnos lo m´as posible a condiciones reales. Recordemos que los modelos meteorol´ ogicos utilizados para pron´ ostico no modelan las fluctuaciones que son de vital importancia para nuestras simulaciones, sino que las desprecian[6]. Por lo tanto, nos vimos en la necesidad de desarrollar un modelo propio de simulaci´on. Realizamos una extensa b´ usqueda de datos meteorol´ogicos que pudieran servirnos de referencia para hacer simulaciones. En todos los casos, los datos registrados por anem´ometros son de un u ´nico punto y ser´ıa por lo tanto necesario realizar alg´ un tipo de extrapolaci´on para tener datos espaciales. En un estudio realizado para el Team New Zealand que particip´o en la Copa Am´erica de 2000 [26] en el Golfo de Hauraki (Nueva Zelanda), Philpott et al realizaron mediciones de alta frecuencia en un pilote meteorol´ ogico dispuesto expresamente para tal fin. Tras el an´alisis de la direcci´on e intensidad del viento, se concluy´ o que en ese lugar la correlaci´on entre estas dos m´etricas no era significativa y se simul´ o solo la direcci´ on con un proceso de Markov, suponiendo que la intensidad era constante. Esto permiti´ o a los autores generar condiciones de viento comparables a las sensadas. En correspondencia personal, Philpott ampli´o: “The Markov chain assumed constant wind speed and random wind direction. The direction at any location varied as a Markov chain. This model was very crude and should be improved. The difficulty is in representing the spatial and time correlation of wind vectors realistically. A Markov chain is the simplest attempt to do this. We tried different approaches and eventually settled on assuming a single constant wind direction on any line at right angles to the course. This wind varied as a Markov chain.”22 22 “La

cadena de Markov asum´ıa para el viento intensidad constante y direcci´ on aleatoria. La direcci´ on en cualquier

Mart´ınez, Sainz–Tr´ apaga

P´agina 55 de 82

Como bien aclara el autor, el problema de esta idea es que la correlaci´ on espacial que existe en las variaciones de viento no es veros´ımil: las fluctuaciones en el viento no se propagan como olas rectas perpendiculares a la cancha de regatas (Figura 5.1). Adem´as, el objetivo del trabajo de Philpott era diferente al nuestro, ya que intentaban comparar dise˜ nos alternativos de barcos, y no calcular estrategias ´optimas. Nuestra aplicaci´on es m´as sensible a las deformaciones de los escenarios generados puesto que los utilizamos para evaluar heur´ısticas.

Figura 5.1: Modelo de viento de Philpott et al

A´ un cuando hubi´eramos decidido reutilizar la t´ecnica aqu´ı descripta, nos fue imposible obtener datos de viento con la resoluci´on temporal necesaria: todas las estaciones meteorol´ogicas locales, incluso las que son utilizadas como referencia por los regatistas [13, 27, 28, 34], presentan los datos a lo sumo en intervalos de 5 minutos, y por lo general de forma agregada (por ejemplo, promedio de intensidad sobre ese lapso de tiempo). A partir de este tipo de datos es imposible recuperar la informaci´on original de alta resoluci´on que incluye peque˜ nas fluctuaciones vitales para nuestra aplicaci´on.

Los u ´nicos datos que nos fue posible obtener provenientes de anem´ometros de alta resoluci´on temporal fueron obtenidos del sitio winddata.com [35]. Esta compa˜ n´ıa vende datos de este tipo para su utilizaci´ on en el dise˜ no de turbinas e´olicas para generaci´on de energ´ıa, y la calidad de los mismos es excelente. Sin embargo, al estar sensados en tierra y por lo general en la zona de los pa´ıses N´ ordicos (con el desconocimiento que eso implica sobre las caracter´ısticas del lugar por nuestra parte) decidimos buscar otra alternativa.

5.1.3.

El modelo de simulaci´ on

Resolvimos entonces buscar expertos en meteorolog´ıa y en regatas que pudieran darnos informaci´ on sobre cu´ ales son los factores m´as significativos que gobiernan la evoluci´on del viento a peque˜ na escala. As´ı podr´ıamos construir un modelo ad hoc de canchas de regata que estuviera en consonancia con la experiencia de navegaci´on. Tras una entrevista con Alberto Enguix23 , resolvimos generar escenarios para regatas que tuvieran una distribuci´ on veros´ımil de rachas aleatorias, tanto en su intensidad como en su forma y duraci´ on. A continuaci´ on reproducimos los conceptos esenciales que dieron origen a nuestro modelo[9]. El viento de escala sin´ optica (el que se deriva de los centros de alta y baja presi´on que circulan por la atm´ osfera) se caracteriza seg´ un los modelos meteorol´ogicos a alrededor de 1000 metros punto variaba seg´ un una cadena de Markov. Este modelo era muy rudimentario y deber´ıa mejorarse. La dificultad reside en representar la correlaci´ on espacial y temporal de los vectores de viento de manera realista. Una cadena de Markov es el intento m´ as simple de hacer esto. Intentamos varias opciones y finalmente decidimos asumir una u ´ nica direcci´ on de viento para cada l´ınea perpendicular a la direcci´ on del recorrido.” 23 Enguix es un experto local en meteorolog´ ıa aplicada a regatas y autor de varios libros sobre la materia [10, 11, 12]. Fue profesor de Vela en el Yacht Club Centro Naval y en la Escuela Argentina de N´ autica Deportiva. En 1986, la Universidad Nacional de C´ ordoba (C´ atedra de Navegaci´ on a Vela) lo nombr´ o Profesor Honoris Causa. Como regatista, represent´ o a la Argentina en 3 campeonatos mundiales de la clase 505. Adem´ as, fue responsable del dise˜ no y supervis´ o la construcci´ on del casco del Lantia, un velero de la clase internacional Penguin con que Mart´ın Costa se consagr´ o campe´ on mundial en 1972 en los Estados Unidos.

Mart´ınez, Sainz–Tr´ apaga

P´agina 56 de 82

Viento

Intensidad

Viento de gradiente Viento de superficie sobre agua Viento de superficie sobre tierra

100 % 65 % 30 %

Direcci´on +15o +30o

Tabla 5.1: Resumen del modelo de la espiral de Ekman de altura. Este viento se denomina tambi´en “viento de gradiente” ya que se desplaza seg´ un los gradientes de presi´ on atmosf´erica que lo producen. El viento de superficie est´a condicionado por este viento de altura, pero tambi´en est´ a sujeto a una importante fricci´on con la superficie terrestre. Por esta raz´ on, el viento de superficie originado de esta forma tiene siempre una velocidad menor que la del viento sin´ optico. La rotaci´ on de la tierra (y la resultante fuerza de Coriolis) hacen que esta disminuci´ on de velocidad redunde a su vez en un cambio de la direcci´on en la que sopla el viento, seg´ un el modelo de la espiral que Ekman introdujo en un articulo cl´asico de 1905 [8]. La espiral se ilustra en la Figura 5.2. As´ı, en el hemisferio sur, el viento de superficie est´a desfasado en sentido horario respecto del viento de altura. La Tabla 5.1 resume los valores m´as significativos de la espiral de Ekman. La diferencia entre las valuaciones sobre tierra y sobre agua corresponde a la diferencia de fricci´on que existe cuando el viento circula sobre uno u otra. Esta discordancia valid´o la decisi´on comentada en la Secci´ on 5.1.2 de no utilizar datos sensados en tierra a pesar de que las mediciones tuvieran buena calidad. La condici´on esencial que afecta la cantidad y calidad de las r´afagas es la estabilidad del aire en la capa m´as baja de la atm´osfera. El concepto de estabilidad se refiere a la cantidad de movimiento vertical que se produce entre las diferentes capas de aire atmosf´erico. Figura 5.2: Espiral de Ekman (hemisferio sur)

(a) Estabilidad

(b) Inestabilidad

Figura 5.3: Corte de las capas atmosf´ericas seg´ un el grado de estabilidad

Mart´ınez, Sainz–Tr´ apaga

P´agina 57 de 82

En condiciones estables como las de la Figura 5.3a, los estratos se comportan de manera independiente, con las capas m´ as bajas presentando intensidades de viento m´as reducidas y una direcci´ on desfasada seg´ un la espiral de Ekman. En este tipo de situaci´on, es muy dif´ıcil que se produzcan r´ afagas y variaciones aleatorias en la direcci´on e intensidad del viento de superficie. En condiciones inestables, se producen movimientos convectivos que “mezclan” las capas entre s´ı. Aqu´ı, es mucho m´ as f´ acil que una masa de aire de altura descienda de forma turbulenta hacia la superficie arrastrada por una celda de convecci´on. Este fen´omeno causa las r´afagas que los navegantes experimentan en la superficie, y que son las que originan las fluctuaciones aleatorias de direcci´ on e intensidad en el viento durante las regatas. Estas r´ afagas, que son en esencia una tajada de viento de altura que se abre paso hacia la superficie, descienden de forma abrupta, chocan con el agua y se propagan por la superficie hasta que por efecto de la fricci´on pierden su velocidad y direcci´ on caracter´ıstica, mezcl´andose con el viento de superficie lindante. Dicha propagaci´on tiene forma de un frente de onda de mayor intensidad. En High Performance Sailing, Bethwaite describe una estructura similar [3]. Enguix hace lo propio en su libro [11]. A su vez, es posible encontrar evidencia de esta caracterizaci´on en fotos satelitales de alta resoluci´ on tomadas sobre espejos de agua. La Figura 5.4 es un ejemplo, donde el viento de mayor intensidad “arruga” la superficie del agua formando peque˜ nas olas que reflejan la luz del sol y describen la forma de la racha.

Figura 5.4: R´afaga de viento en el embalse Exequiel Ram´os Mej´ıa (Neuqu´en, Argentina)

A partir de esta concepci´ on, Enguix nos transmiti´o varias ideas que nos sirvieron de base para la construcci´ on de un modelo: Las r´ afagas no pueden superar en intensidad al viento de gradiente, que es seg´ un la espiral de Ekman un 50 % superior al de superficie sobre el agua. Las r´ afagas tienen por lo general la direcci´on inicial del viento de gradiente, que est´a desfasado unos 15o en sentido antihorario respecto del de superficie. Las r´ afagas golpean la superficie y se propagan de forma expansiva con un ´angulo de aproximadamente 60o y un tama˜ no que depende del grado de inestabilidad de la atm´osfera. Las r´ afagas se propagan por la superficie a la velocidad del viento que las compone. Caracter´ıstica Tiempo estimado entre rachas ´ Area abarcada por las rachas Aumento sobre viento base ´ Angulo de desv´ıo sobre base

Inestabilidad baja

Inestabilidad media

8-10 minutos 50-100 metros 10 % 5o -10o

2-3 minutos 100-200 metros 30 % 10o -15o

Inestabilidad alta 1 minuto 400-500 metros 50 % 30o -40o

Tabla 5.2: Par´ ametros estimativos para escenarios

Adem´ as, desde su condici´ on de experto del dominio nos proporcion´o informaci´on cuantitativa basada en su experiencia de algunos par´ametros relativos a las r´afagas, que agrupamos en tres escenarios representativos de la meteorolog´ıa caracter´ıstica del R´ıo de la Plata (Tabla 5.2).

Mart´ınez, Sainz–Tr´ apaga

P´agina 58 de 82

Figura 5.5: Secuencia de una racha impactando sobre el agua Los par´ ametros involucrados son: El tiempo estimado entre rachas, que corresponde a la esperanza del tiempo que un navegante espera entre el momento en que percibe una racha y percibe la siguiente. El ´ area abarcada por las r´ afagas, que corresponde a la expansi´on geogr´afica en la que el viento de superfice se ve modificado por acci´on de una corriente de aire descendente de una capa superior. El aumento sobre el viento base, que es la variaci´on porcentual de intensidad que es esperable observar cuando una racha de viento alcanza a un observador. El ´ angulo de desv´ıo sobre el viento base, que es la diferencia respecto de la direcci´on del viento de base (en sentido horario u antihorario) que puede causar una r´afaga. Con la colaboraci´ on de Enguix construimos una secuencia de im´agenes que describen la propagaci´ on de una racha de modo cualitativo, de acuerdo a nuestra experiencia conjunta. La misma se exhibe en la Figura 5.5. En la figura, las zonas oscuras son las que perciben un incremento en la intensidad de viento, mientras que las zonas claras perciben una disminuci´on. Las zonas con el tono gris utilizado para el fondo no influyen de ninguna manera sobre el viento de base. La modificaci´on que la racha produce sobre la direcci´ on del viento se establece en funci´on de la distancia al centro de la racha, lo que resulta coherente con la expansi´on que se produce cuando ´esta golpea el agua. La secuencia de la Figura 5.5 se parametriza seg´ un los valores establecidos en la Tabla 5.2 para ajustarla al escenario que se desea modelar. Repitiendo este proceso e incorporando variaciones aleatorias en los par´ ametros puede generarse una variedad de rachas que luego se combinan con un viento de base apropiado para generar canchas simuladas con condiciones realistas de viento. As´ı, proporcionando un viento de base y generando r´afagas aleatorias seg´ un los par´ametros estipulados aqu´ı, podemos construir una variedad de simulaciones de condiciones meteorol´ogicas con r´ afagas de caracter´ısticas y distribuci´on apropiadas. Se presenta un ejemplo en la Figura 5.6. Esta propuesta es particularmente s´ olida frente a la cuesti´on de la correlaci´on espacial entre los datos que describi´ o Philpott. Dado que las rachas se construyen a partir de su estructura global, las lecturas de viento en cuadrantes contiguos siempre ser´an consistentes frente al impacto de las r´ afagas. Con esta herramienta, estamos en condiciones de generar condiciones meteorol´ogicas simuladas

Mart´ınez, Sainz–Tr´ apaga

P´agina 59 de 82

para realizar optimizaciones con nuestros algoritmos. Gracias a la comprensi´on del funcionamiento de los fen´ omenos meteorol´ ogicos involucrados, logramos un modelo cuya simulaci´on coincide con nuestra experiencia pr´ actica as´ı como con la de un experto del dominio del problema. En particular, nos interesaremos a continuaci´ on por condiciones simuladas que se encuadren en las tipolog´ıas descriptas en la Tabla 5.2, ya que son representativas de las condiciones locales del R´ıo de la Plata. Podemos con ellas realizar experimentos para evaluar el funcionamiento de nuestros algoritmos en condiciones realistas.

5.1.4.

La corriente y el barco

Los escenarios descriptos hasta el momento involucran s´ olo las caracter´ısticas referidas al viento. Las otras dos variables de entrada al modelo son la corriente y las caracter´ısticas propias de la embarcaci´on a considerar (sus curvas polares y sus costos t´ıpicos de maniobra). Para todos los escenarios que se detallan en este cap´ıtulo, se trabaj´ o sin ning´ un tipo de corriente. Si bien es importante que el modelo considere este factor (sobre todo en aras de no perder generalidad y ser utilizable en regatas de larga distancia tanto como de corta distancia), introducir esta variable extra complica sustancialmente la evaluaci´ on de los resultados.

Figura 5.6: R´afaga simulada de viento en un escenario para optimizaci´on

En la medida en que se eval´ uen regatas de corta distancia, la corriente ser´a por lo general uniforme para todos los participantes, ya que los flujos de agua en r´ıos, lagos o mares son por lo general de una extensi´ on espacial significativa. Si adem´as consideramos que las regatas son suficientemente breves como para que no pueda producirse un cambio de marea24 las condiciones ser´ an constantes y homog´eneas durante todo el per´ıodo analizado. En principio, no parece que una condici´ on homog´enea para todos los participantes pueda aventajar a uno sobre otro. Por esta raz´ on, despreciamos el efecto de la corriente en todos los experimentos, relegando el an´alisis de este factor para trabajos futuros. Maniobra Virada Trasluchada Derivada Orzada

Costo (en segundos) 5.0 2.6 1.3 1.3

Tabla 5.3: Costos asignados a las maniobras Respecto de la embarcaci´ on a analizar, utilizamos las curvas polares caracter´ısticas de un velero clase Farr 36, un barco moderno de regatas de 36 pies de eslora25 cuyas polares caracter´ısticas est´an disponibles en Internet, y que ya se exhibieron parcialmente en la Figura 1.7. Los costos de las maniobras fueron asignados manualmente seg´ un la Tabla 5.3 a partir de nuestra experiencia previa en barcos de caracter´ısticas similares. 24 Las

mareas astron´ omicas tienen un per´ıodo aproximado de 12 horas, por lo que esta presunci´ on resulta razonable. Longitud de un barco.

25 Eslora:

Mart´ınez, Sainz–Tr´ apaga

P´agina 60 de 82

Si bien para realizar un an´ alisis completo ser´ıa necesario trabajar a partir de barcos distintos, decidimos limitarnos a analizar un u ´nico barco para acotar la complejidad del trabajo. Por las caracter´ısticas del modelo, es de esperarse que el comportamiento del mismo sea relativamente uniforme cuando se consideran barcos comparables.

5.2.

Heur´ısticas para A*

En primer lugar vamos a observar el rendimiento de las heur´ısticas utilizadas para guiar la b´ usqueda del algoritmo exacto que utiliza informaci´on completa de los escenarios. Se presentan en primer lugar las ´ areas exploradas de la grilla del modelo, tanto por la implementaci´on b´asica del algoritmo de Dijkstra as´ı como las dos heur´ısticas que se presentaron en la Secci´on 3.1.3. Se consideraron 4 casos: Viento uniforme y constante de direcci´on 0o a 10kts (Figura 5.7) Viento uniforme girando de 0o a 20o a lo largo de la navegaci´on (Figura 5.8) Un escenario de inestabilidad media y viento base de 0o a 13 kts (Figura 5.9) Viento uniforme y constante de direcci´on 0o a 10kts y navegaci´on directa (Figura 5.10) En los tres primeros escenarios presentados los resultados obtenidos son muy similares. La implementaci´ on ingenua del algoritmo de Dijkstra explora el grafo en todas las direcciones, generando todas las rutas ´ optimas hacia todos los nodos con longitud inferior a un c0 . Cuando encuentra una ruta que termina en el nodo de destino, el algoritmo termina con la certeza de que la ruta es ´ optima. Se observa en todos los gr´ aficos correspondientes al algoritmo de Dijkstra que el ´area explorada corresponde a la contenida por la isocrona de longitud c0 : la forma descripta no es m´as que la de la curva polar de vmg para la intensidad de viento de inter´es. La heur´ıstica de distancia cartesiana sesga la b´ usqueda hacia la direcci´on en que se encuentra el destino. Si bien el ´ area explorada mantiene la forma original de la curva polar de vmg, aparece una protuberancia en la misma en la direcci´on de inter´es. Dado que la forma del ´area explorada es m´ as larga en la dimensi´ on deseada, el algoritmo encuentra el nodo de destino antes de que el ´area aumente mucho de tama˜ no, recorriendo as´ı una parte significativamente menor del grafo. La heur´ıstica de vmc tiene un rendimiento superior, a pesar de recorrer un ´area nada despreciable del grafo. Si consideramos que por la simetr´ıa de las bordejeadas, existe una ruta igualmente optima que es sim´etrica en el sentido vertical a la propuesta por el algoritmo, se deduce que el ´ area a explorar no puede ser significativamente menor al romboide que se aprecia particularmente ´ bien en la Figura 5.7c. En efecto, la superficie explorada se condice muy bien con lo que desde el conocimiento del dominio de las regatas a vela se considera el ´area razonable para realizar una bordejeada. No se exploran zonas que desde la experiencia podr´ıan considerarse sin sentido, a diferencia de las otras implementaciones. Adem´ as, a diferencia de las otras heur´ısticas que exploran ´areas de la misma forma para cualquier tipo de destino, manteniendo siempre la silueta aproximada de la curva, la heur´ıstica de vmc explora un camino particularmente angosto cuando la navegaci´on puede realizarse en forma directa y sin bordejeadas. Esta situaci´on se observa en la Figura 5.10. Los gr´ aficos siguientes son comparaciones sistem´aticas de las heur´ısticas para vientos constantes

Mart´ınez, Sainz–Tr´ apaga

(a) Algoritmo de Dijkstra

P´agina 61 de 82

(b) A∗ con heuristica Cartesiana

(c) A∗ con heuristica VMC

´ Figura 5.7: Area explorada para una cancha con viento constante 0o

(a) Algoritmo de Dijkstra

(b) A∗ con heuristica Cartesiana

(c) A∗ con heuristica VMC

´ Figura 5.8: Area explorada para una cancha con viento girando de 0o a 20o

(a) Algoritmo de Dijkstra

(b) A∗ con heuristica Cartesiana

(c) A∗ con heuristica VMC

´ Figura 5.9: Area explorada para una cancha inestable media con todos los ´ angulos posibles de navegaci´on respecto del viento. La Figura 5.12 corresponde a ejecuciones de los algoritmos para una grilla de 100 × 100 cuadrantes y n = 15 nodos por lado de cuadrante, y exhibe la cantidad de arcos visitados en el grafo para obtener la soluci´on ´optima. La Figura 5.11 muestra, para los mismos casos, el tiempo insumido por las variantes de A∗ expresado como porcentaje del tiempo utilizado por la implementaci´on ingenua del algoritmo de Dijkstra.

Mart´ınez, Sainz–Tr´ apaga

(a) Algoritmo de Dijkstra

P´agina 62 de 82

(b) A∗ con heuristica Cartesiana

(c) A∗ con heuristica VMC

´ Figura 5.10: Area explorada para navegaci´on directa con viento constante

A* con cota cartesiana A* con cota de VMC

Porcentaje del tiempo de Dijkstra

La Figura 5.12 muestra c´ omo las navegaciones que involucran bordejeadas (las que rodean a 0o y a 180o ) son notablemente m´ as costosas de resolver que aquellas en las que la navegaci´ on es directa. La heur´ıstica cartesiana presenta una mejora importante aunque aproximadamente constante para todos los rumbos de navegaci´ on. Por el contrario, la heur´ıstica de vmc presenta una mejora que es superior en los rumbos de bordejeada, y excelente en los rumbos directos. Si bien no se grafican los tiempos de ejecuci´ on, los mismos est´ an en correlaci´on perfecta con la cantidad de arcos visitados en el grafo.

50

40

30

20

10

La Figura 5.11 muestra la mejora de 0 0 50 100 150 200 250 300 350 rendimiento de los algoritmos gracias a las heur´ısticas. Como se deduc´ıa de la figura anÁngulo de navegación terior, la mejora obtenida por la heur´ıstica cartesiana es aproximadamente constante, insumiendo entre el 35 y el 50 % del tiem- Figura 5.11: Porcentaje del tiempo del algoritmo de Dijkstra en funci´on del ´angulo del viento po utilizado por el algoritmo de Dijkstra. La heur´ıstica de vmc, por su parte, insume a lo sumo el 13 % del tiempo del algoritmo de Dijkstra en los escenarios de bordejeada, mientras que obtiene un rendimiento hasta 100 veces mayor en navegaciones directas. En funci´ on de los resultados aqu´ı presentados consideramos apropiado el rendimiento de los algoritmos exactos como para proceder con el resto de la implementaci´on.

Mart´ınez, Sainz–Tr´ apaga

P´agina 63 de 82

Dijkstra A* con cota cartesiana A* con cota de VMC

0°

Millones de arcos 9 8

315°

7

45°

6 5 4 3 2 1 270°

90°

225°

135°

180°

Figura 5.12: Cantidad de arcos del grafo expresados en funci´on del ´angulo del viento

5.3.

Comportamiento del modelo

En segundo lugar examinaremos el comportamiento del modelo respecto de sus par´ametros. Evaluaremos c´ omo los cambios en los mismos afectan la precisi´on de los resultados obtenidos, la cantidad de arcos que resulta necesario explorar en el modelo (utilizando A∗ con heur´ıstica de vmc, que es la que presenta el mejor comportamiento) y el tiempo insumido para la obtenci´on de la ruta ´ optima.

5.3.1.

Cantidad de nodos por lado

Los gr´ aficos siguientes muestran el efecto que tiene el par´ametro n sobre las m´etricas mencionadas. Recordemos que n era la cantidad de nodos que se consideraban por cada lado de cuadrante. Las corridas se realizaron sobre una u ´nica instancia de cada tipo. Los dem´as par´ametros se dejaron fijos para las corridas.

Mart´ınez, Sainz–Tr´ apaga

P´agina 64 de 82

1004

Costo del camino (zoom)

Costo del camino

1000 800 600 400 200 0

0

10

20

30

40

1002 1000 998 996 994 992

50

0

Puntos por lado de cuadrante

10

20

30

40

50

Puntos por lado de cuadrante

4.5

40

4.0

35

Tiempo de ejecución (s)

Millones de arcos visitados

(a) Calidad del resultado

3.5 3.0 2.5 2.0 1.5 1.0

30 25 20 15 10 5

0.5 0.0

0 0

10

20

30

40

Puntos por lado de cuadrante

50

0

10

20

30

40

Puntos por lado de cuadrante

(b) Benchmarks de rendimiento

Figura 5.13: Influencia del par´ametro n para viento constante, A = 30

50

Mart´ınez, Sainz–Tr´ apaga

P´agina 65 de 82

910 1000

Costo del camino (zoom)

905

Costo del camino

800 600 400 200 0

900 895 890 885 880 875 870

0

5

10

15

20

25

865

30

5

0

Puntos por lado de cuadrante

10

15

20

25

30

Puntos por lado de cuadrante

(a) Calidad del resultado 450 400

12

Tiempo de ejecución (s)

Millones de arcos visitados

14

10 8 6 4 2

350 300 250 200 150 100 50

0

0 0

5

10

15

20

25

Puntos por lado de cuadrante

30

5

0

10

15

20

25

Puntos por lado de cuadrante

(b) Benchmarks de rendimiento

Figura 5.14: Influencia del par´ametro n para condiciones inestables, A = 30

30

Mart´ınez, Sainz–Tr´ apaga

P´agina 66 de 82

Los experimentos para verificar la calidad de los resultados son relevantes en la medida en que por la complejidad del modelo resulta muy dif´ıcil acotar los errores cometidos producto de discretizar variables. Las Figuras 5.13a y 5.14a muestran que si bien el error cometido por usar una discretizaci´ on demasiado gruesa es peque˜ no en relaci´on con la soluci´on, a medida que aumenta el valor de n el mismo se reduce hasta estabilizarse. En resumidas cuentas, el an´alisis parece indicar que en condiciones veros´ımiles (como las de escenario inestable de la Figura 5.14a) un valor de n = 30 parece ser m´ as que suficiente. Si bien en una situaci´on hipot´etica de viento constante se observan mejoras al aumentar m´ as el valor, la magnitud de las mismas es muy peque˜ na. Respecto de los benchmarks de las Figuras 5.13b y 5.14b, observamos el impacto predicho por la complejidad te´ orica del algoritmo. Aumentar n aumenta linealmente la cantidad de nodos (como se explic´ o en la Secci´ on 2.2.2). A su vez, cada cuadrante tiene una cantidad cuadr´atica de arcos, lo que ocasiona a su vez que el aumento de n tenga un impacto cuadr´atico en la cantidad de arcos totales del grafo, lo que redunda en la progresi´on observada en las figuras. Una vez m´ as, y al igual que en el apartado anterior, se observa una correspondencia muy fuerte entre la cantidad de arcos visitados por el algoritmo de camino m´ınimo y el tiempo insumido. Se desprende que el n´ umero de arcos es el mayor condicionante del tiempo de ejecuci´on del algoritmo.

5.3.2.

Cantidad de cuadrantes

En tercer lugar se analiz´ o el impacto del aumento del par´ametro A, que gobierna el tama˜ no total de la grilla de discretizaci´ on del modelo, y por lo tanto afecta directamente la cantidad de ´ cuadrantes. Este par´ ametro fue descripto en la Secci´on 2.2.1. Dado que el valor de A describe el lado de la grilla, afecta cuadr´ aticamente la cantidad de nodos del grafo puesto que el modelo subdivide el ´ area de inter´es en A × A cuadrantes. Los dem´as par´ametros se dejaron fijos para las corridas. No se analizaron en este caso escenarios que no fuesen constantes ya que al modificar la resoluci´ on de la grilla, se afecta significativamente el modelo a resolver, introduciendo as´ı variaciones dif´ıciles de controlar. Por otro lado, en general la resoluci´on de la grilla a utilizar no es realmente una variable libre para ajustar, sino que est´a condicionada por la disponibilidad de datos meteorol´ ogicos o de pron´ ostico. Seg´ un lo predicho por la complejidad algor´ıtmica, se observa en la Figura 5.15 una progresi´on polinomial en la cantidad de arcos visitados, acompa˜ nada por otra id´entica en el tiempo de ejecuci´on insumido. Al igual que para n, el valor de A tiene un fuerte impacto sobre el rendimiento de los algoritmos.

5.3.3.

Cantidad de tiempos de cambio

Por u ´ltimo, evaluamos el impacto del aumento en la resoluci´on temporal de los datos meteorol´ ogicos que proporcionamos al modelo. Aqu´ı se modific´o la cantidad de muestras de vientos para toda la superficie de inter´es por unidad de tiempo. La cantidad de tiempos de cambio se reparte de forma uniforme en la duraci´ on total del escenario que se somete a optimizaci´on, que abarca un lapso de 2500 segundos. Durante ese per´ıodo, la direcci´on del viento rota a velocidad uniforme desde los 0o hasta los 20o .

Mart´ınez, Sainz–Tr´ apaga

P´agina 67 de 82

16 14

Tiempo de ejecución (s)

Millones de arcos visitados

2.0

1.5

1.0

0.5

12 10 8 6 4 2

0.0

0 0

10

20

30

40

50

0

Cuadrantes por lado de la cancha

10

20

30

40

50

Cuadrantes por lado de la cancha

Figura 5.15: Benchmarks de rendimiento para viento constante, n = 10

45 40

0.9

Tiempo de ejecución (s)

Millones de arcos visitados

1.0

0.8 0.7 0.6 0.5 0.4

35 30 25 20 15 10 5

0.3

0 0

10

20

30

40

Resolución temporal

50

0

10

20

30

40

Resolución temporal

Figura 5.16: Benchmarks de rendimiento con viento girando, n = 10

50

Mart´ınez, Sainz–Tr´ apaga

P´agina 68 de 82

Como se discuti´ o en la Secci´ on 3.1.2, cada vez que en la b´ usqueda realizada por el algoritmo se desea evaluar el costo de un arco, por la conversi´on a grafo fifo se debe verificar una cantidad lineal de tiempos posibles en busca de un m´ınimo tiempo necesario para realizar la transici´on. Esta minimizaci´ on explora todas las combinaciones factibles de esperas y avances en tiempos futuros. En raz´ on de esto es esperable la relaci´ on lineal que se observa en la Figura 5.16 entre la cantidad de tiempos de cambio en los datos de entrada y el tiempo del algoritmo de optimizaci´on. Resulta m´ as llamativa la brusca disparidad entre esta variable y la cantidad de arcos que visita la implementaci´ on de A∗ . La explicaci´ on es sencilla: si bien la resoluci´on temporal aumenta, la longitud esperada de un arco en el grafo no se ve afectada, ya que la condiciona esencialmente el valor del par´ ametro A. Pasado un cierto nivel de resoluc´ı´on, el algoritmo no percibe mejoras en la ruta: una vez que la duraci´ on de los intervalos de tiempo cae muy por debajo del tiempo necesario para recorrer un arco, la ruta ´ optima dejar´a de variar y por lo tanto la cantidad de ejes explorados se estabilizar´ a. Estas observaciones son relevantes ya que demuestran que el aumento en la resoluci´on temporal tiene un costo apreciable respecto del tiempo de ejecuci´on de los algoritmos, pero sin embargo este incremento no vendr´ a necesariamente acompa˜ nado de una mejora en la precisi´on de la ruta: la misma puede verse limitada por el valor de A.

5.4. 5.4.1.

Heur´ısticas Modelo para experimentaci´ on

A partir de lo estipulado en la Secci´on 5.1.3, decidimos construir una serie de escenarios que consideramos representativos para la evaluaci´on de la calidad de las heur´ısticas que presentamos en 4. Recordemos las siglas que utilizaremos para referirnos a ellas: P: vmg ponderado (sim´etrico) PA: vmg ponderado (asim´etrico) PD: vmg y distancia ponderada (sim´etrico) PDA: vmg y distancia ponderada (asim´etrico) VPBF: Viento promedio (boya ficticia) VPI: Viento promedio (boya infinita) Para los criterios que tienen dos versiones, consideraremos que el criterio es asim´etrico cuando sus par´ ametros son distintos para cada amura. De lo contrario lo consideraremos sim´etrico. De esta forma separamos los criterios, ya que faltando esta consideraci´on los criterios sim´etricos son un caso particular de un criterio asim´etrico.

5.4.1.1.

Optimizaci´ on de los par´ ametros

Una vez establecido el marco para la experimentaci´on, el primer paso consisti´o en buscar valores apropiados de los par´ ametros de cada heur´ıstica para obtener un buen rendimiento. Para esto,

Mart´ınez, Sainz–Tr´ apaga

P´agina 69 de 82

Figura 5.17: Tiempo promedio para distintas configuraciones de p´arametros para el criterio pd consideramos para cada criterio rangos razonables para los valores de sus par´ametros y probamos las distintas combinaciones de los mismos en un procedimiento anidado. Esta b´ usqueda se realiz´ o inicialmente con una granularidad baja, y posteriormente cuando se encontr´ o la combinaci´ on de valores de mejor comportamiento, se realizaron refinamientos progresivos en intervalos m´ as peque˜ nos. Para la evaluaci´on del comportamiento en funci´on de los par´ametros recurrimos a un subconjunto de los escenarios descriptos anteriormente: utilizamos u ´nicamente las 200 canchas con condiciones inestables medias y viento promedio de 0o , por considerar que son las m´ as representativas y generales. Como m´etrica para la valuaci´on de los par´ametros, buscamos minimizar el tiempo promedio obtenido por las heur´ısticas en todas las simulaciones. La Figura 5.17 ilustra los resultados de la optimizaci´on para la heur´ıstica pd. Cuanto m´as oscuro es el color de un punto, mejor fue el resultado obtenido por la heur´ıstica en las simulaciones. Se observa en la Figura que hay una franja diagonal de valores buenos (que aparecen de color negro), rodeados por valores de peor comportamiento. Esta franja se extiende mas all´a de los valores de cd mostrados. Sin embargo, a medida que el coeficiente cd aumenta, observamos que la franja se angosta. Esto implica que la calidad de la heur´ıstica es muy sensible a peque˜ nas variaciones de los par´ ametros. Tras hacer esta observaci´ on, consideramos que estos valores tan ajustados podr´ıan no ser apropiados en escenarios levemente distintos a los inestables medios que utilizamos para este caso. Decidimos entonces conservar el o´ptimo dentro del rango graficado.

Mart´ınez, Sainz–Tr´ apaga

Heur´ıstica P PD PA PDA VPBF VPI

P´agina 70 de 82

cv

cd

cve

cvb

cde

3.50 -1.80 -

6900.00 -

3.20 -0.40 2.45 0.40

2.80 1.20 1.45 1.30

2900.00 1600.00 1400.00

cdb 2300.00 1600.00 0.00

Tabla 5.4: Par´ ametros ´optimos para las distintas heur´ısticas El procedimiento descripto se realiz´o para todas las heur´ısticas presentadas, obteniendo los valores que se exhiben en la Tabla 5.4.

5.4.1.2.

Comparaci´ on de las heur´ısticas

Una vez obtenidos valores apropiados para los par´ametros, procedimos a comparar las cualidades de los diferentes criterios. Una vez m´as, realizamos las comparaciones en canchas de condiciones inestables medias, utilizando diversas m´etricas. La mayor´ıa de las mismas son sencillas de comprender, pero corresponde aclarar la m´etrica de puntos acumulados. En ella se utiliz´o el sistema de puntuaci´ on que se utiliza en campeonatos de vela para asignar puntajes en un conjunto de regatas. La cantidad de puntos que le corresponden a cada participante por cada regata son los de la posici´ on que obtuvo en la misma: el ganador recibe 1 punto, el segundo 2, y as´ı sucesivamente. El ganador del campeonato ser´ a el participante que acumule la menor cantidad de puntos al completarse todas las regatas. Los resultados de estas comparaciones se observan en las Figuras 5.18, 5.19, 5.20 y 5.21. La primera constataci´ on es que en general los criterios se comportaron relativamente bien, alcanzando errores relativos promedio del orden de entre el 4 y el 7 %. Adem´as, se desprende del an´alisis de los resultados que el criterio vpi tiene un comportamiento considerablemente mejor que los dem´as. A partir de estos resultados, decidimos poner el mayor ´enfasis en la heur´ıstica vpi para continuar haciendo experimentos m´ as extensivos en otros escenarios, por lograr ´esta resultados marcadamente superiores a los de las dem´ as. A fin de poder contrastar sus resultados, conservamos a su vez para experimentos futuros a la heur´ıstica pd, por utilizarse variantes de la misma con mucha frecuencia en el ambiente n´ autico. Introdujimos a su vez una nueva heur´ıstica que llamamos pdd, correspondiente a la utilizaci´on de par´ ametros malos de la heur´ıstica pd que la hacen comportarse de forma particularmente ingenua. La estrategia resultante de pdd corresponde a la actitud que tendr´ıa un navegante que se inicia: navegar en un mismo borde hasta tanto considere que el borde opuesto lograr´a llevarlo directamente a su destino, y reci´en en ese momento realizar su primera (y posiblemente u ´nica) virada. La Figura 5.22 exhibe las rutas propuestas por las heur´ısticas para las 200 canchas inestables medias, mientras que la Figura 5.23 presenta los puntos en que los algoritmos consideraron conveniente realizar viradas. Es dif´ıcil observar alg´ un tipo de patr´on en las rutas ´optimas. Tanto los bordes como las viradas

Tiempo promedio (segundos)

Mart´ınez, Sainz–Tr´ apaga

P´agina 71 de 82

940

920

900

880

860

Óptimo

P

PA

PD

PDA

VPBF

VPI

Diferencia con el tiempo óptimo (%)

Figura 5.18: Tiempo promedio de las rutas para condiciones de inestabilidad media

7 6 5 4 3 2 1 0 P

PA

PD

PDA

VPBF

VPI

Figura 5.19: Diferencia relativa promedio con el tiempo ´optimo bajo inestabilidad media

Mart´ınez, Sainz–Tr´ apaga

P´agina 72 de 82

Diferencia con el tiempo óptimo

60

50

40

30

20

10

0 P

PA

PD

PDA

VPBF

VPI

Figura 5.20: Diferencia absoluta promedio con el tiempo ´optimo bajo inestabilidad media

1000

Puntos acumulados

800

600

400

200

0 P

PA

PD

PDA

VPBF

VPI

Figura 5.21: Cantidad de puntos obtenidos compitiendo con inestabilidad media

Mart´ınez, Sainz–Tr´ apaga

´ (a) Optimos

P´agina 73 de 82

(b) VPI

(c) PD

(d) PDD

Figura 5.22: Recorridos para las 200 canchas de condici´on inestable media

´ (a) Optimos

(b) VPI

(c) PD

Figura 5.23: Viradas para las 200 canchas de condici´on inestable media

(d) PDD

Mart´ınez, Sainz–Tr´ apaga

P´agina 74 de 82

se distribuyen de forma relativamente uniforme en toda la cancha de regatas, en consonancia con la uniformidad de la distribuci´ on de las rachas que se modelan. Dado que el algoritmo ´optimo utiliza un conocimiento completo de las condiciones de viento, es capaz de seleccionar rutas que una heur´ıstica dif´ıcilmente pueda adivinar: trabajan con conjuntos de informaci´on esencialmente distintos. La heur´ıstica pdd exhibe el comportamiento descripto antes, realizando por lo general una u ´nica virada. Esta es la estrategia trivial para este tipo de situaci´on, y es relevante s´olo como punto de referencia para las dem´ as. Comparadas con el ´ optimo, tanto vpi como pd realizan comparativamente pocas viradas, circulando mucho por la parte exterior de la cancha de regatas en lugar de hacerlo por su parte central. Desde un punto de vista n´ autico, estas estrategias son bastante riesgosas. Un barco que circula por el borde de la cancha como lo hace (en un caso extremo) pdd puede ver arruinada su regata por un cambio de viento repentino. Sin embargo, dado que nuestros escenarios de prueba no incorporan cambios permanentes de viento sino que se centran en oscilaciones aleatorias, es razonable que los par´ ametros de mejor comportamiento sean relativamente arriesgados, realizando pocas viradas y navegando hasta los bordes: esta reducci´on en la cantidad de viradas les permite ahorrar valiosos segundos de navegaci´ on. Vpi exhibe una preferencia superior por el lado izquierdo de la cancha. Esto se condice con que el viento base utilizado para generar los escenarios favorece levemente ese lado, ya que se encuentra unos grados por debajo del viento promedio. Ello se debe a que por lo descripto en 5.1.3, las rachas se encuentran por lo general algunos grados por encima del promedio. Es probablemente esta diferencia la que le permite vencer de forma sistem´atica a la heur´ıstica pd. Los mismos experimentos realizados para canchas de condiciones inestables medias con viento base 0o se realizaron para canchas inestables y estables con viento base 0o , e inestables medias pero con viento base 20o . Para estos experimentos mantuvimos los par´ametros de los criterios con los mismos valores que obtuvimos luego de optimizarlos con las canchas inestables medias. En general, todos los resultados apuntan en la misma direcci´on: la heur´ıstica vpi se comporta muy bien, en general mucho mejor que los dem´as criterios y de forma muy consistente. Se mantiene adem´ as muy cerca de los valores del ´ optimo, una caracter´ıstica muy buena si tenemos en cuenta que trabaja con un subconjunto muy reducido de la informaci´on que utiliza este u ´ltimo. En las canchas estables (Figura 5.25) se ve c´ omo el criterio logra estar muy cerca del ´optimo, teniendo un gap de optimalidad promedio de menos del 2 %. En el caso de las canchas de condiciones inestables medias con viento base 20o (cuyos resultados se muestran en la Figura 5.26) se hace m´as marcada la tendencia, logrando vpi estar a menos de un 4 % de la soluci´on ´optima, contra casi un 6 % de las otras heur´ısticas. Por u ´ltimo, es importante se˜ nalar la diferencia abismal que existe entre los tiempos de ejecuci´on de las heur´ısticas y los algoritmos exactos. En la Tabla 5.5 se resumen los tiempos26 de ejecuci´on promedio, los tiempos de las rutas obtenidas, la diferencia promedio con el recorrido ´optimo, el porcentaje del tiempo ´ optimo y el desv´ıo est´andar de dicho porcentaje. Toda esta informaci´on corresponde a corridas realizadas sobre canchas de condiciones inestables medias con viento base 0o . 26 Estas pruebas fueron realizadas en una configuraci´ on de hardware diferente al resto de las pruebas, por lo que los tiempos de ejecuci´ on difieren a los presentados antes

Mart´ınez, Sainz–Tr´ apaga

P´agina 75 de 82

12 Diferencia con el tiempo óptimo (%)

Tiempo promedio (segundos)

980 960 940 920 900 880 860 840 820 800

Óptimo

PDD

PD

4 2

PD

PDD

VPI

600

80

500

70 Puntos acumulados

Diferencia con el tiempo óptimo

6

(b) Diferencia relativa promedio con el tiempo o ´ptimo ( %) en condiciones inestables

90

60 50 40 30 20

400 300 200 100

10 0

8

0

VPI

(a) Tiempo promedio de las rutas para las canchas de condiciones inestables

10

PD

PDD

VPI

(c) Diferencia absoluta promedio con el tiempo ´ optimo en condiciones inestables

0

PD

PDD

VPI

(d) Cantidad de puntos obtenidos por regatas en condiciones inestables

Figura 5.24: Condiciones inestables

Mart´ınez, Sainz–Tr´ apaga

P´agina 76 de 82

12 Diferencia con el tiempo óptimo (%)

Tiempo promedio (segundos)

980 960 940 920 900 880 860 840 820 800

Óptimo

PDD

PD

4 2

PDD

PD

VPI

600

80

500

70

Puntos acumulados

Diferencia con el tiempo óptimo

6

(b) Diferencia relativa promedio con el tiempo o ´ptimo ( %) en condiciones estables

90

60 50 40 30 20

400 300 200 100

10 0

8

0

VPI

(a) Tiempo promedio de las rutas para las canchas de condiciones estables

10

PDD

PD

VPI

(c) Diferencia absoluta promedio con el tiempo ´ optimo en condiciones estables

0

PD

PDD

VPI

(d) Cantidad de puntos obtenidos por regatas en condiciones estables

Figura 5.25: Condiciones estables

Mart´ınez, Sainz–Tr´ apaga

P´agina 77 de 82

12 Diferencia con el tiempo óptimo (%)

Tiempo promedio (segundos)

980 960 940 920 900 880 860 840 820 800

Óptimo

PDD

PD

4 2

PDD

PD

VPI

600

80

500

70

Puntos acumulados

Diferencia con el tiempo óptimo

6

(b) Diferencia relativa promedio con el tiempo o ´ptimo ( %) en condiciones inestables medias 20o

90

60 50 40 30 20

400 300 200 100

10 0

8

0

VPI

(a) Tiempo promedio de las rutas para las canchas de condiciones inestables medias 20o

10

PDD

PD

VPI

(c) Diferencia absoluta promedio con el tiempo ´ optimo en condiciones inestables medias 20o

0

PD

PDD

VPI

(d) Cantidad de puntos obtenidos por regatas en condiciones inestables medias 20o

Figura 5.26: Condiciones inestables medias 20o

Mart´ınez, Sainz–Tr´ apaga

Heur´ıstica Algoritmo de Dijkstra A* euclidiana A* vmc PD PDD VPI

P´agina 78 de 82

T ejec

T rec

T − T∗

%T ∗

124.60 93.40 83.20 0.05 0.04 0.04

884.02 884.02 884.02 927.90 938.00 916.40

0.00 0.00 0.00 43.90 54.26 32.43

100.00 100.00 100.00 104.90 106.17 103.60

σ %T ∗ 0.00 0.00 0.00 2.52 2.74 2.42

Tabla 5.5: Resumen de benchmarks de heur´ısticas y algoritmos exactos

Notemos que si bien la heur´ıstica vpi est´a a alrededor de 4 % en promedio de la soluci´on ´ptima, su tiempo de ejecuci´ o on es mas de 3000 veces m´as peque˜ no. Esta diferencia de rendimiento la hace aplicable para su utilizaci´ on en tiempo real, en conexi´on directa con los instrumentos de una embarcaci´ on que le proveen de toda la informaci´on que necesita. Estas caracter´ısticas hacen que pueda convertirse en una valiosa herramienta para un estratega embarcado.

Mart´ınez, Sainz–Tr´ apaga

P´agina 79 de 82

Cap´ıtulo 6

Conclusiones 6.1.

Balance del trabajo

En este trabajo implementamos un modelo m´as general que los utilizados en el software comercial, obteniendo as´ı la posibilidad de extender su uso para situaciones de regatas de corta distancia en que el costo de las maniobras pueda resultar significativo. La cota de vmc descripta para el algoritmo A∗ en la Secci´on 3.1.3.2 exhibe un comportamiento muy interesante, explorando u ´nicamente el ´area del grafo que es realmente pertinente a la navegaci´ on que se espera del barco. Este resultado, adem´as de habernos permitido realizar experimentos de forma muy r´ apida para el ajuste de las heur´ısticas, puede ser transferido a las aplicaciones de ruteo de larga distancia convencional, a las que puede significarles una mejora significativa de rendimiento. Las heur´ısticas que desarrollamos para tomar decisiones de ruteo on-line reflejan en gran medida el conocimiento popular de los regatistas del medio local. Entre ellas, se destaca el comportamiento de la heur´ıstica vpi de la Secci´ on 4.3.4, que logra por lo general resultados que se encuentran a un 4 % del ´ optimo utilizando s´ olo la informaci´on accesible por los instrumentos del barco. A su vez, logran esto con cantidades m´ınimas de tiempo de c´omputo, haciendo posible su implementaci´on para su uso en tiempo real durante la navegaci´on. Por u ´ltimo, el modelo de simulaci´ on de canchas que desarrollamos, si bien parte de conocimiento experto y no del an´ alisis de mediciones reales, es m´as sofisticado que los presentados hasta el momento en la literatura porque ataca directamente el problema de correlaci´on espacial enunciado por Philpott. As´ı, es un buen punto de partida para su ajuste con datos concretos y la experimentaci´on futura.

6.2.

Trabajos futuros

Sin duda la extensi´ on m´ as interesante al trabajo realizado hasta el momento es el pasaje a la pr´ actica de las heur´ısticas que exhibieron buen comportamiento para poder ajustarlas y observar su desempe˜ no en condiciones reales de regata. Para ello, es necesario valerse de una interfaz simple con instrumental n´ autico, lo que hace que el proyecto sea relativamente modesto en cuanto a su complejidad. Otra alternativa posible es trabajar en la sofisticaci´on del modelo de simulaci´on de canchas de regata para ajustarlo a datos reales, realizando as´ı un an´alisis formal que permita validar emp´ıricamente al modelo como fuente de escenarios para regatas.

Mart´ınez, Sainz–Tr´ apaga

P´agina 80 de 82

En tercera instancia, si bien la corriente fue descartada de nuestro marco experimental, ser´ıa interesante evaluar el impacto de la misma sobre el funcionamiento tanto de los algoritmos exactos como de las heur´ısticas. Si bien el factor de la corriente es m´as relevante en ruteo de larga distancia, por las caracter´ısticas generales de nuestro modelo, esta l´ınea est´a abierta a futuros desarrollos. Desde el punto de vista te´ orico, hay algunas ideas que vale la pena explorar. Nuestro modelo se centra u ´nicamente en navegaciones entre un origen y un destino. Por las caracter´ısticas habituales de las regatas entre boyas, las distintas piernas son esencialmente independientes entre s´ı y el modelo funciona perfectamente sobre ellas trat´andolas de forma secuencial. Sin embargo, muchas regatas de marcas fijas tienen recorridos m´as complejos en los que dependiendo de la navegaci´on que sea conveniente hacer, puede no resultar necesario pasar por una marca intermedia. El modelo puede generalizarse para contemplar estas situaciones realizando un grafo organizado por niveles. Una opci´ on m´ as es la de revisar la discretizaci´on propuesta para el espacio navegable. La misma est´ a bien adaptada al formato de los pron´osticos de tipo grib, que por lo general utilizan una malla uniforme. Resulta adem´ as apropiada para la navegaci´on en extensiones de agua sin obst´aculos. Sin embargo, en situaciones donde existieran obst´aculos de morfolog´ıa compleja (islas, bancos de arena, etc), para obtener una descripci´ on fiel de estos u ´ltimos ser´ıa necesario aumentar mucho la resoluci´on de la grilla, con el consiguiente costo computacional. Una grilla adaptativa (como por ejemplo, la resultante de una triangulaci´ on de Delaunay) podr´ıa ofrecer caracter´ısticas m´as adecuadas para estas situaciones.

Mart´ınez, Sainz–Tr´ apaga

P´agina 81 de 82

Referencias [1] Adrena, 2010, Adrena, http://www.adrena.fr/ [2] F. Bethwaite, 1996, Sailing the Wind Patterns, High Performance Sailing, 12(119), Adlard Coles Nautical. [3] F. Bethwaite, 1996, Sailing the Wind Patterns, High Performance Sailing, 5(39), Adlard Coles Nautical. [4] b&g, 2008, Deckman 9.1 , http://www.bandg.com/ [5] E. W. Dijkstra, 1959, A note on two problems in connexion with graphs. Numerische Mathematik 1: 269–271. [6] Lic. Maria Eugenia Dillon, meteor´ ologa, Comunicaci´on personal. [7] S.E. Dreyfus, 1969, An appraisal of some shortest-path algorithms, Operations Research 17(3), 395–412. [8] V. W. Ekman ,1905, On the Influence of the Earth’s Rotation on Ocean-Currents, Arkiv foer matematik. astronomi o. fysik., Vol. 11. [9] A. Enguix, 2010, Comunicaci´ on personal. [10] A. Enguix, 2006, Curso de Vela, en tres tomos, Ediciones Granica. [11] A. Enguix, 2010, El pr´ oximo role, NEW Visiones [12] A. Enguix, 2003, Viento: Pron´ ostico y estrategia para Regata y Crucero, Editorial puma. [13] Empopado, http://www.empopado.com/ [14] M. L. Fredman, R.R. Tarjan, 1987, Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596-615. [15] B. Gladstone, 1983, Performance Racing Tactics, North U. [16] H.J. Halpern, 1977, Shortest route with time dependent length of edges and limited delay possibilities in nodes, Operations Research 21, 117–124. [17] P. E. Hart, N.J. Nilsson, B. Raphael, 1968, A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100–107. [18] P.E. Hart, N.J. Nilsson, B. Raphael, 1972, Correction to “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. SIGART Newsletter 37: 28–29. [19] E. Kanoulas, Y. Du, T. Xia, D. Zhang, 2006, Finding fastest paths on a road network with speed patterns, Proc. ICDE 06 10-19. [20] D.E. Kaufman, R.L. Smith, 1993, Fastest paths in time-dependent networks for intelligent vehicle-highway systems application, J. Intelligent Transportation Systems 1(1), 1–11. [21] J.E. Kerwin, J.N. Newman, 1979, A Summary of the H. Irving Pratt Ocean Race Handicapping Project, Proceedings of the Chesapeake Sailing Yacht Symposium.

Mart´ınez, Sainz–Tr´ apaga

P´agina 82 de 82

[22] A. Orda, R. Rom, 1990, Shortest-path and minimum-delay algorithms in networks with timedependent edge-length, J. ACM 37(3), 607–625. [23] A. Orda, R. Rom, 1989, Traveling without waiting in time-dependent networks is NP-hard, Manuscript, Dept. Electrical Engineering, Technion – Israel Institute of Technology, Haifa, Israel. [24] C.P. Padhy, D Sen y P.H. Bhaskaran, 2008, Application of wave model for weather routing of ships in the North Indian Ocean, Natural Hazards 44:373-385. [25] A. Philpott, A. Mason, Optimising Yacht Routes under Uncertainty, Proceedings of the 15th Chesapeake Sailing Yacht Symposium. [26] A. Philpott, 2005, Optimal Routing under Uncertainty, Applications of Stochastic. Programming 17, 315-335 [27] Pilote Norden, http://www.riovia.com/fotonor.php [28] Pilote tiba, http://www.tiba.com/weather/index.php [29] M. Rushall, 2007, Tactics , Royal Yachting Association, 1.1(18). [30] H.D. Sherali, K. Ozbay, S. Subramanian, 1998, The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms, Networks 31(4), 259–272. [31] R. Stelzer, T. Pr¨ oll, 2007, Autonomous Sailboat Navigation for Shourt Course Racing, Robotics and Autonomous Systems 56(7) 604-614. [32] P.H. Stoter, 1992, Ship Weather Routeing, The Meteorologist’s Job?, Ship & Werf de Zee. 8(92) 340-343. [33] Tasman Bay Navigation Systems, 2010, Expedition 8, http://www.tasmanbaynav.co.nz/ [34] Yspots, http://www.yspots.com/ [35] WindData, http://www.winddata.com/ [36] L. Zhao, T. Ohshima, 2008, A* algorithm for the time-dependent shortest path problem. En WAAC08: The 11th Japan-Korea Joint Workshop on Algorithms and Computation.