Lattice-based motion planners are an established method to generate feasible motions for car-like vehicles. However, the solution paths can only reach a discretized approximation of the intended goal pose. Moreover, they can be optimal only with respect to the actions available to the planner, which can result in paths with excessive steering. These drawbacks have a negative impact when used in real systems. In this paper we address both drawbacks by integrating a steering method into a state-of-the-art lattice-based motion planner. Un- like previous approaches, in which path optimization happens in an a posteriori step after the planner has found a solution, we propose an interleaved execution of path planning and path optimization. The proposed approach can run in real-time and is implemented in a full-size autonomous truck, and we show experimentally that it is able to greatly improve the quality of the solutions provided by a lattice planner.

Autonomous navigation in real-world environments is still a challenging task in many respects. One of the key open challenges is fast planning of physically executable complex maneuvers under non-holonomic constraints. In recent years, lattice-based motion planners have been successfully used to generate kinematically and kinodynamically feasible motions for non-holonomic vehicles. However, it is not clear yet what algorithms are best to efficiently explore the lattice state space, while at the same time ensuring real-time performance. Here, we show how motion planning can greatly benefit from tapping into the latest results in path planning on grids, and we present a new version of Time-Bounded A*. Our version is designed to work for high-dimensional motion planning problems in real-world robotic applications. We demonstrate our algorithm in simulation and on a full-size autonomous truck.

Motion planning for a general 2-trailer system poses a hard problem for any motion planning algorithm and previous methods have lacked any completeness or optimality guarantees. In this work we present a lattice-based motion planning framework for a general 2-trailer system that is resolution complete and resolution optimal. The solution will satisfy both differential and obstacle imposed constraints and is intended either as a part of an autonomous system or as a driver support system to automatically plan complicated maneuvers in backward and forward motion. The proposed framework relies on a precomputing step that is performed offline to generate a finite set of kinematically feasible motion primitives. These motion primitives are then used to create a regular state lattice that can be searched for a solution using standard graph-search algorithms. To make this graph-search problem tractable for real-time applications a novel parametrization of the reachable state space is proposed where each motion primitive moves the system from and to a selected set of circular equilibrium configurations. The approach is evaluated over three different scenarios and impressive real-time performance is achieved.

Autonomous navigation in real-world industrial environments is a challenging task in many respects. One of the key open challenges is fast planning and execution of trajectories to reach arbitrary target positions and orientations with high accuracy and precision, while taking into account non-holonomic vehicle constraints. In recent years, lattice-based motion planners have been successfully used to generate kinematically and kinodynamically feasible motions for non-holonomic vehicles. However, the discretized nature of these algorithms induces discontinuities in both state and control space of the obtained trajectories, resulting in a mismatch between the achieved and the target end pose of the vehicle. As endpose accuracy is critical for the successful loading and unloading of cargo in typical industrial applications, automatically planned paths have not be widely adopted in commercial AGV systems. The main contribution of this paper addresses this shortcoming by introducing a path smoothing approach, which builds on the output of a lattice-based motion planner to generate smooth drivable trajectories for non-holonomic industrial vehicles. In real world tests presented in this paper we demonstrate that the proposed approach is fast enough for online use (it computes trajectories faster than they can be driven) and highly accurate. In 100 repetitions we achieve mean end-point pose errors below 0.01 meters in translation and 0.002 radians in orientation. Even the maximum errors are very small: only 0.02 meters in translation and 0.008 radians in orientation.

The problem of gas detection is relevant to many real-world applications, such as leak detection in industrial settings and surveillance. In this paper we address the problem of gas detection in large areas with a mobile robotic platform equipped with a remote gas sensor. We propose a novel method based on convex relaxation for quickly finding an exploration plan that guarantees a complete coverage of the environment. Our method proves to be highly efficient in terms of computational requirements and to provide nearly-optimal solutions. We validate our approach both in simulation and in real environments, thus demonstrating its applicability to real-world problems.

Coordinating fleets of autonomous, non-holonomic vehicles is paramount to many industrial applications. While there exists solutions to efficiently calculate trajectories for individual vehicles, an effective methodology to coordinate their motions and to avoid deadlocks is still missing. Decoupled approaches, where motions are calculated independently for each vehicle and then centrally coordinated for execution, have the means to identify deadlocks, but not to solve all of them. We present a novel approach that overcomes this limitation and that can be used to complement the deficiencies of decoupled solutions with centralized coordination. Here, we formally define an extension of the framework of lattice-based motion planning to multi-robot systems and we validate it experimentally. Our approach can jointly plan for multiple vehicles and it generates kinematically feasible and deadlock-free motions.

In this paper, we define and study the general framework of Simple Temporal Problems with Taboo regions (STPTs) and show how these problems capture metric temporal reasoning aspects which are common to many real-world applications. STPTs encode simple temporal constraints between events and user-defined taboo regions on the timeline, during which no event is allowed to take place. We discuss two different variants of STPTs. The first one deals with (instantaneous) events, while the second one allows for (durative) processes. We also provide polynomial-time algorithms for solving them. If all events or processes cannot be scheduled outside of the taboo regions, one needs to define and reason about "soft" STPTs. We show that even "soft" STPTs can be solved in polynomial time, using reductions to max-flow problems. The resulting algorithms allow for incremental computations, which is important for the successful application of our approach in real-time domains.

Coordinating multiple autonomous ground vehicles is paramount to many industrial applications. Vehicle trajectories must take into account temporal and spatial requirements, e.g., usage of floor space and deadlines on task execution. In this paper we present an approach to obtain sets of alternative execution patterns (called trajectory envelopes) which satisfy these requirements and are conflict-free. The approach consists of multiple constraint solvers which progressively refine trajectory envelopes according to mission requirements. The approach leverages the notion of least commitment to obtain easily revisable trajectories for execution.

Consider a house cleaning robot planning its activities for the day. Assume that the robot expects the human inhabitant to first dress, then have breakfast, and finally go out. Then, it should plan not to clean the bedroom while the human is dressing, and to clean the kitchen after the human has had breakfast. In general, robots operating in inhabited environments, like households and future factory floors, should plan their behavior taking into account the actions that will be performed by the humans sharing the same environment. This would improve human-robot cohabitation, for example, by avoiding undesired situations for the human. Unfortunately, current task planners only consider the robot's actions and unexpected external events in the planning process, and cannot accommodate expectations about the actions of the humans. In this article, we present a human-aware planner able to address this problem. Our planner supports alternative hypotheses of the human plan, temporal duration for the actions of both the robot and the human, constraints on the interaction between robot and human, partial goal achievement and, most importantly, the possibility to use observations of human actions in the policy generated for the robot. Our planner has been tested both as a stand-alone component and within a full framework for human-robot interaction in a real environment.

Intelligent environments are increasingly rich in ubiquitous sensing capabilities that can be leveraged to know which actions a user is engaged in at any given moment in time. The ability of an intelligent environment to recognize a high-level plan of activities performed by the user in a smart home would allow to construct proactive services, such as reminding, forecasting and providing timely physical support. This article proposes an approach to human activity recognition based on temporal planning. The approach leverages on one hand the ubiquitous sensors provided by the PEIS-Home, a sensor-rich intelligent environment, and, on the other hand, the temporal representation and reasoning capabilities of OMPS, a constraint-based temporal planning and scheduling framework.