Navegació autònoma

La navegació autònoma o robòtica és l'estudi dels sistemes que permeten que un vehicle es desplaçi cap a un objectiu, evitant obstacles automàticament, durant llargs períodes sense cap operador.

La navegació és una part fonamental dels robots autònoms mòbils que s'han de desplaçar durant llargs períodes sense un operador humà.

La navegació es divideix en quatre components bàsics: percepció, localització i mapatge, planificació de trajectòria i control de moviment. La percepció s'encarrega de percebre l'entorn del robot fent servir sensors. Aquesta informació es fa servir per definir un plànol de l'entorn i ubicar-se. Aleshores, sabent la posició inicial, l'objectiu i els obstacles del mapa es pot definir un pla de ruta. Finalment, mentre el robot segueix la trajectòria que s'ha definit, s'ha d'aplicar un control de moviment per assegurar-se que el vehicle no es desvia de la ruta. Aquest esquema pot variar lleugerament segons el sistema.

De la dècada dels 90 ençà, la navegació robòtica ha aconseguit fer grans avenços, gràcies a les investigacions per aconseguir desenvolupar un cotxe autònom. Tot i això, encara queden reptes importants per resoldre com la millora de la robustesa, la capacitat d'adaptar-se a canvis a l'ambient i la possibilitat de comprendre l'entorn.

Percepció

Un robot es pot moure de forma eficient si pot percebre, amb suficient detall, el seu entorn. Per això són necessaris sensors, que detecten els objectes de la rodalia del vehicle i generen unes senyals que permeten modelar l'entorn matemàticament. Com que no hi ha cap sensor que funcioni bé en qualsevol circumstància, generalment els vehicles autònoms fan servir un conjunt de diferents sensors. Els més habituals són lidars, radars, sonars, càmeres i càmeres d'infrarojos.

Un cotxe autònom, un Nissan Leaf modificat per l'Oxford Robotics Institute, amb LIDARs, càmeres i un radar a dins d'un radom.

Els lidar, de l'anglès LIght Detection and Ranging, poden detectar la distància que hi ha entre el robot i un obstacle mitjançant un díode emissor de llum i un fotodíode que detecta el retorn del feix làser. Fent servir principis de triangulació, temps de retorn o canvi de fase es pot calcular la distància en una direcció. Aquests sensors són molt populars, ja que tenen una alta precisió i són robusts; a més a més, si es col·loquen múltiples lidar en capçals rotatius es poden crear plànols en 2D o 3D de l'entorn.

Els radars, de l'anglès RAdio Detection and Ranging, emet ones de ràdio d'alta freqüència i en detecta el retorn, permetent obtenir lectures de distància, geometria i material de l'obstacle. Fins fa poc aquesta tecnologia era massa voluminosa i costosa per usar-se en robots, però recentment s'han començat a implementar gràcies a la miniaturització i abaratiment dels costos. Tot i oferir molta informació dels obstacles, i poder treballar en pràcticament qualsevol condició meteorològica, tenen una lleugera menor resolució de profunditat i angular respecte els lidars a causa de problemes de reflexió especular.

Els sonars, de l'anglès SOund Navigation and Ranging, es fan servir com a principal sensor en aplicacions submarines però també es poden emprar a la superfície. En aquest cas, s'emeten ones sonores mecàniques i es calcula la distància detectant el temps de retorn. En aquest cas, comparat amb els radars i lidars, la resolució angular i de profunditat és molt menor a causa de la reflexió especular, baixa velocitat d'ona, atenuació i interferència ambiental. Per altra banda, són sensors assequibles, poc voluminosos i de baix consum.

Un robot mòbil equipat amb un LIDAR planar, un dels sensors més robusts i habituals.

