Lecture

Global Navigation: Path Planning

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MICRO-452: Basics of mobile robotics

This course gives an overview of the field of mobile robotics, introducing to the main techniques and allowing to test them in exercises and a team-based project. ...

Description

This lecture covers the basics of mobile robotics with a focus on navigation. It starts by discussing the concept of global navigation and bio-inspired navigation. The lecture then delves into different approaches to path planning, including graph search strategies like breadth-first search, depth-first search, and best-first search (e.g. A*). Examples of path planning algorithms such as Dijkstra's Algorithm and Voronoi Diagrams are presented. The lecture also explores techniques like cell decomposition and potential field methods for path planning. Additionally, it introduces stigmergy-based path optimization using concepts like ant colony optimization. Practical examples and demonstrations are provided throughout the lecture.

Instructor

Francesco Mondada

Dr. Mondada received his M.Sc. in micro-engineering in 1991 and his Doctoral degree in 1997 at EPFL. During his thesis he co-founded the company K-Team, being both CEO and president of the company for about 5 years. He is one of the three main developers of the Khepera robot, considered as a standard in bio-inspired robotics and used by more than 1,000 universities and research centers worldwide. Fully back in research in 2000 and after a short period at CALTECH, he participated to the SWARM-BOTS project as the main developer of the s-bot robot platform, which was ranked on position 39 in the list of The 50 Best Robots Ever (fiction or real) by the Wired Journal in 2006. The SWARM-BOTS project was selected as FET-IST success story by the EU commission. He is author of more than 100 papers in the field of bio-inspired robotics and system level robot design. He is co-editor of several international conference proceedings. In November 2005 he received the EPFL Latsis University prize for his contributions to bio-inspired robotics. In 2011 he received the "Crédit Suisse Award for Best Teaching" from EPFL and in 2012 the "polysphère" award from the students as best teacher in the school of engineering. His interests include the development of innovative mechatronic solutions for mobile and modular robots, the creation of know-how for future embedded applications, and making robot platforms more accessible for education, research, and industrial development.

Official source

Related concepts (32)

A* search algorithm

A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.

Ant colony optimization algorithms

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.

Mobile robot

A mobile robot is an automatic machine that is capable of locomotion. Mobile robotics is usually considered to be a subfield of robotics and information engineering. Mobile robots have the capability to move around in their environment and are not fixed to one physical location. Mobile robots can be "autonomous" (AMR - autonomous mobile robot) which means they are capable of navigating an uncontrolled environment without the need for physical or electro-mechanical guidance devices.

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

Breadth-first search

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored. For example, in a chess endgame, a chess engine may build the game tree from the current position by applying all possible moves and use breadth-first search to find a win position for White.

Related lectures (64)

Graph Algorithms: Modeling and Traversal

Covers graph algorithms, modeling relationships between objects, and traversal techniques like BFS and DFS.

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Navigation: Basics of Mobile Robotics

Covers obstacle avoidance and navigation strategies in mobile robotics using sensors and potential fields.

Basics of Mobile Robotics: Components and Control

Covers the components and challenges of mobile robot control, including mechanics, locomotion, sensors, and architectures.

Search Algorithms: Abductive Reasoning