Dans cet article, nous présentons un nouvel algorithme de recherche heuristique basé sur le calcul de moyennes pour la planification temps réel, appelé MHSP (Mean-Based Heuristic Search Planning). Il associe les principes d'UCT (Upper Confidence for Tree), un algorithme de type bandit ayant donné de très bons résultats dans le domaine des jeux, et plus particulièrement dans le cadre du jeu de Go, et une recherche heuristique en vue d'obtenir un planificateur temps réel dans le contexte de la planification d'actions. MHSP est évalué sur différents problèmes de planification et comparé aux algorithmes de recherche en ligne et d'apprentissage existants. Nos résultats mettent en évidence la capacité de MHSP à retourner en temps réel des plans qui tendent vers un plan optimal au cours du temps. Ils montrent de plus que MHSP est plus rapide et retourne des plans de meilleure qualité que les algorithmes existants dans la littérature.