Les càmeres són sensors visuals passius que capten l'espectre visible de la llum ambiental i la converteixen en dades que pot llegir un ordinador. Generalment, la llum incident a la càmera es converteix periòdicament en una matriu de mesures d'intensitat fent servir sensors CCD o CMOS. Les matrius de píxels resultants, codifiquen la intensitat de color vermell, verd i blau cada cert temps. La gran quantitat de dades generades és molt difícil de processar però actualment, gràcies als avenços en visió per computador, sol ser vital en gairebé tots els sistemes de navegació autònoma, ja que les càmeres són assequibles, compactes i tenen un baix consum respecte altres tecnologies.

Les càmeres d'infrarojos detecten les ones electromagnètiques amb freqüències entre l'espectre visible i les microones. Per detectar la radiació infraroja a mitja i llarga distància, es fan servir bolòmetres un sensor basat en l'efecte fototèrmic, la producció de calor en resposta a la radiació infraroja incident. Aquestes càmeres poden funcionar amb refrigeració, que són més sensibles a petits canvis de temperatura però necessiten sistemes addicionals, o sense refrigeració, menys sensibles però més compactes i amb menor consum. Aquests sensors tenen dos grans avantatges respecte les càmeres convencionals: poden operar en entorns sense il·luminació, ja que responen a l'energia tèrmica emesa pels objectes, i permeten diferenciar fàcilment objectes d'interès en navegació, com vehicles o persones. Per contra, generalment tenen menors resolucions, temps de resposta més lents i són menys assequibles.

Localització i mapatge

Per poder navegar o dur a terme tasques a llocs específics un vehicle no tripulat ha de saber "on és". Aquest problema s'anomena localització, i pot ser forta si s'ha d'estimar la posa del robot respecte una representació global, o feble si només s'ha de determinar si ja s'ha visitat una posició prèviament. Amb estimacions aproximades de la posició del robot, fent servir odometria, un mapa de l'entorn i uns mínims sensors de percepció és possible mantenir una estimació de la posició respecte el mapa. Com que els sensors incorporen soroll en les seves mesures, els algoritmes de localització han d'estimar la posa i també han d'oferir una mesura de la incertesa de l'estimació. Per aquest motiu, sovint s'usen processos d'estimació recursius com per exemple el filtre de Kalman o de partícules.

Mapa d'obstacles generat per un robot, blau cel, amb possibles rutes basades en diagrames de Voronoi, blau marí.

En molts casos, els robots no disposen d'un mapa de la zona on han de treballar o no tenen la posició dels obstacles de l'entorn. A més a més, fins i tot tenint un mapa, les mesures dels sensors poden diferir de les distàncies d'un mapa. El mapatge soluciona aquest problema construint, actualitzant i validant plànols que els robots puguin fer servir, i és d'una importància cabdal per una navegació efectiva. Segons el processament de les dades, un plànol es pot classificar com a:

1. Sensorial: dades sense processar o amb un processament de senyals simple.
2. Geomètric: mapa en dues o tres dimensions dels objectes d'una àrea basat en les lectures dels sensors. Els mapes geomètrics són els que la majoria de robots fan servir.
3. Relacional local: plànol que incorpora relacions funcionals, estructurals o semàntiques entre objectes geomètrics propers.
4. Topològic: mapa amb relacions de llarga distància entre tots els objectes d'un entorn.
5. Semàntic: plànol amb les descripcions funcionals de cada àrea.

Exemple d'un algorisme A* cercant la ruta òptima entre dos punts d'un mapa amb un obstacle.

SLAM

La localització i mapatge simultanis o SLAM, de l'anglès simultaneous localization and mapping, soluciona el problema de crear el mapa d'un entorn desconegut i al mateix temps localitzar la pròpia ubicació del vehicle en aquest plànol. Aquest problema, molt comú en tot tipus d'aplicacions, és crucial perquè un robot pugui navegar de forma autònoma i es van presentar les primeres solucions a la dècada dels 2000, tot i que encara queden qüestions substancials per resoldre en termes de robustesa i nivell de detall dels mapes. Les principals solucions fan ús d'un filtre de Kalman estès (EKF-SLAM), un filtre de partícules de Rao-Blackwell (FastSLAM) o SLAM visual.

Planificació de ruta

