Configurable flows

Abstract

In this work, we propose a new solution to agent navigation based upon boundary value problems (BVP), called Configurable Flows, to control steering behaviors of characters in dynamic environments. We use a potential field formalism that allows synthetic actors to move negotiating space, avoiding collisions, and attaining goals while producing very individual paths. The individuality of each character can be set by changing its inner field parameters leading to a broad range of possible behaviors without jeopardizing its performance. BVP Path Planners generate potential fields through a differential equation whose gradient descent represents navigation routes from any point of the environment to a goal position. Resulting paths are smooth and free from local minima. In spite of these advantages, these kind of planners consumes a lot of time to produce a solution. Our approach combines a BVP Path Planner with the Full Multigrid Method, which solves elliptic partial differential equations using a hierarchical strategy. The proposed planner enables real-time performance in large environments. Results show that our proposal spends less than 1% of the time needed to compute a solution using the original BVP planners in several environments. We refine our Path Planner by introducing a new form of the core equation that permits to easily cope with terrain inhomogeneities. This is accomplished by locally changing the concavity/ convexity of the potential, and then creating regions with higher or lower navigation preferences. As the potential field requires several steps to converge, this approach can be expensive computationally. To overcome this problem, we integrate this novel core equation to the hierarchical planner, emerging a wide variety of applications. We believe our proposal can contribute to several areas of research including agent navigation, pathfinding for games, crowd simulation and robotics. Our publications reinforce the relevance of the proposed method.

A animação de agentes autônomos em aplicações que exigem uma resposta em tempo real ainda é um desafio, se o problema necessitar que o agente alcance um local com precisão em um mundo virtual (planejamento de caminho), mover-se realisticamente de acordo com sua personalidade, intenções e humor. É muito difícil produzir um comportamento natural através de alguma estratégia que foque no controle global dos agentes. Por outro lado, levar em conta a individualidade de cada agente pode ser uma tarefa custosa. A proposta dessa tese é uma nova solução para o problema da navegação de agentes, baseada em problemas de valores de contorno (BVP), chamada “Configurable Flows”, para controlar a navegação de agentes em ambientes dinâmicos. Nós usamos um formalismo baseado em campos potenciais para possibilitar que agentes virtuais se movam negociando o espaço, evitando colisões, e alcançando seus objetivos, através de caminhos diferenciados. A individualidade de cada agente pode ser definida alterando parâmetros internos dos agentes. Planejadores BVPs produzem campos potenciais através de equações diferenciais das quais o gradiente descendente representa rotas navegacionais de qualquer lugar do ambiente para algum destino. Os caminhos resultantes são suaves e livres de mínimos locais. Apesar dessas vantagens, estes tipos de planejadores consomem muito tempo de execução para produzir uma solução. A nossa abordagem combina nosso planejador BVP com o método Full Multigrid, o qual resolve equações diferenciais parciais elípticas usando uma estratégia hierárquica. Os resultados mostram que a nossa proposta gasta menos que 1% do tempo necessário para computar a solução usando os planejadores BVPs tradicionais. Nós refinamos o planejador introduzindo uma nova forma para o núcleo da equação que permite facilmente lidar com terrenos não-homogêneos. Isto é obtido através de mudanças locais na concavidade/convexidade do potencial, criando regiões com altas ou baixas preferências de navegação. Nós integramos esta nova equação ao planejador hierárquico, surgindo uma ampla variedade de aplicações. Nossa proposta contribui para diversas áreas incluindo a navegação de agentes, pathfinding em jogos, simulação de multidões, e a navegação de robôs. Nossas publicações reforçam a relevância e robustez do método proposto.