Trabalho de conclusão de curso sobre programação por restrições
junho de 2019
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.
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.
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.
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.
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.
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