Cet article présente une nouvelle méthode pour résoudre le problème de planification de chemin de recherche de zone multi-robots (MCPP) sur une grille 2D à 4 voisins. Les méthodes existantes calculent d'abord l'arbre de recherche sur une grille coordonnée par quadrants, puis génèrent le chemin à l'aide du paradigme de recherche par arbre couvrant (STC). Ce paradigme présente la limitation de son application aux grilles comportant des blocs 2x2 partiellement occultés. Dans cet article, nous proposons un paradigme STC étendu (ESTC) qui redéfinit le problème directement sur la grille, garantissant une recherche complète même dans les grilles comportant des blocs partiellement occultés. De plus, nous présentons un nouveau cadre algorithmique, LS-MCPP, qui intègre ESTC et trois nouveaux opérateurs de voisinage dans la stratégie de recherche locale. Enfin, nous intégrons une procédure de post-traitement polyvalente qui applique d'abord la technique de recherche de chemin multi-agents (MAPF) à la MCPP pour résoudre les collisions entre robots et prendre en compte les coûts de virage, améliorant ainsi son applicabilité pratique. Les résultats expérimentaux montrent que la solution peut être générée en quelques minutes, même sur des grilles comportant jusqu'à 100 robots et des tailles de 256x256, et la faisabilité d'applications réelles est vérifiée par validation à l'aide de vrais robots.
