Takafumi Horiuchi

Trabalho de conclusão de curso sobre programação por restrições

Visão geral

Quanto mais eventos possíveis uma simulação inclui, mais condições ela precisa avaliar repetidamente. Mas, se o avanço da simulação permite estabelecer que uma condição nunca mais poderá ser verdadeira, seria seguro deixar de verificá-la? Projetei e implementei um método para HydLa, uma linguagem de modelagem de sistemas híbridos, que usa a direção de variação das variáveis para remover condições que já não precisam ser verificadas.

No modelo de avaliação, o método reduziu o tempo de execução para aproximadamente metade do tempo do algoritmo original, sem alterar os resultados da simulação. A melhoria veio do uso da estrutura do problema para reduzir as possibilidades consideradas.

A perspectiva da programação por restrições que desenvolvi nesta pesquisa hoje fundamenta minha abordagem aos projetos do meu portfólio: em vez de especificar cada resultado diretamente, definir regras, prioridades e limites e, então, derivar soluções que os satisfaçam.


Problema: mais possibilidades significam maior tempo de execução

HydLa descreve sistemas híbridos, que combinam mudanças contínuas e eventos discretos, por meio de restrições matemáticas e lógicas. Em vez de especificar cada etapa de um procedimento, o modelo declara as condições que devem ser satisfeitas, e o simulador encontra comportamentos compatíveis com elas.

Em modelos com muitas regras condicionais, o simulador verifica repetidamente um grande conjunto de candidatos. Mesmo as condições que já não podem se tornar verdadeiras permanecem nesse conjunto. À medida que o modelo cresce, essas verificações desnecessárias aumentam o trabalho computacional.

Modelo: combinando mudanças contínuas e discretas

Uma bola quicando é um exemplo simples de sistema híbrido. Sua posição e sua velocidade variam continuamente enquanto ela está no ar, e o contato com o chão desencadeia um evento discreto de rebote. Termostatos, carros e robôs também combinam esses dois tipos de mudança, em diferentes escalas.

A avaliação usou um modelo de uma bola que se move horizontalmente e quica sobre uma superfície dividida em segmentos. Cada segmento tem uma regra condicional que faz a bola quicar quando chega àquela área. A inclusão de segmentos permite representar mais objetos, mas também aumenta o número de condições que o simulador precisa verificar.

Código-fonte em HydLa que define uma bola que se move horizontalmente e quica sobre uma superfície dividida em N segmentos adjacentes.
Um modelo curto em HydLa descreve uma bola e uma superfície dividida em N segmentos, cada um com uma restrição guardada.

Gargalo: mais condições aumentam o tempo de execução

Uma regra que só é ativada quando uma condição é satisfeita é chamada de restrição guardada. No modelo de avaliação, a regra de rebote de um segmento só é ativada quando a bola atinge o chão e sua posição horizontal está dentro daquele segmento.

Quando o número de segmentos passou de 10 para 200, o tempo de execução do simulador original cresceu aproximadamente com o quadrado desse número. Modelos maiores podem ampliar esse problema ao incluir mais objetos, regiões de contato e eventos possíveis.

Investigação: o que consumia 96% do tempo de execução?

A análise de desempenho do modelo com 100 segmentos mostrou que FindMinTime consumia 96% do tempo total de execução. Essa rotina encontra o primeiro evento que pode ocorrer a seguir, avaliando repetidamente todas as condições de guarda candidatas.

Isso revelou uma oportunidade bem definida de melhoria: reduzir com segurança os candidatos enviados a FindMinTime. O objetivo era ignorar apenas as possibilidades que já não precisavam ser avaliadas, preservando os resultados da simulação.

Abordagem: remover condições que não podem voltar a ser verdadeiras

Imagine uma bola quicando escada abaixo. Depois que ela passa por um degrau e continua avançando, esse degrau já não pode afetá-la. Uma pessoa que olha o diagrama ignora imediatamente os degraus atrás da bola; o algoritmo original continuava verificando todos eles.

