Recherche de chemin | EPFL Graph Search

La recherche de chemin, couramment appelée pathfinding par anglicisme, est un problème de l'intelligence artificielle qui se rattache plus généralement au domaine de la planification et de la recherche de solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Nature du problème Initialement, un problème de pathfinding peut se ramener à un problème de recherche du meilleur chemin entre deux nœuds dans un graphe. Il existe un ensemble d'algorithmes classiques pour résoudre ce type de problème. Toutefois, le pathfinding devient un problème complexe lorsque l'on cherche à prendre en compte diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc.). Algorithmes de recherche de chemin Problème de plus court chemin Deux algorithmes déterministes principaux sont utilisés po

Adaptive Highways on a Grid

Hajir Roozbehani

The primary objective of this paper is to introduce the adaptive highways algorithm, a path planning algorithm for vehicles moving on a grid. We consider a workspace that consists of a symmetric grid and a large number of vehicles that move on the grid to accomplish a certain task. Each vehicle is assigned the task of visiting a set of randomly selected locations, which are updated over time. The dynamics of the vehicles are described by a constrained linear double-integrator model. The objective is to find, in real time, a set of trajectories that maximize the average speed of the vehicles while ensuring safety. The trajectory optimization problem is solved locally, whereas a central entity is employed for distribution of information. Safety guarantees are provided through a space reservation mechanism. Several algorithms are presented and compared in terms of performance.

Springer-Verlag Berlin2011

Motion planning and obstacle avoidance for mobile robots in highly cluttered dynamic environments

Roland Philippsen

After a quarter century of mobile robot research, applications of this fascinating technology appear in real-world settings. Some require operation in environments that are densely cluttered with moving obstacles. Public mass exhibitions or conventions are examples of such challenging environments. This dissertation addresses the navigational challenges that arise in settings where mobile robots move among people and possibly need to directly interact with humans who are not used to dealing with technical details. Two important aspects are solved: Reliable reactive obstacle avoidance to guarantee safe operation, and smooth path planning that allows to dynamically adapt environment information to the motion of surrounding persons and objects. Given the existing body of research results in the ﬁeld of obstacle avoidance and path planning, which is reviewed in this context, particular attention is paid to integration aspects for leveraging advantages while compensating drawbacks of various methods. In particular, grid-based wavefront propagation (NF1 and fast marching level set methods), dynamic path representation (bubble band concept), and high-ﬁdelity execution (dynamic window approach) are combined in novel ways. Experiments demonstrate the robustness of the obstacle avoidance and path planning systems.

EPFL2004

Requirements for building an ontology for autonomous robots

Howard Li, Kamilo Andres Melo Becerra

Purpose - IEEE Ontologies for Robotics and Automation Working Group were divided into subgroups that were in charge of studying industrial robotics, service robotics and autonomous robotics. This paper aims to present the work in-progress developed by the autonomous robotics (AuR) subgroup. This group aims to extend the core ontology for robotics and automation to represent more specific concepts and axioms that are commonly used in autonomous robots. Design/methodology/approach - For autonomous robots, various concepts for aerial robots, underwater robots and ground robots are described. Components of an autonomous system are defined, such as robotic platforms, actuators, sensors, control, state estimation, path planning, perception and decision-making. Findings - AuR has identified the core concepts and domains needed to create an ontology for autonomous robots. Practical implications - AuR targets to create a standard ontology to represent the knowledge and reasoning needed to create autonomous systems that comprise robots that can operate in the air, ground and underwater environments. The concepts in the developed ontology will endow a robot with autonomy, that is, endow robots with the ability to perform desired tasks in unstructured environments without continuous explicit human guidance. Originality/value - Creating a standard for knowledge representation and reasoning in autonomous robotics will have a significant impact on all R&A domains, such as on the knowledge transmission among agents, including autonomous robots and humans. This tends to facilitate the communication among them and also provide reasoning capabilities involving the knowledge of all elements using the ontology. This will result in improved autonomy of autonomous systems. The autonomy will have considerable impact on how robots interact with humans. As a result, the use of robots will further benefit our society. Many tedious tasks that currently can only be performed by humans will be performed by robots, which will further improve the quality of life. To the best of the authors'knowledge, AuR is the first group that adopts a systematic approach to develop ontologies consisting of specific concepts and axioms that are commonly used in autonomous robots.

Emerald Group Publishing Ltd2016

Requirements for building an ontology for autonomous robots

Howard Li, Kamilo Andres Melo Becerra

Emerald Group Publishing Ltd2016