Cet article propose DECBS, un nouvel algorithme d'approximation pour le problème de recherche de chemin multi-agents (MAPF). MAPF est un problème NP-difficile où plusieurs agents trouvent un chemin vers un objectif sans collision. Les algorithmes d'approximation contraints existants, tels qu'ECBS et EECBS, utilisent des techniques de recherche focale pour équilibrer efficacité de calcul et qualité de la solution. Cependant, la recherche focale conventionnelle souffre du problème de la croissance lente de la valeur de la borne inférieure (LB) dans les premières étapes, ce qui limite l'espace de recherche. DECBS résout ce problème en déterminant d'abord la valeur maximale de la LB et en effectuant une recherche par le meilleur d'abord basée sur cette valeur. Les résultats expérimentaux montrent que DECBS surpasse ECBS dans la plupart des cas et est compatible avec les techniques d'optimisation existantes. Plus précisément, lorsque la densité d'agents est moyenne à élevée, DECBS obtient une amélioration moyenne du temps d'exécution de 23,5 % par rapport à ECBS dans les mêmes conditions de borne de sous-optimalité et d'optimisation. Il réduit également les nœuds CT de grande dimension d'environ 30 % et les nœuds de recherche focale de faible dimension d'environ 50 %.
