Algoritmi di Ricerca e Programmazione Logica: Euristiche, ASP e PDDL

Funzioni Euristiche

La formula generale per il calcolo del costo in un algoritmo di ricerca è:
f(n) = g(n) + h(n), dove g(n) rappresenta il Costo Passato e h(n) l'Euristica.

Problemi di cammino su griglia o mappa

• 1. Distanza di Manhattan
  
  • Quando usarla: Griglie con movimenti in 4 direzioni (su, giù, sinistra, destra).
  • Formula: h(n) = |x₁ - x₂| + |y₁ - y₂|
  • Esempio: Muoversi in una città a blocchi.
• 2. Distanza Euclidea
  
  • Quando usarla: Movimento continuo nello spazio (senza restrizioni di direzione).
  • Formula: h(n) = √{(x₁ - x₂)² + (y₁ - y₂)²}
  • Esempio: Un drone che vola da un punto all’altro in linea retta.
• 3. Distanza di Chebyshev
  
  • Quando usarla: Griglie in 8 direzioni (inclusi movimenti diagonali a costo uniforme).
  • Formula: h(n) = max(|x₁ - x₂|, |y₁ - y₂|)
  • Esempio: Personaggio in un gioco che si muove liberamente in diagonale.

Sintassi e Costrutti ASP (Answer Set Programming)

• Weak Constraints: :~ <condizione>. [<peso>@<lvl>:termini]
• Funzioni di Aggregazione: #funzione { <Peso>, <etichetta per appartenenza> : <Condizione> } <op. confronto> <Numero>
  Esempio: #max{C,S : minCost(S, C)}
• Choice Rules: {p(a), q(b)} oppure {sensOn(S)} :- sensore(S).
• Simboli di Funzione: f(t1, t2, ..., tn). Servono per assegnare un nome a un oggetto e sono analoghi a "record" o "strutture".

Semantica e Valutazione ASP

Ridotto di Gelfond-Lifschitz

Per calcolare il ridotto:

1. Prendi un answer set potenziale.
2. Elimina le regole che hanno nel corpo un not presente in esso.
3. Cancella i not restanti.
4. Verifica se l’answer set è ancora deducibile dal programma risultante.

Processo di Esecuzione ASP con Simboli di Funzione

1. Controllare se le regole sono safe.
2. Grounding (istanziazione delle variabili).
3. Riduzione di Gelfond-Lifschitz.
4. Derivazione degli atomi partendo dai fatti e iterando fino alla saturazione.

Gestione delle Liste

Esistono due notazioni principali:

1. Notazione testa-coda: [ H | T ]
2. Elenco esplicito: [ t1, ..., tn ]

Grafo delle Dipendenze

• Nodi: Sono i fatti (atomi) in testa alle regole.
• Archi: Un arco b → a esiste se b compare nel corpo positivo di una regola con a in testa.
• Stratificazione: Il programma è non stratificato se esiste un ciclo contenente una negazione ("-").
• Proprietà: Se un programma è aciclico, la condizione che il modello sia supportato è necessaria e sufficiente affinché sia un Answer Set (A.S.).

PDDL (Planning Domain Definition Language)

Per definire un problema di pianificazione è necessario:

1. Identificare chi fa qualcosa (gli enti che agiscono).
2. Identificare gli oggetti nel contesto (elementi dell'ambiente con cui si interagisce).
3. Definire il contesto d'azione (es. spostarsi in un'altra stanza può cambiare l'accessibilità degli oggetti).

Domain

(define (domain <nome-dominio>)
  (:requirements :strips :typing :negative-preconditions :conditional-effects)
  (:types <elenco-tipi>)
  (:predicates 
    (<nome-predicato1> ?<parametri> - <tipo>)
    (<nome-predicato2> ?<param1> ?<param2> - <tipo>)
  )

  ;; Azione 1
  (:action <nome-azione>
    :parameters (?<parametri> - <tipo>)
    :precondition (and (<condizioni>))
    :effect (and 
      (<effetti>)
      (when (<condizione>) (and <effetti>))
    )
  )
)

Problem

(define (problem <nome-problema>)
  (:domain <nome-dominio>)
  (:objects 
    <oggetto1> <oggetto2> - <tipo>
  )
  (:init
    <fatti-veri-nello-stato-iniziale>
  )
  (:goal 
    (and <fatti-desiderati-nel-goal>)
  )
)

Verifica e Validazione

Verifica del Modello

Per determinare se un insieme è un modello, per ogni regola controlla se:

• Il corpo è falso: la regola è soddisfatta automaticamente.
• Il corpo è vero: controlla se la testa è presente nell'Answer Set.

Verifica dell'Answer Set (A.S.)

Per confermare se un insieme è un Answer Set:

1. Applica il ridotto di Gelfond-Lifschitz.
2. Trova il modello minimale del programma risultante:
   • Partendo dai fatti, applica le regole iterativamente finché non è più possibile aggiungere nuovi atomi.
3. Confronta il modello minimale ottenuto con l'interpretazione iniziale. Se coincidono, è un Answer Set.