miniatura|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ó 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ó 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.
miniatura|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.
miniatura|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.
miniatura|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:
Sensorial: dades sense processar o amb un processament de senyals simple. 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. Relacional local: plànol que incorpora relacions funcionals, estructurals o semàntiques entre objectes geomètrics propers. Topològic: mapa amb relacions de llarga distància entre tots els objectes d'un entorn. Semàntic: plànol amb les descripcions funcionals de cada àrea.
miniatura|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.
miniatura|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
miniatura|El control de moviment és necessari per corregir els errors que es poden donar durant el desplaçament.