Treatment planning

O planejador sequencial de [Chan et al. 2007] é baseado na técnica MEA. No seu trabalho, o uso de um planejador sequencial é o suficiente para garantir um plano de ações que possa ser submetido ao processo de escalonamento feito posteriormente. Esse planejador opera de modo a selecionar uma submeta que decrementa a diferença entre o estado inicial e a meta. As ações necessárias para resolver essa submeta são então executadas. Ao selecionar uma submeta, essa pode ser considerada uma nova meta e ser resolvida determinando a submeta necessária para resolvê-la, e assim por diante. Através de um processo recursivo, essas e todas as demais submetas vão sendo resolvidas, até que todas as metas estejam satisfeitas.

Durante a execução de um planejador, é preciso assumir que não existe nenhum tipo de recurso que seja produzido e consumido por uma mesma ação ao mesmo tempo. Todas as ações executam um tipo específico de efeito sobre os recursos do jogo, seja ele de produzir ou consumir os recursos. O Algoritmo3 mostra um pseudocódigo do planejador sequencial. O seu funcionamento será descrito de forma informal.

Para descrever alguns exemplos iremos utilizar o domínio da Figura 3.1, uma vez que os trabalhos de [Chan et al. 2007, Branquinho et al. 2011b] utilizam esse domínio. O algoritmo recebe como entrada o estado inicial de recursos do jogo S e a meta a ser atingida G. Após guardar o estado atual do jogo na variável P S com a função P roj(S) (linha 1), o algoritmo escolhe diversas vezes através de recursividade uma meta ainda não satisfeita onde Ri < gi e tenta construir um plano P lan′ que a resolva. Ele faz isso até

que o plano de ações completo tenha sido resolvido e não exista nenhuma meta pendente. O algoritmo entre as linhas 5 e 10 estabelece todas as variáveis e valores de recursos

Algoritmo 3 MEA(S, G)

1: P S ← P roj(S), estado projetado do jogo

2: if ∀i, Ri ≥ gi é satisfeito por P S then

3: return ∅ 4: end if

5: Ri ← algum recurso onde Ri < gi em P S

6: Ai ← ação que produz Ri

7: ri ← quantidade de Ri em P S

8: α ← quantidade de Ri produzida por Ai

9: k ← ceil((gi− ri)/α)

10: Acts ← plano sequencial com Ai repetido k vezes

11: G∗ _{← ∅ {Plano para satisfazer as pré-condições de A} i}

12: for all Rj = p que são pré-condições de Ai do

13: if Rj = p é uma précondição “require” ou “borrow ” de Ai then

14: G∗ _{← G}∗_{∪ R} j ≥ p

15: end if

16: if Rj = p é uma pré-condição “consume” de Ai then

17: G∗ _{← G}∗_{∪ R} j ≥ k.p 18: end if 19: end for 20: P re ← M EA(S, G∗ )

21: P lan′ _{← concatenar(P re, Acts)}

22: S′

← estado do jogo depois de executar sequencialmente P lan′ a partir de P S

23: return concatenar(P lan′

, M EA(S′

, G))

necessários que devem ser produzidos para satisfazer a meta na iteração atual. A variável Ai determina qual ação deve ser executada, rI, α e k determinam a quantidade de vezes

que a ação deve ser executada e quantos recursos ela irá gerar dado a quantidade atual de existente de recursos no jogo. Os loops seguintes determinam qual ação vai compor uma nova meta G∗que será passada como parâmetro para o algoritmo ser invocado novamente.

Assim são geradas todas as submetas necessárias. Por fim, o algoritmo concatena as ações contidas nas submetas gerando um plano de ações completo.

Uma das vantagens do MEA é que é possível estabelecer todas as ações necessárias que compõe um plano sem necessidade de verificar se alguma meta não foi cumprida. Para que isso aconteça, o algoritmo procura resolver sempre às pré-condições de recursos renováveis de uma ação antes de resolver as de recursos não renováveis. Assim, as pré- condições de recursos renováveis quando resolvidas, sempre ficaram resolvidas devido ao aumento desses recursos que acontece a cada nova meta que é resolvida.

O MEA então, quando produz um plano de ações, utiliza o mínimo de recursos necessários para atingir uma dada meta. Cada ação acrescentada pelo algoritmo é neces- sária para completar a meta, assim não é preciso também fazer verificações redundantes. Com isso, o algoritmo tem a quantidade de iterações relativa à quantidade de ações necessárias para atingir a meta estipulada.

nesses é possível que o MEA fique preso neles tentando resolver uma meta para sempre. Um exemplo de ciclo seria uma ação de collect-gold. Essa, necessita de uma Townhall e de um Peasant, caso tenhamos apenas esse último disponível, o algoritmo iria tentar executar uma ação de build-townhall . Essa iria necessitar de Gold que iria necessitar de Peasant que novamente iria necessitar da Townhall que está ausente. Gerando um ciclo infinito de satisfação de pré-condições. Entretanto, é possível estender o algoritmo para detectar tais ciclos, e para constar tanto no Wargus quanto no StarCraft o estado inicial contém os recursos necessários para evitar tais ciclos. O que pode acontecer é que no decorrer do jogo com as alterações que o mundo sofre, é possível que o estado do jogo em um dado momento esteja sem os recursos necessários para evitar tais ciclos, e se esse for considerado o estado inicial para um planejador o mesmo pode cair em um ciclo.

A seguir será apresentado um exemplo do funcionamento do algoritmo MEA.

Exemplo

Neste exemplo, o objetivo é encontrar um plano sequencial para o estado inicial (1 Townhall, 3 Peasant, 400 Gold, 200 Wood) e meta (1 Townhall, 4 Peasant). A Figura 3.12, mostra a primeira parte da meta que é resolvida pelo algoritmo para o problema em questão.

Figura 3.12: Primeiro passo do problema de planejamento sequencial.

A busca começa verificando cada recurso da meta G. O objetivo é determinar qual recurso não é satisfeito por S. Neste caso, é necessário criar 1 peasant para satisfazer a diferença entre S (3 Peasant) e G (4 Peasant), já que a primeira parte da meta relativa ao recurso Townhall já estava satisfeito no início do algoritmo. Para isso, é preciso adi- cionar uma ação build-peasant ao plano. Após incluir esta ação é realizada uma chamada recursiva para o Algoritmo 3, tendo como objetivo a satisfação das pré-condições de

build-peasant. É importante salientar que as metas de G que não forem satisfeitas neste momento, serão resolvidas em um passo posterior da recursão.

O algoritmo continua selecionando novas ações que decrementam a distancia do es- tado atual para a meta. Cada uma dessas transforma-se em uma submeta que deve ser resolvida antes que uma nova ação que interfere diretamente na meta G seja escolhida. Por fim, temos um conjunto de ações que devem ser executadas em na ordem estrita em que são colocadas no plano. Se essa ordem não for seguida, não será possível executar determinadas ações. Isso ocorre, pois sempre que uma ação vai ser executada suas pré- condições que são satisfeitas por outras ações estão atrás dela na sequência de posições, portanto a ação só deve ser acionada quando as que estão antes dela já tiverem sido executadas. A Figura 3.13 mostra a sequência final do algoritmo MEA e o plano gerado.

Figura 3.13: Plano sequencial obtido no exemplo tratado.