Section: Research Program

Navigation and cooperation in dynamic environments

Participants : Olivier Simonin, Anne Spalanzani, Jilles S. Dibangoye, Christian Wolf, Laetitia Matignon, Fabrice Jumel, Jacques Saraydaryan, Christian Laugier, Alessandro Renzaglia, Mohamad Hobballah, Vincent Le Doze.

In his reference book Planning algorithms (Steven M. LaValle, Planning Algorithms, Cambridge University Press, 2006.) S. LaValle discusses the different dimensions that made the motion-planning problem complex, which are the number of robots, the obstacle region, the uncertainty of perception and action, and the allowable velocities. In particular, it is emphasized that complete algorithms require at least exponential time to deal with multiple robot planning in complex environments, preventing them to be scalable in practice. Moreover, dynamic and uncertain environments, as human-populated ones, expand this complexity.

In this context, we aim at scale up decision-making in human-populated environments and in multi-robot systems, while dealing with the intrinsic limits of the robots (computation capacity, limited communication).

Motion-planning in human-populated environment

Context. Motion planning in dynamic and human-populated environments is a current challenge of robotics. Many research teams work on this topic. We can cite the Institut of robotic in Barcelone [59], the MIT [48], the Autonomous Intelligent Systems lab in Freiburg [52], or the LAAS [80]. In Chroma, we explore different issues : integrating the risk (uncertainty) in planning processes, modeling and taking into account human behaviors and flows.

Objective We aim to give the robot some socially compliant behaviors by anticipating the near future (trajectories of mobile obstacle in the robot's surroundings) and by integrating knowledge from psychology, sociology and urban planning. In this context, we will focus on the following 3 topics.

Risk-based planning. Unlike static or controlled environments (known environment without uncertainty) where global path planning approaches are suitable, dealing with highly dynamic and uncertain environments requires to integrate the notion of risk (risk of collision, risk of disturbance). Then, we examine how motion planning approaches can integrate this risk in the generation and selection of the paths. An algorithm called RiskRRT was proposed in the previous eMotion team. This algorithm plans goal oriented trajectories that minimize the risk estimated at each instant. It fits environments that are highly dynamic and adapts to a representation of uncertainty [90] (see Figure 3.a for illustration). Now, we extend this principle to be adapted to various risk evaluation methods (proposed in 3.2) and various situation (highways, urban environments, even in dense traffic).

We also investigate the problem of learning recurring human displacements - or flows of humans - from robots embedded sensors. It has been shown that such recurring behaviors can be mapped from spatial-temporal observations, as in [92]. In this context, we explore counting-based mapping models [66] to learn motion probabilities in cells of a grid representing the environment. Then we can revisit cost-function of path-planning algorithms (eg. A*) by integrating the risk to encountering humans in opposite direction. We also aim at demonstrating the efficiency of the approach with real robots evolving in dense human-populated environments.

Recently we investigated the automatic learning of robot navigation in complex environments based on specific tasks and from visual input. We address this problem by combining computer vision, machine learning (deep-learning), and robotics path planning (see 7.4.2).

Sharing the physical space with humans. Robots are expected to share their physical space with humans. Hence, robots need to take into account the presence of humans and to behave in a socially acceptable way. Their trajectories must be safe but also predictable, that is why they must follow social conventions, respecting proximity constraints, avoiding people interacting or joining a group engaged in conversation without disturbing. For this purpose, we proposed earlier to integrate some knowledge from the psychology domain (i.e. proxemics theory), see figure 3.b. We aim now to integrate semantic knowledge (B. Kuipers, The Spatial Semantic Hierarchy, Artificial Intelligence, Volume 119, Issues 1–2, May 2000, Pages 191-233) and psycho-social theories of human behavior (Gibson, J. (1977). The theory of affordances, in Perceiving, Acting, and Knowing. Towards an Ecological Psychology. Number eds Shaw R., Bransford J. Hoboken,NJ: John Wiley & Sons Inc.) (Hall, E. (1966). The hidden dimension. Doubleday Anchor Books.) in the navigation framework we have developed for a few years (i.e. the Risk-based navigation algorithms [62], [90], [96]). These concepts were tested on our automated wheelchair (see figure 3.c) but they have and will be adapted to autonomous cars, telepresence robots and companion robots. This work is currently supported by the ANR Valet and the ANR Hianic.

Decision Making in Multi-robot systems

Context. A central challenge in Chroma is to define decision-making algorithms that scale up to large multi-robot systems. This work takes place in the general framework of Multi-Agent Systems (MAS). The objective is to compute/define agent behaviors that provide cooperation and adaptation abilities. Solutions must also take into account the agent/robot computational limits.

We can abstract the challenge in three objectives :

i) mastering the complexity of large fleet of robots/vehicles (scalability),

ii) dealing with limited computational/memory capacity,

