Navigation function | EPFL Graph Search

Navigation function usually refers to a function of position, velocity, acceleration and time which is used to plan robot trajectories through the environment. Generally, the goal of a navigation function is to create feasible, safe paths that avoid obstacles while allowing a robot to move from its starting configuration to its goal configuration. Potential functions assume that the environment or work space is known. Obstacles are assigned a high potential value, and the goal position is assigned a low potential. To reach the goal position, a robot only needs to follow the negative gradient of the surface. We can formalize this concept mathematically as following: Let be the state space of all possible configurations of a robot. Let denote the goal region of the state space. Then a potential function is called a (feasible) navigation function if if and only if no point in is reachable from . For every reachable state, , the local operator produces a state for which . Probabilistic navigation function is an extension of the classical navigation function for static stochastic scenarios. The function is defined by permitted collision probability, which limits the risk during motion. The Minkowski sum used for in the classical definition is replaced with a convolution of the geometries and the Probability Density Functionss of locations. Denoting the target position by , the Probabilistic navigation function is defined as: where is a predefined constant like in the classical navigation function, which ensures the Morse nature of the function. is the distance to the target position , and takes into account all obstacles, defined as where is based on the probability for a collision at location . The probability for a collision is limited by a predetermined value , meaning: and, where is the probability to collide with the i-th obstacle. A map is said to be a probabilistic navigation function if it satisfies the following conditions: It is a navigation function. The probability for a collision is bounded by a predefined probability .

Collision-Free Coordination of Fiber Positioners in Multi-object Spectrographs

Denis Gillet, Jean-Paul Richard Kneib, Laleh Makarem

Many ber-fed spectroscopic survey projects, such as DESI, PFS and MOONS, will use thousands of fiber positioners packed at a focal plane. To maximize observation time, the positioners need to move simultaneously and reach their targets swiftly. We have previously presented a motion planning method based on a decentralized navigation function for the collision-free coordination of the fiber positioners in DESI. In MOONS, the end-effector of each positioner handling the ber can reach the centre of its neighbours. There is therefore a risk of collision with up to 18 surrounding positioners in the chosen dense hexagonal conguration. Moreover, the length of the second arm of the positioner is almost twice the length of the rst one. As a result, the geometry of the potential collision zone between two positioners is not limited to the extremity of their end-effector, but surrounds the second arm. In this paper, we modify the navigation function to take into account the larger collision zone resulting from the extended geometrical shape of the positioners. The proposed navigation function takes into account the conguration of the positioners as well as the constraints on the actuators, such as their maximal velocity and their mechanical clearance. Considering the fact that all the positioners' bases are xed to the focal plane, collisions can occur locally and the risk of collision is limited to the 18 surrounding positioners. The decentralizing motion planning and trajectory generation takes advantage of this limited number of positioners and the locality of collisions, hence signicantly reduces the complexity of the algorithm to a linear order. The linear complexity ensures short computation time. In addition, the time needed to move all the positioners to their targets is independent of the number of positioners. These two key advantages of the chosen decentralization approach turn this method to a promising solution for the collision-free motion-planning problem in the next-generation spectroscopic survey projects. A motion planning simulator, exploited as a software prototype, has been developed in Python. The pre-computed collision-free trajectories of the actuators of all the positioners are fed directly from the simulator to the electronics controlling the motors. A successful demonstration of the effectiveness of these trajectories on the real positioners as well as their simulated counterparts are put side by side in the following online video sequence (https://goo.gl/YuwwsE).

Spie-Int Soc Optical Engineering2016

Decentralized multi-robot coordination in crowded workspaces

Laleh Makarem

The coordination of multi-robot systems is becoming one of the most important areas of research in robotics, mostly because it is required by numerous complex applications. These applications range from intelligent transportation systems, search and rescue robots, and medical robots, to cosmology and astrophysics. The coordination of multi-robot systems is based upon cooperation. The actions performed by each robot take into account the actions executed by the others in such a way that the whole system can operate coherently and efficiently. Regardless of the application, coordination is the key to the successful design and implementation of multi-robot systems. The number of robots involved in the aforementioned applications is increasing along with advances in miniaturization and automation. Consequently, a large number of robots need to share a workspace. This crowded workspace introduces new challenges into the coordination problem by increasing the risk of collision. To take into account communication constraints and sensor ranges, robots rely on local information. Therefore, efficient but simple coordination algorithms are required. This thesis investigates decentralized approaches based on navigation functions for the coordination of multi-robot systems in crowded workspaces. Decentralization allows robots to rely on local information, guarantees scalability and enables real-time deployment. Navigation functions are a special category of potential functions. Their negated gradient vector-field is attractive towards the goal and repulsive with respect to fixed or moving obstacles to avoid collision. In the first part of the thesis, we present the multi-robot coordination problem using navigation functions in a game-theory based framework. We propose a motion model along with a control law that leads the robots to a Nash equilibrium. The existence of the Nash equilibrium enables navigation functions to be exploited for studying, building, and running coordination frameworks for multi-robot systems. In the second part, we address the coordination of autonomous vehicles at intersections. A novel decentralized navigation function is proposed. It guarantees collision-free crossing of autonomous vehicles modeled as first order dynamic systems. The inertia of the vehicles is also introduced in the navigation functions to ensure deadlock-free coordination. The proposed approach does not require adaptation of the road infrastructure and relies upon onboard vehicles sensor data. Compared with traffic lights and roundabouts, the proposed method significantly reduces the travel time and the number of stops, thus decreasing energy consumption and pollution emission. This provides a strong motivation to pursue efforts towards the deployment of autonomous vehicles on roads. In the third part of the thesis, we investigate a coordination framework for a large number of miniaturized fiber positioner robots. The fiber positioner robots are designed and built as parts of the next generation of telescopes enabling large spectroscopic surveys. The proposed decentralized framework ensures the collision-free coordination of the fiber positioners sharing a crowed workspace at the focal plate of the telescope. The dynamical (max speed) and the mechanical (limited actuation range) constraints of the positioners are taken into account in the proposed coordination approach, which significantly reduces the time to reach a new robot configuration.

EPFL2015

Fluent coordination of autonomous vehicles at intersections

Denis Gillet, Laleh Makarem

In this paper we introduce a new decentralized navigation function for coordination of autonomous vehicles at intersections. The main contribution is a navigation function designed for vehicles with predefined paths that uses expected time to intersection for collision avoidance. In such way, deadlock situations are avoided. Different inertias of the vehicles are taken into account to enable on-board energy optimization for crossing. Heavier vehicles that need more energy and time for acceleration or braking are given an indirect priority at intersections. The proposed decentralized coordination scheme shows a significant improvement in energy consumption and in motion smoothness compared to traditional crossing with human drivers.

2012