Un graphe de navigation représente lieux ou états comme des nœuds reliés par des passages, avec des coûts et contraintes qui permettent de choisir un itinéraire plutôt que de suivre une géométrie continue seule.
Une carte métrique décrit positions et distances dans un repère continu ; un graphe topologique décrit connexions et relations entre lieux, souvent avec moins de précision géométrique.
Le poids d’une arête combine distance, temps, énergie, pente, largeur, risque, incertitude, congestion et pénalité de changement selon l’objectif de la mission.
Lorsqu’un passage est bloqué, le robot marque l’arête indisponible ou plus coûteuse, vérifie les observations, recalcule un itinéraire et conserve un repli si aucune route fiable ne reste.
La couverture d’un graphe se vérifie en comparant nœuds, arêtes, accès, contraintes et replis aux itinéraires réellement nécessaires, puis en parcourant et requalifiant les passages.