iii) building adaptive solutions (robustness).

Combining Decision-theoretic models and Swarm intelligence.

Over the past few years, our attempts to address multi-robot decision-making are mainly due to Multi-Agent Sequential Decision Making (MA-SDM) and Swarm Intelligence (SI). MA-SDM builds upon well-known decision-theoretic models (e.g., Markov decision processes and games) and related algorithms, that come with strong theoretical guarantees. In contrast, the expressiveness of MA-SDM models has limited scalability in face of realistic multi-robot systems (Martin L. Puterman, Markov Decision Processes; Stuart Russell and Peter Norvig, Artificial Intelligence - A Modern Approach), resulting in computational overload. On their side, SI methods, which rely on local rules – generally bio-inspired – and relating to Self-Organized Systems (D. Floreano and C. Mattiussi, Bio-Inspired Artificial Intelligence - Theories, Methods, and Technologies, MIT Press, 2008.), can scale up to multiple robots and provide robustness to disturbances, but with poor theoretical guarantees (S. A. Brueckner, G. Di Marzo Serugendo, A. Karageorgos, R. Nagpal (2005). Engineering Self-Organising Systems, Methodologies and Applications. LNAI 3464 State-of-the-Art Survey, Springer book.). Swarm models can also answer to the need of designing tractable solutions [89], but they remain not geared to express complex realistic tasks or to handle (point-to-point) communication between robots. This motivates our work to go beyond these two approaches and to combine them.

First, we plan to investigate incremental expansion mechanisms in anytime decision-theoretic planning, starting from local rules (from SI) to complex strategies with performance guarantees (from MA-SDM) [57]. This methodology is grounded into our research on anytime algorithms, that are guaranteed to stop at anytime while still providing a reliable solution to the original problem. It further relies on decision theoretical models and tools including: Decentralized and Partially Observable Markov Decision Processes and Games, Dynamic Programming, Distributed Reinforcement Learning and Statistical Machine Learning.

Second, we plan to extend the SI approach by considering the integration of optimization techniques at the local level. The purpose is to force the system to explore solutions around the current stabilized state – potentially a local optimum – of the system. We aim at keeping scalability and self-organization properties by not compromising the decentralized nature of such systems. Introducing optimization in this way requires to measure locally the performances, which is generally possible from local perception of robots (or using learning techniques). The main optimization methods we will consider are Local Search (Gradient Descent), Distributed Stochastic Algorithm and Reinforcement Learning. We have shown in [93] the interest of such an approach for driverless vehicle traffic optimization.

Both approaches must lead to master the complexity inherent to large and open multi-robot systems. Such systems are prone to combinatorial problems, in term of state space and communication, when the number of robots grows. To cope with this complexity we explore several approaches :

• Combining MA-SDM, machine learning and RO (Operations Research) techniques to deal with global-local optimization in multi-agent/robot systems. In 2016, we started a collaboration with the VOLVO Group, in Lyon, to deal with VRP problems and optimization of goods distribution using a fleet of autonomous vehicles. We also explore such a methodology in the framework of the collaboration with the team of Prof. G. Czibula (Cluj Univiersity, Romania).

• Defining heuristics by decentralizing global exact solutions. We explore this methodology to deal with dynamic problems such as the patrolling of moving persons (see [86]). We also deal with dynamic-MRR (Multi-Robot Routing) problems in the context of the PhD of M. Popescu, see Section 7.5.1.2.

• Online incremental refining of the environment representation. This allows us to revisit mapping/coverage techniques and problems, see section 7.5.2.1[77].

Beyond this methodological work, we aim to evaluate our models on benchmarks from the literature, by using simulation tools as a complement of robotic experiments. This will lead us to develop simulators, allowing to deploy thousands of humans and robots in constrained environments.

Towards adaptive connected robots.

Mobile robots and autonomous vehicles are becoming more connected to one another and to other devices in the environment (concept of cloud of robots (see for instance the first International Workshop on Cloud and Robotics, 2016.) and V2V/V2I connectivity in transportation systems). Such robotic systems are open systems as the number of connected entities is varying dynamically. Network of robots brought with them new problems, as the need of (online) adaption to changes in the system and to the variability of the communication.

In Chroma, we address the problem of adaptation by considering machine learning techniques and local mechanisms as discussed above (SI models). More specifically we investigate the problem of maintaining the connectivity between robots which perform dynamic version of tasks such as patrolling, exploration or transportation, i.e. where the setting of the problem is continuously changing and growing (see [81]).

In Lyon, the CITI Laboratory conducts research in many aspects of telecommunication, from signal theory to distributed computation. In this context, Chroma develops cooperations with the Inria team Agora [81] (wireless communication protocols) and with Dynamid team [54] (middlleware and cloud aspects), that we wish to reinforce in the next years.