Un cop s'han recollit dades dels sensors, el robot sap on està ubicat i disposa d'un mapa, el següent pas consisteix en planificar la ruta des d'un punt A a un punt B del plànol. Els entorns es consideren estàtics, quan la ubicació de tots els obstacles és coneguda, o dinàmics, si només es té informació parcial dels obstacles abans de començar a desplaçar-se. Els entorns dinàmics són més habituals, i per evitar els obstacles se sol dividir el problema en dues parts: global i local. Les tècniques globals fan ús del mapa per trobar la ruta teòrica òptima, però la seva complexitat no permetria que el robot reaccionés ràpidament als obstacles desconeguts. Per això es fan servir les tècniques locals, més ràpides i senzilles però que no poden generar una solució òptima per si soles. Els algorismes de planificació de ruta, tant globals com locals, es poden classificar segons el mètode de cerca que fan servir:

El primer grup és el de cerca gràfica, que divideix el mapa en una quadrícula (o espai d'estats) i busca una solució intentant minimitzar el nombre de quadrats (o estats) pels quals hagi de passar el robot per arribar a l'objectiu. Generalment, són algoritmes adequats per espais coneguts a priori, però els costos de temps i memòria poden ser massa elevats per àrees extenses. Aquest grup inclou els algoritmes A*, D*, Theta* o AD*.

El segon grup són els planificadors basats en mostreig, que cerquen una solució sondejant aleatòriament l'espai d'estats i intentant connectar els estats sense obstacles. Aquests algorismes eviten definir l'espai obstaculitzat, facilitant-ne la implementació, però tenen l'inconvenient que ofereixen una solució subòptima. Els algorismes més usats són el PRM, de l'anglès probabilistic road map, i l'RRT, rapidly exploring random trees.

Exemple d'un algorisme PRM buscant possibles rutes a través d'un mapa amb obstacles poligonals.

El tercer grup són els planificadors interpoladors de corbes. Aquestes tècniques es fan servir sovint com a mètodes per donar continuïtat a les rutes planificades per altres algorismes; tenint en compte la dinàmica del vehicle, la factibilitat de la ruta o el comfort. La interpolació insereix nous punts a la ruta prèviament establerta i la suavitza. En aquest cas hi ha nombrosos mètodes, clotoides, polinomis, corbes de Bézier o splines.

El quart grup són els mètodes d'optimització numèrica. En aquest cas l'objectiu consisteix en minimitzar o maximitzar una funció matemàtica subjecta a diferents restriccions variables. Aquestes tècniques es poden fer servir per suavitzar rutes prèviament calculades o també per trobar-ne de noves fent servir restriccions cinemàtiques. La trajectòria generada pot tenir en compte moltes variables, com la velocitat, orientació, acceleració, comfort... per contra, és computacionalment costós, ja que ha d'optimitzar la funció per cada punt de la ruta.

Tot i que no no es poden emmarcar en les categories prèviament exposades, hi ha molts altres algoritmes que es fan servir en navegació robòtica. Un dels mètodes més notables i àmpliament usats sense categoria és la navegació per camps potencials. Consisteix a assignar un potencial atractiu a la posició on es vol anar, mentre que els obstacles tenen un potencial repulsiu. Amb aquests valors es pot generar una funció de navegació que segueixi el gradient que fa que el robot es mogui seguint el camí més atractiu.

Control de moviment

Article principal: Control de moviment

El control de moviment és necessari per corregir els errors que es poden donar durant el desplaçament.

El control és el darrer gran aspecte de la navegació autònoma i converteix la planificació en moviments. Els actuadors d'un robot mòbil solen ser elèctrics, tot i que també poden ser motors de combustió. La tasca d'un controlador consisteix a subministrar la potència necessària a aquests sistemes per tal que segueixin la ruta establerta prèviament. Durant el desplaçament hi poden haver errors, que són detectats amb els sensors del sistema de percepció. Per corregir-los, els controladors solen incloure un model matemàtic que descriu com es mou el robot i que permet que el controlador redreci la trajectòria.

La majoria de controladors per a robots mòbils disposen d'una estructura jerarquitzada. Tot i que no hi ha cap estructura definitiva, generalment sempre hi ha les següents capes: control independent, coordinat i de trajectòria. Cada capa s'implementa subministrant senyals de referència (comandaments) a la capa immediatament subordinada i les capes subordinades envien senyals de retroalimentació a les capes superiors.

La capa més bàsica és la de control independent, també coneguda com a SISO de l'anglès single input single output. Aquesta capa s'encarrega de dirigir els moviments d'un sol grau de llibertat fent servir sensors únicament associats a l'actuador d'aquell moviment. Generalment no disposa de cap informació de la resta de sistemes. A més a més, aquesta capa típicament reacciona simplement a l'error de l'estat actual i té una capacitat de predicció limitada a la computació dels errors derivatius. Els controls d'aquest nivell solen connectar-se directament a actuadors com la potència d'un motor elèctric o una vàlvula hidràulica. Generalment es necessita calibratge i els mètodes clàssics de control, com un PID, solen ser adequats.

La segona capa és la de control coordinat, també coneguda com a MIMO de l'anglès multiple input multiple output. En aquest cas s'aconsegueix un control instantani de tot el vehicle, que es tracta com una sola entitat. El control coordinat intenta mantenir tots els sistemes independents sincronitzats de manera que el seu efecte net sigui el comportament desitjat. Sol fer servir senyals de sensors de diferents components i pot dur a terme diferents accions basant-se en els senyals de comandament i retroalimentació que rep. Els mètodes de control d'estat d'espais se solen usar en aquest nivell i s'apliquen per controlar la velocitat lineal i angular del vehicle, coordinant la totalitat de la locomoció.

Finalment, el control de trajectòria rep com a senyal la ruta planificada i fa que el robot la segueixi. Generalment es fan servir mesures de l'entorn i predicció del moviment per dirigir el vehicle correctament. Aquest control s'usa per conduir el robot a una posa, seguir una ruta específica o per seguir un altre vehicle basant-se en els sistemes de percepció.

Bibliografia

• Atsushi, Sakai. «PythonRobotics: a Python code collection of robotics algorithms». ArXiv, 2018. [Consulta: 8 març 2019].
• Dudek, Gregory; Jenkin, Michael. Computational Principles of Mobile Robotics. Nova York: Cambridge University Press, 2010, p. 283-287. ISBN 978-0-521-87157-0 [Consulta: 1r febrer 2019]. 
• González, David; Pérez, Joshué; Milanés, Vicente; Nashashibi, Fawzi. A Review of Motion Planning Techniques for Automated Vehicles (en anglès). IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 4, 2016, p. 1135-1145. ISBN 978-0-262-01535-6 [Consulta: 19 març 2019]. 
• Kelly, Alonzo. Mobile robotics: mathematics, models, and methods. Nova York: Cambridge University Press, 2013, p. 701. ISBN 978-1-107-03115-9 [Consulta: 22 març 2019]. 
• LaValle, Seven M. Planning algorithms. Cambridge University Press, 2006, p. 842. ISBN 978-0521862059 [Consulta: 3 maig 2019]. 
• Siegwart, Roland; Nourbakhsh, Illah R.; Scaramuzza, Davide. Introduction to Autonomous Mobile Robots (llibre) (en anglès). 2. Cambridge, Massachusetts: The MIT Press, 2011, p. 472. ISBN 978-0-262-01535-6 [Consulta: 25 febrer 2019]. 
• Thoa Mac, Thi; Copot, Cosmin; Trung Tran, Duc; De Keyser, Robin «Heuristic approaches in robot path planning: A survey». . Robotics and Autonomous Systems, 2016, p. 13-28. DOI: /10.1016/j.robot.2016.08.001 [Consulta: 19 març 2019].

Enllaços externs

• Enllaç a Github amb algorismes de navegació robòtica: PythonRobotics (anglès)