Mapes de cobertura en entorns amb obstacles

Abstract

Aquest projecte és una continuació de la recerca realitzada al GILab de la Universitat de Girona pel doctor Narcís Coll i la doctora Marta Fort sobre problemes de cobertura de la branca de la informàtica i matemàtiques coneguda com a geometria computacional. Els problemes de cobertura tracten de, donada una distribució de serveis, determinar quines regions d’un domini queden cobertes. Hi ha variants d’optimització d’aquest problema on s’afegeixen graus de llibertat, per exemple: intentant trobar la millor distribució d’un nombre fix de serveis o la millor amb el mínim nombre possible d’aquests. En tots els casos la solució és un mapa de cobertura, una representació gràfica que ens permet determinar quines són les regions cobertes per com a mínim un servei. En aquest tipus de problemes es considera que un punt està cobert per un servei si existeix algun camí de longitud menor o igual al radi d’abast d’aquest que els connecti. En entorns sense obstacles això implica que la cobertura de cada servei sigui una circumferència del mateix radi que aquest, ja que tots els camins que arribin al servei seran línies rectes de la mateixa longitud. Quan treballem en entorns amb obstacles ja no podem assegurar que l’àrea coberta per qualsevol servei sigui sempre una circumferència. En aquest cas podem trobar-nos camins que hagin de vorejar obstacles per tal d’arribar al seu objectiu i, per tant, passin de ser rectes a poligonals que creuen per les cantonades dels obstacles. Els mapes de cobertura tenen un ampli rang d’aplicacions tant al sector públic com al privat, ja que es poden aplicar a qualsevol classe de servei que tingui un cert rang d’abast, tant real o com imposat, des de punts de càrrega de robots on podem voler que cada robot operi com a molt X distància d’un d’aquests, p. ex. robots Roomba, fins a kits de primers auxilis que volem que estiguin a un temps/distància raonable de cada sala d’un edifici. En ambdós casos estem buscant un mapa de cobertura que maximitzi aquesta. Addicionalment, aquest ens permetrà prendre decisions sobre el nombre de serveis que necessitem i la qualitat d’aquests (rang d’abast), ja que a partir del mapa podem determinar que en necessitem més o que amb menys ja en faríem prou perquè hi ha un alt nivell de coincidència. En aquest projecte es presenta una solució per l’obtenció de mapes de cobertura en entorns en obstacles basada en una modificació de l’algoritme de Bellman-Ford en paral·lel que aprofita la capacitat de còmput de la GPU i una tècnica d’optimització basada en un algoritme genètic per trobar distribucions de serveis que maximitzin la cobertura