Planning con SAT: un approccio ibrido

La pianificazione automatica è un campo dell'AI che si occupa di trovare sequenze di azioni per raggiungere un obiettivo. I problemi di planning classici sono spesso definiti usando rappresentazioni del primo ordine, che offrono compattezza e generalità. Tuttavia, la maggior parte dei planner grounda queste rappresentazioni per semplificare il ragionamento, il che può portare a un'esplosione esponenziale delle dimensioni del problema.

Codifica parzialmente groundata

Un recente studio presenta un approccio intermedio tra planning completamente lifted e completamente groundato. Vengono introdotte tre codifiche SAT che mantengono le azioni lifted, groundando parzialmente i predicati. A differenza delle precedenti codifiche SAT, che scalano quadraticamente con la lunghezza del piano, questo approccio scala linearmente, consentendo performance migliori su piani più lunghi.

Performance e scalabilità

I risultati empirici mostrano che la migliore codifica proposta supera lo stato dell'arte nella pianificazione a lunghezza ottimale su domini difficili da groundare. Questo suggerisce che la codifica parzialmente groundata può essere una tecnica promettente per affrontare problemi di planning complessi con requisiti di scalabilità elevati.