Uma trajetória vermelha acompanha a bola que quica pelos degraus pretos. Os degraus hachurados já foram ultrapassados e não podem mais afetar a bola.
À medida que a bola avança para a direita, a guarda associada a um degrau sombreado atrás dela pode deixar de ser verificada.

A dificuldade está em provar que uma guarda removida não será necessária mais tarde. Removê-la apenas porque é falsa naquele momento poderia produzir um resultado incorreto sem aviso caso ela voltasse a ser verdadeira. Por isso, o método proposto usa a monotonicidade: a possibilidade de garantir que uma variável continue aumentando ou diminuindo durante determinado intervalo.

Quando a direção da variação se mantém

A primeira abordagem se aplica quando uma variável varia em uma única direção durante toda a simulação. No modelo de superfície segmentada, a posição horizontal da bola sempre aumenta. Depois que ela ultrapassa um segmento, a guarda desse segmento nunca mais pode se tornar verdadeira. Técnicas de verificação de modelos podem confirmar essa propriedade antes da simulação, permitindo remover as guardas com segurança à medida que se tornam irrelevantes durante a execução.

Uma linha vermelha sobe de α no instante 0 até β no fim da simulação, representando uma variável que aumenta durante todo o intervalo simulado.
Monotonicidade uniforme significa que a direção da variação se mantém durante todo o intervalo simulado.

Quando a direção da variação se inverte

Muitos sistemas não variam em uma única direção indefinidamente: uma variável pode aumentar, inverter a direção e depois diminuir. Por isso, o trabalho propôs uma segunda abordagem. Ela pressupõe uma direção de variação e monitora essa suposição com asserções. Quando a direção muda, o processo de redução recomeça, restaurando as guardas removidas durante o intervalo monótono anterior. Essa abordagem foi projetada, mas não foi implementada nem avaliada neste projeto.

Cinco diagramas mostram um intervalo de crescimento inicialmente presumido, uma falha de asserção, um novo intervalo de decrescimento, uma segunda falha e a identificação sucessiva de intervalos monótonos.
As falhas de asserção dividem o comportamento em intervalos, cada um dos quais pode ser tratado como monótono.

Resultado: cerca de metade do tempo de execução no modelo de avaliação

Implementei a abordagem de monotonicidade uniforme e a avaliei com o modelo de superfície segmentada. O tempo de execução cresceu com o número de segmentos em ambos os algoritmos, mas o método proposto foi consistentemente mais rápido. Nas curvas ajustadas, o coeficiente do termo de maior ordem caiu de 1,1463 para 0,6083. Nesse teste de desempenho, o tempo total de simulação foi reduzido em aproximadamente metade.

Esse resultado se refere especificamente ao modelo avaliado. O método é útil quando um modelo contém muitos objetos com restrições guardadas, a direção da variação pode ser demonstrada e as guardas se tornam permanentemente irrelevantes durante a execução. Isso não significa que todos os modelos em HydLa serão executados duas vezes mais rápido.

Tempo de simulação em função de N, o número de segmentos da superfície. De 10 a 200 segmentos, o método proposto é consistentemente mais rápido. Com N = 200, leva cerca de 250 segundos, comparado a aproximadamente 470 segundos do algoritmo original.
Nos modelos avaliados, o método proposto (quadrados) leva aproximadamente metade do tempo do algoritmo original (círculos).

O que aprendi

Esta pesquisa usou propriedades conhecidas do comportamento de um sistema para reduzir o conjunto de possibilidades que o simulador precisava considerar. Restringir o espaço de busca e preservar os resultados é um dos pontos fortes da programação por restrições.

A implementação e a avaliação abrangeram variáveis que continuavam variando em uma única direção. O tratamento de inversões permaneceu na etapa de projeto e ainda precisava ser avaliado. Propriedades além da monotonicidade também podem ajudar a identificar restrições desnecessárias.

Essa experiência orienta meu interesse atual em projetar as condições e os limites dentro dos quais a IA pode buscar soluções. Ao lidar com resultados complexos, definir o que pode ser ignorado com segurança é tão importante quanto definir o que calcular.

Takafumi Horiuchi e Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Anais da 33ª Conferência Anual da Sociedade Japonesa de Inteligência Artificial, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02