Durante la fase di costruzione del Planning Graph vengono inoltre definite le relazioni di mutua esclusione tra coppie di azioni e coppie di fatti. Tali relazioni risultano fondamentali nella successiva fase di ricerca. Il concetto di mutua esclusione segue direttamente quello di Interferenza e di Competing needs (precondizioni contrastanti). Due azione interferiscono fra loro se una cancella anche una sola precondizione o un effetto additivo di un'altra. Due azioni hanno competing needs se i fatti delle loro precondizioni sono mutuamente esclusivi, cioè se non è possbile rendere veri entrambi i fatti allo stesso istante temporale. Due azioni sono dunque mutuamente esclusive se ad un certe istante temporale interferiscono fra loro o hanno competing needs. Due fatti sono mutualente esclusivi se nessuno stato del mondo può renderli veri entrambi contemporaneamente. Per concludere, un operatore è applicabile ad un livello dei fatti Nf(n) se e solo se in questo livello le sue precondizioni sono presenti e non mutuamente esclusive. In questo modo il pianificatore non aggiunge al grafo potenziali conflitti fra azioni o fatti.Questo procedimento viene ripetuto n volte fino che i goal G non appartengono all'istante finale e non sono mutuamente esclusivi (in tal caso viene avviato il processo di ricerca) oppure finché il grafo non è stabilizzato e l'ultimo livello contiene una coppia di elementi di G mutuamente esclusivi (il problema non ha soluzione). Un grafo si dice stabilizzato al livello n se il numero di fatti presenti (|Nf(n)|=|Nf(n-1)|)e di coppie di fatti mutuamente esclusivi in n è uguale a quelli del livello precedente n-1. Quindi un problema di pianificazione P non ha soluzione se il suo Planning Graph è stabilizzato a n e, le formule atomiche del Goal non sono contenute nel livello fatti n (Nf(n) ) o due formule atomiche dei Goal sono mutuamente esclusive. In caso contrario la costruzione grafo si ferma e comincia la ricerca, a partire dal Goal fino ai fatti iniziali. Il pianificatore infatti parte dall'ultimo livello fatti Nf(n) raggiunto durante la costruzione del grafo e cerca le azioni del livello n-1 che supportano i goal in Nf(n). Come passo successivo Ipp calcola i fatti goaldel livello n-1 basandosi sulle precondizioni delle azioni trovate precedentemente. Graficamente il pianificatore sceglie gli archi che vanno dai fatti goal di Nf(n) fino ai loro operatori in No(n-1) e poi definisce, tramite le precondizioni di questi, i sottogoal del livello Nf(n-1). Questo spostamento lungo gli archi non è univoco, infatti più di un operatore può portare a un fatto goal e quindi l'algoritmo di ricerca sceglie di volta in volta uno fra gli archi disponibili. Se l'insieme sottogoal contiene fatti mutuamente esclusivi, il pianificatore fa backtrack, torna indietro, e sceglie altri archi diversi da quelli di prima. Viene fatto così un successivo controllo sull'insieme delle azioni scelte per vedere se è minimo cioè se ogni azione rende supportato un fatto goal che non è reso vero da nessun altra azione dell'insieme stesso. Se ciò non è verificato Ipp fa backtrack e viene valutato un nuovo insieme di azioni e archi. Le precondizioni delle azioni valide definiscono il nuovo insieme di goal del livello Nf(n-1) e la ricerca prosegue in questo livello sempre cercando nuove strade quando i controlli fatti danno esito negativo. Se si riesce ad arrivare ai fatti della situazione iniziale significa che la ricerca ha avuto successo e il piano soluzione per il mio problema di pianificazione P consiste nell'insieme di azioni che Ipp ha selezionato (e non scartato) nella sua salita fra i livelli. Se il pianificatore necessita di fare backtrack al massimo livello del grafo (cioè quello dei goal) significa che non è possibile trovare soluzione per il problema P. Allora il Planning Graph viene esteso con un livello aggiuntivo di azioni e di fatti e ricomincia la ricerca con questo nuovo grafo. Questo processo di espansione e ricerca termina o quando viene trovata una soluzione o se il problema risulta essere irrisolvibile.