4. ROBOTIC SYSTEMS
4. ROBOTIC SYSTEMS
4.1. The SHARP Project
SHARP is an INRIA project carried on in common with the GRAVIR Laboratory of IMAG (CNRS, INPG, UJF).
The main goal of the Sharp project in the field of motion autonomy is to design a software architecture to control an automated vehicle and to enable it to move in an autonomous way. Automobile driving is the primary context of Sharp's research. This context makes it possible to address motion autonomy in a very general framework. Indeed, car-like vehicles are subject to motion constraints common to most terrestrial vehicles (from a kinematic and a dynamic point of view). Besides, the type of environments considered, from its dynamic and uncertain character (presence of moving obstacles whose future behavior is partially known if not unknown), is representative of a significant number of real environments.
Sharp works on these problems since 1986. A first control architecture was proposed and partially validated within the framework of the European project "Prometheus" [1986-1994]. Then, Sharp's involvement in two French programs, "Praxitèle" [1993-1997] and "La route automatisée" [1999] allowed the refinement of this architecture and its implementation on real vehicles for the realization of truly automated motions.
Autonomy in general and motion autonomy in particular has been a long standing issue in Robotics. In the late sixties, Shakey was one of the first robots able to move and perform simple tasks autonomously. Ever since, many authors have proposed control architectures to endow robot systems with various autonomous capabilities. These approaches differ in several ways, however it is clear that the control structure of an autonomous robot placed in a dynamic and partially known environment must have both deliberative and reactive capabilities.
The Sharp architecture aims at meeting these two requirements. It belongs to the family of the three-layered hybrid architectures (such as Atlantis, 3T or Hilare) that are based on three main functional layers: (1) a top layer which is in charge of the high-level planning and decision making (deliberative functions), (2) an intermediate layer whose purpose is to manage the various sequences of actions to execute, and (3) a lower layer that includes the reactive "skills" of the system (control and sensing functions).
In the Sharp architecture, the three previous layers are respectively represented by the Motion Planner, the Mission Scheduler, and the Motion Controller (presented in more detail later on). However, the efficiency and robustness of the architecture has been improved by introducing a new concept in order to produce the motion plans on-line: the concept of "Sensor-Based Manoeuvres" (SBM) that can be seen as "meta-skills" or general templates encoding the knowledge of how a given motion task is to be performed. The introduction of SBM was motivated by the observation that the kind of motion tasks that a vehicle has to perform can usually be described as a series of simple steps (a script). A SBM is basically a script, it combines control and sensing skills (i.e. elementary functions with real-time abilities). The Mission Scheduler can then efficiently produce motion plans by combining previously planned trajectories with appropriate instantiations of these generic SBM. This approach is justified by the fact that, in the type of applications considered, the number of different type of manoeuvres is finite and relatively small.
Motion planning deals with the a priori computation of the motion that is to be executed by a robotic system. In its basic form, motion planning addresses primarily collision avoidance with the stationary obstacles of the environment. However, when the robotic system considered is a vehicle, there is much more to motion planning than that. For a start, such a vehicle is subject to kinematic and dynamic constraints that restricts its motion capabilities. Then it moves among moving obstacles that should be avoided too. Finally, it is affected by various sources of uncertainty (control, sensing and model errors), that may lead to failure at execution time. Sharp has been working at designing novel motion planning techniques that take into account these constraints.
As far as motion planning in general is concerned, Sharp has proposed a novel motion planning scheme, the Ariadne's Clew Algorithm, which is generic and has been successfully applied to different motion planning problems.
From a kinematic point of view, wheeled vehicles are subject to nonholonomic constraints that restrict their motion capabilities (wheels should not slip, steering angles are usually limited). Such constraints makes motion planning more difficult. Sharp has addressed these issues and either improved existing techniques or proposed original solutions. Sharp works with two kinds of platforms: classical cars and bi-steerable cars that have better manoeuvring capabilities (such as the "Cycab" of Inria or the "Pi-Car" of the Paris-Sud University). As for classical cars, Sharp has proposed one of the first algorithms that compute paths with continuous-curvature and upper bounded curvature derivative. Experiments carried out with a real car have demonstrated the superiority, in terms of tracking precision, of this type of paths. As for bi-steerable cars, Sharp has proposed the first planner for these systems based on their structural property, namely their differential flatness.
In order to deal with time-dependent constraints (moving obstacles, dynamics of the vehicle), Sharp has introduced the state-time space concept. In this framework, time-dependent constraints are represented by static forbidden regions of state-time space. A trajectory maps to a curve in state-time space and motion planning can be reduced to finding a curve that avoids the forbidden regions. Such a curve must respect additional constraints due to the fact that time is irreversible and that velocity and acceleration constraints translate to geometric constraints on the slope and the curvature along the time dimension. However, it is possible to extend existing methods for path planning in configuration space in order to solve the problem at hand.
The underlying assumption of most motion planning techniques is that the vehicle should be able to execute the motion accurately enough. A challenging problem is that this assumption hardly holds for a real vehicle operating in the real world because of the various sources of uncertainty affecting the actual robot (sensing and control errors). A solution to this problem is to explicitly take into account uncertainty at planning time so as to compute safe motions that guarantee that the goal will be reached in spite of the uncertainty. Sharp has developed a safe motion planner that mainly relies upon: (a) simulations of the vehicle's sensing and localization systems, and (b) a novel type of landmarks used for localization purposes. The landmarks are built automatically, they simplify and improve localization.
When given a mission description, e.g. "park at location l", the Mission Scheduler generates a Parameterized Motion Plan (PMP) which is an ordered set of generic Sensor-Based Manoeuvres (SBM) possibly completed with nominal trajectories. The SBMs are selected from a SBM library, according to the current execution context. A SBM may require a nominal trajectory (it is the case for instance of the "Follow Trajectory" SBM). A nominal trajectory is a continuous time-ordered sequence of (position, velocity) of the vehicle that represents a theoretically safe and executable trajectory, i.e. a collision-free trajectory which satisfies the kinematic and dynamic constraints of the vehicle. When they are needed, such trajectories are computed by the Motion Planner, under the request of the Mission Scheduler. The involved SBMs, along with their associated nominal trajectories, are passed to the Motion Controller for their reactive executions.
The goal of the Motion Controller is to execute in a reactive way the current SBM of the PMP. For that purpose, the current SBM is instantiated according to the current execution context, i.e. the variable parameters of the SBM are set by using the a priori known or sensed information available at the time, e.g. road curvature, available lateral and longitudinal space, velocity and acceleration bounds, distance to an obstacle, etc. As mentioned above, a SBM combines control and sensing skills that are either parameterized control programs or sensor data processing functions. It is up to the Motion Controller to control and coordinate the execution of the different skills required. The sequence of Control Skills that is executed for a given SBM is determined by the events detected by the Sensor Skills. When an event that cannot be handled by the current SBM happens (e.g. the intrusion of an unexpected obstacle which cannot be avoided using the current Control Skills), the Motion Controller reports a failure to the Mission Scheduler which updates the current PMP either by applying a re-planning procedure (time permitting), or by selecting in real-time a SBM adapted to the new situation.
At a given time instant, the vehicle is carrying out a particular SBM that has been instantiated to fit the current execution context. SBMs are general templates encoding the knowledge of how a given motion task is to be performed. They combine real-time functions, control and sensing skills, that are either control programs or sensor data processing functions. From the practical point of view, a SBM can be seen as a specialized controller which generates safe and smooth motions for executing in a reactive way a given type of manoeuvre (i.e. by combining some predefined sensory modalities and controls).
Three types of SBM have been developed and tested: the "Trajectory Following", "Parallel Parking" and "Platooning" SBMs. The Orccad tool has been selected to implement both SBMs and skills: "Robot procedures" (in the Orccad formalism) are used to encode SBMs, while "robot-tasks" encode skills; robot procedures and robot tasks can both be represented as finite automata or transition diagrams. The Control Skills are used to control the motions of the vehicle and to activate the selected sensors; the task of the Sensing Skills is to evaluate the perception-based predicates or conditional statements involved.
4.2. MOLOG (MOtion for LOGistics) - Esprit LTR Project 28226
Duration: 1999-2002
Partners: LAAS-CNRS, Toulouse, France (Coordinator) ; University of Utrecht, The Netherlands ; EDF, Chatou, France ; Cadcentre, Cambridge, UK.
Over the past years the functionality and use of CAD systems has rapidly increased. It has become common practice to design large systems primarily by computer systems. These models are mainly designed to facilitate the construction and to test the functionality. However, the current functionalities of the CAD systems are inadequate to facilitate easy use for logistic engineering. In a more and more competitive market such as the energy sector nowadays production costs and downtime must be minimized.
Modern computer workstations and recently developed algorithmic techniques make it possible to extend CAD systems by adding tools that facilitate logistics engineering. In particular, recent developments in robot motion planning make it possible to add motion design functionalities that support the operator to make decisions about transportation of objects through the design. Such motions must be dealt with in the framework of a broader decision environment where obstacles, moving objects, and handling devices for moving the objects, are variable. The operator should be supported in the choice of route, handling device, etc., while constraints on the allowed motions can be specified.
The objective of MOLOG is to develop such motion design technology and integrate it in an existing CAD system to test its capabilities in real applications. The project consists of four, closely related parts:
The design and implementation of fast collision checkers to quickly decide whether particular motions are feasible.
The design and implementation of a general purpose motion planner that can handle and solve a large variety of motion planning problems (dealing with different constraints on the motion and the environments).
The design and implementation of a general tool to support the choice and use of handling devices to carry out required transportation tasks.
The integration of these three components into a major existing CAD system.
The approach is based on the analysis of practical generic motion problems defined by an experienced end-user (EDF-DER) to improve the product of a major provider (Cadcentre), on the basis of the experience of two academic institutes (LAAS-CNRS and Utrecht University) in motion planning research.
The outputs of MOLOG are:
New, general algorithmic techniques for collision detection, motion planning, and the planning of the use of handling devices;
A collection of general purpose software modules for adding motion design capabilities to various CAD systems;
The integration of these software modules into the CAD system PDMS of CADcenter, as a mean of testing the applicability of these capabilities by a collection of end-users including EDF-DER and members of PRUG (PDMS & REVIEW Users' Group of Cadcentre).