Abstract: Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as a sum of these potentials. Mutexes are invariants stating that a certain set of facts cannot be part of any reachable state. In this paper, we use mutexes to improve potential heuristics in two ways. First, we show that the mutex-based disambiguations of the goal and preconditions of operators leads to a less constrained linear program providing a better set of potentials. Second, we utilize mutexes in a construction of new optimization functions based on counting of a number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.