La planification de chemin consiste à concevoir une séquence d'étapes à suivre pour une entité mobile. Cette tâche est au coeur de nombreux problèmes du monde réel. L'étude de la planification autonome peut permettre de réduire la congestion, la pollution, les accidents, les coûts et plus encore. Dans certaines applications, il est important de considérer la connectivité des agents. Bien que certaines configurations garantissent une connectivité permanente entre les entités (ex: entrepôts), ce n'est pas toujours le cas dans les applications avec des environnements ouverts. Un autre aspect que l'on retrouve dans de nombreuses applications est le manque de la connaissance complète de la zone dans laquelle les entités se déplacent. Par exemple, dans les missions d'exploration, les agents ne reçoivent aucune information sur l'environnement et doivent le découvrir par eux-mêmes. Les travaux récents sur la planification des entités se sont concentrés sur la planification d'exécutions sans collision. Ce problème, appelé Multi-Agent Path Finding (MAPF), consiste à trouver une séquence d'étapes pour qu'un groupe d'agents atteigne des cibles spécifiées tout en évitant les collisions. La contribution de ce travail est double. Tout d'abord, nous présentons un cadre pour étudier et modéliser les problèmes de planification de chemins multi-agents basés sur la connectivité. Nous fournissons un travail initial détaillé sur la complexité de ce cadre et un algorithme optimal pour le résoudre. Deuxièmement, nous étendons notre cadre de connectivité au cadre de connaissance incomplète et montrons la complexité du calcul connecté et décentralisé des plans dans des environnements partiellement connus.