O Planejamento de IA (AI Planning) é um ramo da Inteligência Artificial que gera sequências de ações para sair de um estado inicial e chegar a um estado objetivo. No roteamento de veículos, por exemplo, cada decisão sobre a rota (escolher ruas, sequenciar paradas) é uma ação dependente de fatores como tráfego e distância.

Este artigo cobre o básico e traz um exemplo prático.

Planejamento para Diferentes Domínios

O mesmo formalismo funciona em vários domínios. Na logística, otimiza rotas de veículos dado tráfego e distância. Na saúde, gerencia planos de tratamento. Na manufatura, sequencia etapas de produção. Como a representação é agnóstica ao domínio, um planejador construído para uma área pode ser reutilizado em outra — só muda a definição do problema.

O Papel do PDDL no Planejamento de IA

A forma padrão de expressar problemas de planejamento é o Planning Domain Definition Language (PDDL). O PDDL oferece um formato estruturado para definir os componentes de um problema: ações, estados e objetivos. Qualquer planejador que leia PDDL pode, em princípio, resolver problemas de qualquer domínio.

Na prática, os planejadores evoluíram junto com a linguagem, e o suporte varia. Planejadores mais antigos podem não lidar com recursos do PDDL 3, enquanto planejadores mais recentes podem não suportar certas variantes de sintaxe do PDDL 2.1. Isso significa que é preciso escolher um planejador compatível com a definição do seu problema.

Planejamento de IA em Ação

Para ver o Planejamento de IA na prática, vamos usar o LAMA, um planejador voltado para problemas reais. O LAMA utiliza busca heurística progressiva com estratégias baseadas em marcos (landmarks), múltiplas heurísticas e o algoritmo A* com peso progressivo. A descrição completa está no artigo.

Instalando o LAMA

Para instalar o LAMA, podemos usar o planutils, uma ferramenta projetada para ambientes Linux que ajuda a desenvolver, executar e avaliar planejadores. Consulte o README no GitHub para obter diretrizes completas de instalação.

Definindo o Domínio

Considere um robô navegando em uma grade bidimensional. Algumas células são marcadas com "X" como obstáculos. O objetivo é mover o robô de uma célula inicial até um destino. Neste cenário, o robô precisa ir da caixa 1 à caixa 5, mas a caixa 3 está bloqueada, então o caminho é 1, 2, 4, 5.

Simples Domínio do Robô

Para definir este domínio em PDDL, precisamos especificar:

  • Objetos: Os objetos são as entidades no domínio.
  • Predicados: Os predicados definem o estado do domínio.
  • Ações: As ações que podem ser realizadas no domínio.
  • Estado Inicial: O estado inicial do domínio.
  • Estado Final: O estado objetivo do domínio.

Este é o domínio em PDDL para o cenário proposto:

(define (domain robot)
  (:requirements :strips :typing)
  (:types robot location)

  (:predicates
    (at ?r - robot ?l - location)
    (blocked ?l - location)
    (adjacent ?l1 ?l2 - location)
  )

  (:action move-up
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-down
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-left
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-right
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1)))))

Definindo o Problema

Também precisamos de um arquivo de problema. Este arquivo lista os objetos específicos e descreve os estados inicial e final. Abaixo está o arquivo de problema para este cenário:

(define (problem robot)
  (:domain robot)
  (:objects
    robot1 - robot
    box1 box2 box3 box4 box5 - location
  )
  (:init
    (at robot1 box1)
    (blocked box3)

    (adjacent box1 box2)
    (adjacent box1 box3)
    (adjacent box2 box4)
    (adjacent box3 box4)
    (adjacent box4 box5)
  )

  (:goal (at robot1 box5))
)

Este arquivo de problema PDDL, chamado robot, define um cenário específico para um robô navegando em uma grade:

  • Domínio: O domínio no qual o problema é definido. Neste caso, o domínio é robot.
  • Objetos: Existem dois tipos de objetos:
    • robot1, representando o robô.
    • box1, box2, box3, box4, box5, representando locais na grade.
  • Estado Inicial: O robô (robot1) começa na caixa1. A caixa3 é marcada como uma localização bloqueada. As relações de adjacência entre as caixas são definidas, especificando quais caixas são acessíveis diretamente umas das outras.
  • Estado Final: O objetivo é mover robot1 para box5.

Executando o LAMA

Com ambos os arquivos prontos, execute o LAMA na linha de comando (certifique-se de que ele está instalado e acessível no PATH):

lama domain.pddl problem.pddl

O LAMA retorna a solução como uma sequência de ações. Se não existir plano válido, ele informa que nenhuma solução foi encontrada.

(move-down robot1 box1 box2)
(move-down robot1 box2 box4)
(move-down robot1 box4 box5)
; cost = 3 (unit cost)

Este exemplo tem um robô e um objetivo, mas a definição do domínio pode ser estendida para múltiplos robôs com objetivos separados.

Considerações Finais

Este artigo cobriu um domínio simples de robô, mas a mesma abordagem se aplica a problemas muito mais difíceis. A International Planning Competition publica problemas de referência projetados justamente para levar os planejadores ao limite.

Alguns solucionadores também suportam planejamento numérico, em que variáveis podem representar quantidades como custo de entrega. Isso é útil em logística e agendamento, onde chegar ao estado final não basta — também é preciso minimizar o custo.

Recursos Adicionais