We consider an abstract representation of some environment in which an agent is located. Given a goal sequence, we ask what strategy said agent - utilizing readily available algorithmic tools - should incorporate to successfully find a valid traversal route such that it is optimal in accordance with a predefined error-margin. We present four scenarios that each incorporate aspects common to general navigation to further illustrate some of the difficult problems needed to be solved in any general navigation strategy. Two reinforcement learning and four graph path planning algorithms are studied and applied on said predefined scenarios. Through the introduction of a long-term strategy model we allow comparative study of the result of the applications, and note a distinct difference in performance. Further, we discuss the lack of a probabilistic algorithmic approach and why it should be an option in any general strategy as it allows verifiably "good" estimated solutions, useful when the problem at hand is NP-hard. Several meta-level concepts are introduced and discussed to further illustrate the difficulty in producing an optimal strategy with an explicit long-term horizon. We argue for a non-deterministic approach, looking at the apparent gain of epsilon-randomness when incorporated by a reinforcement learning agent. Several problems that may arise with non-determinism are discussed, based on the notion that such an agents' performance can be viewed as a markov chain; possibly resulting in suboptimal paths concerning norm.

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. / 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.

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. / 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.

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. / 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.

Cette thèse porte sur la navigation d'agents dans un environnement manufacturier. Le cadre général du travail relève de la navigation d'AGVs (véhicules autoguidés), transportant librement et intelligemment leur produit. L'objectif est de proposer des outils permettant la navigation autonome et coopérative d’une flotte d’AGVs dans des systèmes de production manufacturiers où les contraintes temporelles sont importantes. Après la présentation d'un état de l'art sur chaque domaine (systèmes manufacturiers et navigation d'agents), les impacts de la mutualisation entre ceux-ci sont présentés. Ensuite, deux problématiques, liées à la navigation d'agents mobiles dans des environnements manufacturiers, sont étudiées. La première problématique est centrée sur la planification de trajectoire décentralisée où une fonction d'ordonnancement est combinée au planificateur pour chaque agent. Cette fonction permet de choisir une ressource lors de la navigation afin d'achever l'opération du produit transporté le plus tôt possible. La première solution consiste en une architecture hétérarchique où les AGVs doivent planifier (ou mettre à jour) leur trajectoire, ordonnancer leur produit pour l'opération en cours et résoudre leurs propres conflits avec les agents à portée de communication. Pour la seconde approche, une architecture hybride à l'aide d'un superviseur, permettant d'assister les agents durant leur navigation, est proposée. L'algorithme de planification de trajectoire se fait en deux étapes. La première étape utilise des informations globales fournies par le superviseur pour anticiper les collisions. La seconde étape, plus locale, utilise les données par rapport aux AGVs à portée de communication afin d'assurer l'évitement de collisions. Afin de réduire les temps de calcul des trajectoires, une optimisation par essaims particulaires est introduite. La seconde problématique se focalise sur la commande coopérative permettant un rendez-vous d'agents non holonomes à une configuration spécifique. Ce rendez-vous doit être atteint en un temps donné par un cahier des charges, fourni par le haut-niveau de contrôle. Pour résoudre ce problème de rendez-vous, nous proposons une loi de commande à temps fixe (i.e. indépendant des conditions initiales) par commutation permettant de faire converger l’état des AGVs vers une resource. Des résultats numériques et expérimentaux sont fournis afin de montrer la faisabilité des solutions proposées. / This thesis is focused on agent navigation in a manufacturing environment. The proposed framework deals with the navigation of AGVs (Automated Guided Vehicles), which freely and smartly transport their product. The objective is to propose some tools allowing the autonomous and cooperative navigation of AGV fleets in manufacturing systems for which temporal constraints are important. After presenting the state of the art of each field (manufacturing systems and agent navigation), the impacts of the cross-fertilization between these two fields are presented. Then, two issues, related to the navigation of mobile agents in manufacturing systems, are studied. The first issue focuses on decentralized motion planning where a scheduling function is combined with the planner for each agent. This function allows choosing a resource during the navigation to complete the ongoing operation of the transported product at the soonest date. The first proposed approach consists in a heterarchical architecture where the AGVs have to plan (or update) their trajectory, schedule their product and solve their own conflict with communicating agents. For the second approach, hybrid architecture with a supervisor, which assists agents during the navigation, is proposed. The motion planning scheme is divided into two steps. The first step uses global information provided by the supervisor to anticipate the future collisions. The second step is local and uses information from communicating agents to ensure the collision avoidance. In order to reduce the computational times, a particle swarm optimization is introduced. The second issue is focused on the cooperative control, allowing a rendezvous of nonholomic agents at a specific configuration. This rendezvous must be achieved in a prescribed time, provided by the higher level of control. To solve this rendezvous, a fixed time (i.e. independent of initial conditions) switching control law is proposed, allowing the convergence of agent states towards a resource configuration. Some numerical and experimental results are provided to show the feasibility of the proposed methods.