Motion planning with temporal-logic specifications: Progress and challenges

Abstract

Integrating task and motion planning is becoming increasingly important due to the recognition that a growing number of robotics applications in navigation, search-and-rescue missions, manipulation, and medicine involve reasoning with both discrete abstractions and continuous motions. The problem poses unique computational challenges: a vast hybrid discrete/continuous space must be searched while accounting for complex geometries, motion dynamics, collision avoidance and temporal goals. This paper takes the position that continued progress relies on integrative approaches that bring together techniques from robotics and AI. In this context, the paper examines robot motion planning with temporal-logic specifications and discusses open challenges and directions for future research. The paper aims to promote a continuing dialog between robotics and AI communities.

Keywords

Task planning discrete search motion planning temporal logic sampling-based algorithm

1. Introduction

A growing number of diverse robotics applications in mobile navigation, search-and-rescue missions, manipulation, game design and surgical procedures involve reasoning with both discrete actions and continuous motions. In this context, linear temporal logic (LTL) has often been used to express tasks by combining propositions with logical (∧ and, ∨ or, ¬ not) and temporal (◯ next, ♢ eventually, ⊔ until, □ always) operators. As an illustration, the task of inspecting several areas in a damaged building can be expressed as $\begin{matrix} (1) & ♢ π_{A_{1}} \land \dots \land ♢ π_{A_{n}}, \end{matrix}$ where $π_{A_{i}}$ denotes the proposition “robot inspected area $A_{i}$ ”. If the areas need to be inspected in a particular order, then the task can be expressed as $\begin{matrix} (2) & ♢ π_{A_{1}} \land (♢ π_{A_{2}} \land (♢ π_{A_{3}} (\dots ♢ π_{A_{n}}))) . \end{matrix}$ LTL can also be used to impose partial ordering, e.g., “inspect $A_{1}$ or $A_{2}$ before $A_{3}$ ”, $\begin{matrix} (3) & (\neg π_{A_{3}}) ⊔ ((π_{A_{1}} \lor π_{A_{2}}) \land ◯ π_{A_{3}}) . \end{matrix}$ As another example, the task “after cleaning a dirty area go to a waste station”, can be expressed as $\begin{matrix} (4) & \begin{matrix} □ ((π_{D_{1}} \lor \dots \lor π_{D_{n}}) \\ ⟹ ♢ (π_{W_{1}} \lor \dots \lor π_{W_{m}})), \end{matrix} \end{matrix}$ where $π_{D_{i}}$ and $π_{W_{j}}$ denote the propositions “robot cleaned area $D_{i}$ ” and “robot is in waste station $W_{j}$ ”.

Given a robot model, an initial state, a description of the environment and a task specification as a formula ϕ in LTL, the combined task- and motion-planning problem considered in this paper is to plan a collision-free and dynamically-feasible motion trajectory that satisfies ϕ. Such problem poses unique computational challenges stemming from (i) robot dynamics and collision avoidance, (ii) temporal constraints and (iii) intertwined dependencies between motion trajectories and temporal constraints.

At the continuous level, the planner needs to generate dynamically-feasible motions that the robot can execute in the physical world. Robot dynamics express physical constraints on the feasible motions, such as bounding the velocity and directions of motions, ensuring a minimum turning radius or keeping the wheels from sliding sideways. Moreover, the presence of obstacles makes planning more challenging since the planned motions must also be collision-free, often requiring the robot to pass through narrow passages and unstructured terrains.

Challenges arise at the discrete level, as well, and significant work in AI is devoted to task planning [70]. In this domain, the task is typically broken down into sequences of actions to be executed by the robot. In this context, LTL has been used to plan for temporally extended goals [3] and to define the semantics for planning languages [55]. Other temporal logics, such as temporal action logic, have also been developed to facilitate reasoning about actions and change [20,47].

When considering the combined motion-planning problem with dynamics and LTL specifications, there are additional challenges due to the intertwined dependencies. In fact, a discrete solution that satisfies an LTL formula ϕ may not be feasible due to constraints imposed by obstacles and dynamics. In the other direction, collision-free and dynamically-feasible trajectories may violate constraints imposed by ϕ.

This paper takes the position that continued progress in addressing the combined task- and motion-planning problem requires integrative approaches that bring together techniques from robotics and AI. The paper examines recent progress and discusses open challenges and directions for future research. The discussion is motivated by the following questions:

What components enable a successful coupling of planning in discrete and continuous spaces?

How can advances in discrete planning and motion planning be leveraged to enhance the performance of the overall framework?

How can the framework employ information gathered about the space it explores to adapt itself to relevant unexplored discrete actions and continuous regions?

What theoretical guarantees can be offered?

How can the framework adapt to changing environmental and contextual conditions?

The discussion takes place in the context of integrating task and motion planning when dealing with high-dimensional systems, nonlinear dynamics, and tasks given by LTL. This is by no means an exhaustive discussion of the burgeoning body of work on integrating task and motion planning, which also covers manipulation, uncertainty, planning languages and other aspects [10,12,16,22,25,33,48,62,68,74,81,82]. Several workshops at robotics and AI conferences have also been dedicated to this topic. The goal of this paper is to contribute to the dialog between the two communities.

The paper is organized as follows. Section 2 discusses progress and challenges in motion planning. Section 3 discusses the LTL formalism for task specification. Section 4 discusses controller-synthesis approaches. Section 5 focuses on key aspects and challenges when coupling discrete planning and sampling-based motion planning. Section 6 discusses results in theoretical analysis and their ramifications. Section 7 presents replanning as a viable approach to adapt to dynamic environments. The paper concludes in Section 8 with a brief summary of the main discussion points.

2. Robot motion planning

The motion-planning problem is to find a trajectory from an initial state to a goal state while avoiding collision with obstacles. This is an essential problem that is embedded in almost all robotics applications [17,50].

While initially considered in a geometric setting, such as the piano mover’s problem [72], motion planning for complex robots requires taking into account the robot dynamics so that the planned motions can be executed in the physical world. The continuous, dynamically-feasible, motion of a robot is often formalized using a function $ζ : [0, T] \to S$ that satisfies an ordinary differential equation of the form $\begin{matrix} (5) & \dot{ζ} (t) = f (ζ (t), u (t)) \end{matrix}$ for some $u : [0, T] \to U$ , for all $t \in [0, T]$ , where $S \subset R^{n}$ and $U \subset R^{m}$ are the state space and the control space, respectively. A state $s \in S$ defines position, orientation, velocity, steering angle and other components that change as a result of motion. A control input defines external inputs such as acceleration and change in steering angle which are used to control the robot. As an example, the motions of a vehicle can be expressed as $\begin{array}{rcl} (6) & \begin{matrix} \dot{x} = v cos (θ) cos (ψ), \\ \dot{y} = v sin (θ) cos (ψ), \end{matrix} \\ (7) & \dot{θ} = v sin (ψ) / L, \dot{v} = u_{a}, \dot{ψ} = u_{ω}, \end{array}$ where the state $(x, y, θ, v, ψ)$ consists of the position $(x, y)$ , orientation θ, velocity v and steering angle ψ, the control input consists of the acceleration $u_{a}$ and the rate $u_{ω}$ at which the steering wheel is turned, and the body length is given by L.

Even when not considering the dynamics, motion planning is PSPACE-hard [69]. Complete algorithms, which provide a solution if one exists and return failure otherwise, are conceptually complex, hard to implement, and have an exponential dependency on the degrees-of-freedom (DOFs) of the robot [11]. These computational hardness results are directly related to the curse of dimensionality: the size of the search space gets large exponentially fast with the number of DOFs. When dynamics are taken into account, the problem becomes undecidable since differential equations can be used to simulate arbitrary Turing machines [8].

Often, practical approaches to motion planning relax this completeness guarantee in order to alleviate the difficulties implied by the curse of dimensionality. Sampling-based motion planning in particular has resulted in many practical algorithms which guarantee only probabilistic completeness, i.e., a solution is found, when it exists, with probability approaching one as the number of samples approaches infinity [17,50]. The key insight is to selectively sample and explore the space of feasible motions. Numerous formulations have been developed, most notably PRM [38], RRT [51] and others [28,31,35,61,65,75] (see [17,50] for more). To account for dynamics, sampling-based approaches typically expand a motion tree starting from the initial state and incrementally adding collision-free and dynamically-feasible trajectories as branches, as shown in Fig. 1.

Sampling-based motion planners have now been used to solve high-dimensional problems ranging from navigation, manipulation, to computational biology and medicine [2,9,45,58,76]. Another success story has been their use in the DARPA Urban Challenge, which required teams to build a fully autonomous car that can navigate in urban traffic. In a fierce competition, among close to one hundred teams, MIT’s entry vehicle Talos was one of the six vehicles that successfully completed a course of sixty miles [52]. Talos (Fig. 2) uses state-of-the-art estimation algorithms to fuse all the sensory information obtained from its laser-range finders, radars, cameras and navigation system into a live local map of drivable regions and obstacles/hazards. To navigate through this map, Talos uses a carefully-engineered RRT-based planning algorithm.

Fig. 1.

Illustration of sampling-based tree search. Curves shown in red correspond to collision-free and dynamically-feasible trajectories, which are obtained by applying input controls and integrating the differential equations of motion. (The colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-150682.)

Fig. 2.

Left: Talos, team MIT’s entry vehicle in the DARPA Urban Challenge. Right: The tree maintained by the RRT algorithm is shown overlayed on the obstacle map. The trajectories that make up the tree are shown in yellow and blue tones, the obstacles are shown in red, the drivable region is shown in black. The left-, front- and right-camera views are shown at the top of the figure to the right. (The colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-150682.)

Motion planning, however, has generally considered just the reachability problem of computing a trajectory to the goal region. PRM, RRT and other sampling-based algorithms were not designed to take into account high-level specifications given by formal models, such as LTL. As discussed in the rest of the paper, there are significant challenges when considering the combined task- and motion-planning problem.

3. Task specifications via temporal languages

There are fundamental research issues in developing task-specification formalisms, particularly as it relates to balancing expressiveness with ease-of-use, and ensuring amenability to efficient computation and reasoning. To increase expressiveness and facilitate interaction, it is beneficial to describe tasks in an easy-to-use yet expressive structured language, which can internally be translated into a formalism based on well-established logics, such as LTL [67].

3.1. LTL syntax

Let Π denote a set of propositions, where each $π_{i} \in Π$ corresponds to a truth-valued statement, e.g., “robot is in area A”, “object detected”, “measurement taken”. An LTL formula is formed by combining propositions with logical (and ∧, or ∨, not ¬) and temporal operators (next ◯, until ⊔, eventually ♢, always □).

Definition 1.
Every proposition $π \in Π$ is a formula. If ϕ and ψ are formulas, then so are $\begin{matrix} \neg ϕ, ϕ \land ψ, ϕ \lor ψ, ◯ ϕ, ϕ ⊔ ψ, ♢ ϕ, □ ϕ . \end{matrix}$ Let $σ = τ_{0}, τ_{1}, \dots$ denote an infinite sequence, where each $τ_{i} \in 2^{Π}$ . Let $σ^{i} = τ_{i}, τ_{i + 1}, \dots$ denote the ith postfix of σ. The notation $σ ⊨ ϕ$ indicates that σ satisfies ϕ and is defined as $\begin{array}{rcl} σ ⊨ π if π \in Π and π \in τ_{0}, \\ σ ⊨ \neg ϕ if σ ⊭ ϕ, \\ σ ⊨ ϕ \land ψ if σ ⊨ ϕ and σ ⊨ ψ, \\ σ ⊨ ◯ ϕ if σ^{1} ⊨ ϕ, \\ σ ⊨ ϕ ⊔ ψ if \exists k ⩾ 0 such that \\ σ^{k} ⊨ ψ and \forall 0 ⩽ i < k : σ^{i} ⊨ ϕ . \end{array}$ Moreover, $⊥ \equiv π \land \neg π$ , $⊤ \equiv \neg ⊥$ , $ϕ \lor ψ \equiv \neg (\neg ϕ \land \neg ψ)$ , $♢ ϕ \equiv ⊤ ⊔ ϕ$ , $□ ϕ \equiv \neg ♢ \neg ϕ$ .

The expressiveness of temporal logic makes it possible to consider different constructs, such as
coverage: “inspect $A_{1}, \dots, A_{n}$ in any order” $♢ π_{A_{1}} \land \dots \land ♢ π_{A_{n}}$ ;

sequencing: “inspect $A_{1}$ , $A_{2}$ , $A_{3}$ in order” $♢ π_{A_{1}} \land (♢ π_{A_{2}} \land (♢ π_{A_{3}}))$ ;

partial ordering: “take measurements in $A_{1}$ or $A_{2}$ before $A_{3}$ ” $(\neg π_{M_{3}}) ⊔ ((π_{M_{1}} \lor π_{M_{2}}) \land ◯ π_{M_{3}})$ ;

conditions: “if ship detected, then track until identified” $□ ((π_{ship} \Rightarrow (π_{track} ⊔ π_{identified})))$ ;

avoidance and persistency: “avoid hazardous areas; move slowly” $□ (\neg π_{H_{1}} \land \dots \land \neg π_{H_{n}} \land π_{slow})$ ,
where $π_{A_{i}}$ , $π_{M_{i}}$ , $π_{ship}$ , $π_{track}$ , $π_{identified}$ , $π_{H_{i}}$ , $π_{slow}$ denote “robot inspected area $A_{i}$ ”, “robot took measurements in area $A_{i}$ ”, “robot detected ship”, “robot tracked ship”, “robot identified ship”, “robot is in the hazardous area $H_{i}$ ” and “robot is moving slowly”, respectively.

Based on the compositional nature of LTL, complex tasks can be constructed by composing simpler ones. As an illustration, the task of using an underwater vehicle to inspect an offshore platform can employ propositions that express detection of pipes, valves, anchors, anchor lines, flotation chambers and other components, and their status (damaged or functional). Partial ordering constructs can be used to prioritize the inspection of critical components. Conditional constructs can be employed to carry out closer inspections when there is some indication of damage of a particular component. Avoidance and persistency can ensure that the vehicle maintains a safe minimum distance away from the platform components, while still being close enough to carry out inspections. Coverage criteria can ensure that all components have been inspected.
3.2. LTL semantics over motion trajectories

The semantics of a proposition $π \in Π$ is defined over the continuous state space $S$ by a function ${HOLDS}_{π} : S \to {⊤, ⊥}$ , which indicates whether or not $s \in S$ satisfies π. A mapping $τ : S \to 2^{Π}$ defines all the propositions satisfied by s, i.e., $\begin{matrix} (8) & τ (s) = {π : π \in Π \land {HOLDS}_{π} (s) = ⊤} . \end{matrix}$ The semantics of an LTL formula is defined over continuous trajectories $ζ : R_{⩾ 0} \to S$ . As the continuous state changes according to ζ, the discrete state, obtained by τ, may also change. In this way, ζ maps to a sequence of discrete states $w_{ζ} = {[τ_{i}]}_{i = 1}^{n}$ with $τ_{i} \neq τ_{i + 1}$ , referred to as the word generated by ζ. Figure 3 provides an illustration.

Fig. 3.

Trajectory generates the word $[\emptyset, {π_{3}}, \emptyset, {π_{1}}, \emptyset]$ , where $π_{i}$ denotes the proposition “robot is in area $P_{i}$ ”. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-150682.)

In this way, when $w_{ζ}$ is infinite, ζ is said to satisfy an LTL formula ϕ if $w_{ζ} ⊨ ϕ$ . When $w_{ζ}$ is finite, ζ satisfies ϕ if any extension of $w_{ζ}$ to an infinite sequence satisfies ϕ, i.e., $w_{ζ} σ ⊨ ϕ$ for any infinite sequence $σ = τ_{0} τ_{1} \dots$ , where each $τ_{i} \in 2^{Π}$ .

The combined task- and motion-planning problem is then to compute a control function $u : [0, T] \to U$ such that the dynamically-feasible trajectory $ζ : [0, T] \to S$ obtained by applying u to the initial state $s_{init} \in S$ , i.e., $\begin{matrix} (9) & \forall t \in [0, T] : ζ (t) = s_{init} + \int_{h = 0}^{t} f (ζ (h), u (h)) d h, \end{matrix}$ is collision free and satisfies ϕ.

4. Controller-synthesis from LTL specifications

A growing body of work has focused on synthesizing reactive controllers that satisfy LTL specifications. These approaches rely on a discrete abstraction of the continuous system, often obtained by partitioning the continuous state space into polytopes. Propositions are defined over the polytopes and actions refer to discrete functions of the robot such as move left, right, up, down, stand up, sit down. The overall behavior of the robot is captured by an automaton which is synthesized from the LTL specification and the discrete abstraction using techniques from model checking. Each transition in the automaton corresponds to an action with well-defined preconditions and postconditions. In order for the automaton to be viable, controllers must be available for each action that are capable of generating collision-free and dynamically-feasible trajectories that are compatible with the action. The work in [26] obtained the discrete abstraction as a graph whose vertices correspond to regions in a workspace decompositions and edges capture the physical adjacency of the regions. Given an LTL formula over propositions of the form “robot is in region $R_{i}$ ”, model checking was used to compute a discrete path as a sequence of regions that the robot should visit. A controller was then used to drive a point robot along the discrete path from one region to the next. Assuming perfect sensors, the work in [43,44] develops a framework for sensor-based temporal logic motion planning where the synthesized automaton enables the robot to respond to changes in the environment. The assumption of perfect sensing is later relaxed resulting in the synthesis of controllers which satisfy the given LTL specification with a certain probability [32]. Work by Belta et al. [5] uses controllers and motion primitives to satisfy LTL specifications. Extensions in [13,40] use hierarchical abstractions to control a team of robots. Automata learning is used in [14] to develop predictive models of when doors in an office setting are open in order to satisfy LTL specifications that require the robot to go through doors. Receding horizon is used to generate controls that satisfy LTL specifications [85] and to accommodate local events [79]. Dynamic programming is used to construct an optimal trajectory that satisfies a given LTL specification while minimizing a weighted average cost function [83]. There is also work to accommodate partially-known or uncertain environments [29,53,71]. Controller synthesis has also been extended to signal temporal logic, which allows temporal properties of real-valued signals.

Controller-synthesis approaches generally assume that bisimulation holds, which requires the discrete transition system to behave the same as the underlying continuous system with respect to the LTL specification. Controllers are also required in order to implement the transitions of the automaton synthesized from the LTL specification and the discrete abstraction. A challenging problem in controller synthesis is the design of controllers which can implement the automaton transitions for high-dimensional systems with nonlinear dynamics [15,21]. In certain cases, specifically when the differential equations of motions correspond to a smooth continuous vector field, reachable tubes and sequential controller compositions can be used to implement the automaton transitions [19]. When constrained reachability problems can be solved for the system with nonlinear dynamics, e.g., by means of sampling-based motion planning or reachable sets, the work in [84] provides a framework that continually refines the discrete abstraction until a control policy is found that is compatible with the LTL specification.

5. Coupling of discrete planning and sampling-based motion planning

Another line of research has focused on motion planning with LTL specifications for high-dimensional robotic systems with nonlinear dynamics. This research treats the combined task- and motion-planning problem as probabilistic search over a hybrid space consisting of discrete and continuous components [6,7,56,57,63,66,80]. The continuous layer is defined by the underlying state space, input controls and robot dynamics. Drawing from the success of sampling-based motion planning, the continuous layer uses a motion tree $T$ as the basis for conducting the search in the continuous space $S$ . The discrete layer is obtained by considering a simplified and discrete representation of the problem. In many cases, the discrete layer corresponds to the product space of a workspace decomposition and an automaton representing the LTL formula [46].

The key aspect is the coupling of sampling-based motion planning to handle the complexity arising from high-dimensional robotic systems, nonlinear dynamics and collision avoidance with discrete search to handle discrete abstractions and LTL specifications. Figure 4 provides a schematic illustration. Note that the search can progress much more rapidly in the discrete layer, since it uses a simpler, discrete abstraction. This means that the framework can afford to do more exploration in the discrete layer and then use the results of the discrete search to guide the search in the continuous layer. Conceptually, the role of the discrete layer is to suggest to the continuous layer feasible directions in the form of discrete states along which to expand the motion tree. The continuous layer then, as it expands the motion tree along the suggested directions, analyzes the progress that it makes, and feeds back valuable information to the discrete layer so that it can further improve its search. As a result, the discrete layer could suggest to the continuous layer a different direction for expanding the motion tree in the next iteration. By receiving increasingly feasible directions to guide the expansion, the continuous layer can make additional progress, and eventually the framework will generate a collision-free and dynamically-feasible trajectory that satisfies the task specification.

Fig. 4.

Synergistic coupling of sampling-based motion planning and discrete search for the combined task- and motion-planning problem with LTL specifications and nonlinear dynamics. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-150682.)

5.1. Feasibility of discrete plans

An issue that arises relates to the feasibility of the discrete plans. It is important to note that not every discrete plan is feasible. In some cases, due to the robot dynamics and interactions with the environment, it may not be possible to expand the motion tree $T$ along the direction indicated by the discrete plan σ. Therefore, it becomes important to distinguish between feasible and infeasible discrete plans. Since it is not known a priori which discrete plans are feasible, an important research direction is to develop effective estimations of the feasibility of the discrete plans. In this context, the first step is to determine the information that should be used for the feasibility estimates. Since a discrete plan σ is considered feasible when $T$ can be expanded along σ, then sampling-based motion planning provides the most up-to-date and relevant information for the feasibility estimates. We can measure the progress made in expanding $T$ to reach each discrete state in σ, the time spent extending $T$ , and other quantities that provide valuable information in determining the feasibility of σ. This information can be quantified by a function $FEAS : σ \mapsto R_{> 0}$ , where a large value of $FEAS (σ)$ indicates that the discrete plan σ is deemed feasible.

During discrete planning, the feasibility estimates, should be used to select more frequently plans that are deemed highly feasible. This provides the greedy component to the search, by guiding it along directions that are estimated to lead to a solution. To balance greedy with methodical search, less feasible plans should not be completely ignored, but should be selected less frequently. This is particularly relevant in the early stages of the search, where not enough information has been collected to properly evaluate the feasibility of the discrete plans. It is also crucial for the theoretical analysis to ensure probabilistic completeness.

5.2. Integration spectrum

The coupling of discrete planning and sampling-based motion planning opens up a wide spectrum of integration possibilities.

Complete plans: At one end of the spectrum, discrete planning can compute an entire discrete sequence $σ = {[τ_{i}]}_{i = 1}^{n}$ that satisfies the task specification ϕ in order to guide sampling-based motion planning. In this way, the search exhibits confidence in the internal estimates and greedily guides the exploration toward what it deems is a feasible direction to obtain a solution trajectory. Sampling-based motion planning can balance the greedy component by abandoning the exploration early and requesting alternative discrete plans when it does not make sufficient progress.

Partial plans: At the other end of the spectrum, discrete planning can compute just a single discrete state $τ_{1}$ . It is still desirable to select $τ_{1}$ from a discrete plan that satisfies ϕ but without having to compute the entire plan. Research on this topic indicates that in many cases considerable computational time can be saved [54]. Selecting a single discrete state gives the framework the flexibility to quickly change direction based on the tree-expansion progress. This approach can be appropriate especially when more information is needed to justify longer computational times dedicated to one particular discrete plan.

Adjusting the length of the discrete plan based on exploration information: It may also be beneficial to dynamically adjust the length of the discrete plan based on the progress being made. Initially, preference could be given to short sequences to favor exploration over exploitation. As the tree is expanded, the framework can be more confident about its internal estimates, and so it can gradually increase the length of discrete sequences to allow for complete plans.

Criteria on where to be in the above spectrum can be useful in improving the overall performance. Finding the right balance in the above spectrum will depend on the nature of the application as well as the information gathered from the overall search and exploration.

5.3. Tradeoffs

This line of research, which couples discrete search with sampling-based motion planning, is capable of taking into account high-dimensional systems and nonlinear dynamics. It, however, places some restrictions on the LTL specifications. In particular, it supports only syntactically co-safe LTL formulas, which use ¬, ∨, ∧, ◯, ♢, ⊔ but not □ when written in positive-normal form (¬ appears only in front of atomic propositions) [73]. Syntactically co-safe LTL can be interpreted over finite discrete traces, which is necessary when planning finite motion trajectories. This provides a tradeoff with controller-synthesis approaches which can handle a broader fragment of LTL but require bisimulation and the availability of controllers to implement the automaton transitions.

6. Theoretical foundations of sampling-based algorithms for joint task and motion planning

Sampling-based approaches often relax the completeness guarantees to probabilistic or resolution completeness. Similarly, rather than optimality, they provide guarantees on convergence towards optimal solutions. Computational complexity results often relate to the “visibility” of the free space, or they can be analyzed with the help of convergence rates. Along with these, other directions for theoretical analysis emerge in combined task- and motion-planning problems with temporal logic specifications. For example, how expressive and succinct is the task-specification language? How do the expressiveness properties of the specification language relate to the various performance measures for the algorithm, such as completeness, asymptotic optimality, convergence rate and computational complexity? This section discusses these issues and highlights some open problems.

6.1. Expressiveness of temporal logic

First important question is concerned with the expressive power of the task-specification language. What exactly is the expressive power of different languages? For example, can LTL describe all possible motion-planning problems? How restricted is co-safe LTL?

Consider first determining the most expressive language for motion planning. Note that our objective is to find a motion that satisfies the specification. Hence, the specification language is linear time [67], since it describes a single motion rather than a branching-time property [23], such as those that describe all motions of a dynamical system. Hence, ideally the specification language should be able to describe all linear-time properties. Unfortunately, LTL is not sufficient as it cannot describe certain linear-time properties [23,67].

Fortunately, there are other languages that can describe all linear-time properties. One such language is the set of all ω-regular specifications, which is equivalent to the set of nondeterministic Büchi automata [77]. On the other hand, LTL is equivalent to the set of all deterministic Büchi automata [67]. However, non-deterministic Büchi automata are strictly more expressive than their deterministic version, which makes LTL weaker than the set of all ω-regular languages.

Another widely-studied language is μ-calculus [18,24], which is often used to analyze the expressive power of various temporal logics. It turns out that the deterministic fragment of μ-calculus is equivalent to the set of all ω-regular languages. Hence, if one were to design an efficient sampling-based algorithm for planning problems with μ-calculus, nondeterministic Büchi automata, or ω-regular specifications, it would be powerful enough to answer any problem instance described by a linear-time specification.

Second, it is possible that the most expressive languages lead to conceptually and computationally complex algorithms. In fact, this task can be analytically fairly challenging. Hence, there is value in considering subsets of linear-time specifications that may lead to simpler, more efficient algorithms. An important class of tasks are those that do not include a persistent component, that is, those specifications which describe tasks that terminate. The set of such specifications are described by the co-safe fragment of LTL [73].

Third, the incorporation of timed specifications still remains largely open. How can we specify a constraint of the form: “reach the goal region within the next 5 minutes”? Fortunately, there are temporal logics that can describe such specifications. For example, the metric temporal logic (MTL) [42] extends LTL with time intervals. As an illustration, $♢_{[3, 5]} π$ indicates not only that π should be eventually satisfied but that it must be so between 3 and 5 time units after the start.

Finally, how can uncertainty and adversaries be included in the specification? For example, the probabilistic temporal logic (PTL) [30] provides the necessary operators to describe chance constraints on specifications. It is possible to specify that a proposition will eventually hold, with at least 95% probability. In this context, controller synthesis has been used to account for specifications given as a formula in probabilistic computation tree logic (PCTL) [49].

It is crucial that all these languages are explored in the context of robot motion planning. This endeavor will allow us to understand the added conceptual and computational complexity in the algorithms as the expressive power of the language increases.

6.2. Systems with non-trivial differential constraints

Designing planning algorithms for systems with non-trivial differential constraints has long been a challenge in motion planning [15,17,21,50]. Research has shown that PRM approaches have had limited applicability in motion planning with non-trivial differential constraints since each roadmap edge $(s_{i}, s_{j})$ requires connecting the state $s_{i} \in S$ to $s_{j} \in S$ via a feasible trajectory that satisfies the differential constraints imposed by the robot dynamics. Exact solutions to this two-point boundary value problem are available only in limited cases [59,78], while numerical solutions impose significant computational cost, rendering roadmap construction impractical [39]. In fact, sampling-based algorithms that incrementally expand a motion tree, such as RRT and EST, were proposed mainly for systems with complex differential constraints that do not admit exact steering.

Thus, it is reasonable to expect that similar challenges arise also when integrating task and motion planning. In fact, these challenges may have certain implications on the class of specification languages that the algorithmic approach can accommodate. For instance, designing sampling-based algorithms that can handle all linear-time specifications may be limited to exact steering functions, since the persistent motion may need to include a loop [18]. However, focusing on, for example, the co-safe fragment of LTL, may alleviate some of these problems and allow the algorithmic approach to handle a large class of dynamical systems.

6.3. Computational complexity, probabilistic completeness and asymptotic optimality

Many robotic problems involve online settings, where the environment is not fully known a priori, but it is discovered on the fly. Furthermore, the environment is often dynamic as there could be moving objects in addition to static obstacles. While taking into account these requirements, the algorithms must also be amenable to real-time computation.

It is for these reasons that sampling-based algorithms often incrementally expand a motion tree. In this way, the motion tree can be adapted to online settings and dynamic environments. Sampling-based algorithms for joint task and motion planning embody these properties. In fact, when a new vertex v is added to the motion tree, the motion trajectory $ζ_{v}$ from the root to v is incrementally checked to determine if it satisfies the task specification. On the other hand, most algorithms developed in the control-theory literature first generate an abstraction, and then design a controller on this abstraction. As the abstraction must provide the bisimulation property, it remains challenging to adapt these approaches for high-dimensional systems with nonlinear dynamics. Moreover, small changes in the environment require the abstraction to be recomputed. Hence, this “top–down” approach of first constructing a bisimulation-equivalent discrete abstraction and then designing a controller is useful in control design but has limitations in robotics applications. Instead, sampling-based approaches embrace a “bottom–up” approach, where the discrete abstraction is generated incrementally and the motion plans are updated as this abstraction gets finer, as shown in Fig. 5.

Fig. 5.

Incremental generation of a discrete abstraction. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/AIC-150682.)

The theoretical properties of sampling-based approaches for joint task and motion planning are motivated with these issues in mind. We describe these theoretical properties in this section.

First, the completeness requirements are often tied to the number or the density of the samples. For example, the randomized algorithms guarantee probabilistic completeness. For algorithms that employ deterministic approaches, resolution completeness properties can be formulated in a similar manner.

Second, some algorithms may improve their solutions, for example, with respect to a cost function, if they are allowed more samples, for instance, guaranteeing asymptotic optimality, i.e., almost-sure convergence towards optimal solutions.

Finally, the proposed algorithms should be analyzed in terms of computational complexity. Since incremental algorithms do not necessarily terminate, their analysis requires, for instance, computing the expected time until termination, when the algorithm terminates. For algorithms that converge to optimal solutions, convergence rates provide the best estimate regarding the computational complexity of the algorithms.

6.4. Current progress and future directions

On the one hand, it has been shown that probabilistically-complete sampling-based algorithms can be extended to handle all linear-time specifications [34], even guaranteeing asymptotic optimality [36]. Surprisingly, these extensions can be established without incurring too much computational overhead when compared to popular sampling-based algorithms for motion planning, such as PRM and RRT [34,36]. However, this approach is, unfortunately, limited to dynamical systems that admit an exact steering function.

On the other hand, sampling-based algorithms that can handle a large class of dynamical systems with co-safe LTL specifications have been developed [6,7,60,63,64], as discussed in Section 5.

Despite these advances, very little has been achieving in developing the theoretical foundations of the sampling-based approach for joint task and motion planning with temporal logic specifications. Progress must be made in understanding the trade-offs between three directions: (i) expressive power of specification languages, (ii) geometric/differential complexity of the underlying dynamics and (iii) the formal theoretical guarantees on probabilistic/resolution completeness, asymptotic optimality and computational complexity.

7. Robust replanning to adapt to changing environmental and contextual conditions

Even when dynamics and obstacles are taken into account during planning, it is still expected that, at certain times, the robot may diverge or fail to follow the planned motions due to the intricacies of the physical world, uncertainty in the motion outcomes, incomplete maps or changes in the environment. The need for a new plan also arises in response to locally-sensed events, such as avoiding unanticipated obstacles or exploring surrounding areas when detecting an object of interest. To adapt to changing environmental and contextual conditions, it becomes important to complement reactive behaviors to avoid immediate dangers with replanning to ensure completion of the task. In this context, several challenges arise such as deciding when and how to modify the current plan, integrating the sensory information into the current world models, and using prior plans to improve future plans.

Prior motion trees can also be beneficial in improving replanning. In particular, deviation from the planned motions during execution only invalidates certain parts of the motion tree. The rest can serve as a reliable guide for future expansions. This can reduce the running time needed for replanning as large parts of previous computations can be reused. This is akin to anytime search methods in AI, which often gain computational efficiency by locally repairing the plan when faced with new obstacles [1,41]. Sampling-based motion planners have also been used in replanning [4,27,37]. Building on this body of work, the expectation is that replanning can provide the necessary robustness to execute the planned motions in the physical world while responding to locally-sensed events.

8. Conclusion

The integrated task- and motion-planning problem requires integrative approaches that bring together techniques from robotics and AI. While progress has been made, numerous challenges lie ahead in order to ensure continued progress toward increasing the ability of robots to act on their own. Controller-synthesis approaches, coupling of discrete search and sampling-based motion planning, and replanning provide promising research directions. Building on this body of work, significant progress can be made by novel integrative approaches that address planning in a general setting taking into account tasks given in a discrete logic as well as high-dimensional continuous state spaces, nonlinear motion dynamics, general geometries and physics-based interactions. Progress along these directions promises to address fundamental issues and establish a unified paradigm for planning in a general discrete and continuous setting that bridges the gap between AI and robotics. We expect to obtain a better understanding of key components in discrete planning and motion planning, and particularly in their interplay. At the theoretical level, we expect formal guarantees on the algorithmic correctness and efficiency of the approaches, particularly focusing on probabilistic completeness and optimality.

Footnotes

Acknowledgements

The work of E. Plaku was supported by NSF IIS-1449505. The work of S. Karaman was supported by NSF CAREER CNS-1350685.

References

[1]

Aine and

Likhachev, Anytime truncated D^∗: Anytime replanning with truncation, in: Annual Symposium on Combinatorial Search, 2013, pp. 2–10.

[2]

Alterovitz and

Goldberg, Motion Planning in Medicine: Optimization and Simulation Algorithms for Image-Guided Procedures, Springer Tracts in Advanced Robotics, 2008.

[3]

Bacchus and

Kabanza, Planning for temporally extended goals, Annals of Mathematics and Artificial Intelligence 22(1,2) (1998), 5–27.

[4]

K.E.

Bekris and

L.E.

Kavraki, Greedy but safe replanning under kinodynamic constraints, in: IEEE International Conference on Robotics and Automation, 2007, pp. 704–710.

[5]

Belta,

Bicchi,

Egerstedt,

Frazzoli,

Klavins and

G.J.

Pappas, Symbolic planning and control of robot motion, IEEE Robotics and Automation Magazine 14(1) (2007), 61–71.

[6]

Bhatia,

L.E.

Kavraki and

M.Y.

Vardi, Sampling-based motion planning with temporal goals, in: IEEE International Conference on Robotics and Automation, 2010, pp. 2689–2696.

[7]

Bhatia,

Maly,

Kavraki and

Vardi, Motion planning with complex goals, IEEE Robotics Automation Magazine 18 (2011), 55–64.

[8]

M.S.

Branicky, Universal computation and other capabilities of continuous and hybrid systems, Theoretical Computer Science 138(1) (1995), 67–100.

[9]

Bruce and

Veloso, Real-time multi-robot motion planning with safe dynamics, Multi-Robot Systems: From Swarms to Intelligent Automata 3 (2005), 159–170.

10.

[10]

Cambon,

Alami and

Gravot, A hybrid approach to intricate motion, manipulation and task planning, International Journal of Robotics Research 1 (2009), 104–126.

11.

[11]

Canny, The Complexity of Robot Motion Planning, MIT Press, Cambridge, MA, 1988.

12.

[12]

Cashmore,

Fox,

Larkworthy,

Long and

Magazzeni, Planning inspection tasks for AUVs, in: OCEANS, 2013, pp. 1–8.

13.

[13]

Chen,

Ding,

Stefanescu and

Belta, A formal approach to the deployment of distributed robotic teams, IEEE Transactions on Robotics 28(1) (2012), 158–171.

14.

[14]

Chen,

Tŭmová,

Ulusoy and

Belta, Temporal logic robot control based on automata learning of environmental dynamics, International Journal of Robotics Research 32(5) (2013), 547–565.

15.

[15]

Cheng,

Pappas and

Kumar, Decidability of motion planning with differential constraints, in: IEEE International Conference on Robotics and Automation, 2007, pp. 1826–1831.

16.

[16]

Choi and

Amir, Combining planning and motion planning, in: IEEE International Conference on Robotics and Automation, 2009, pp. 238–244.

17.

[17]

Choset,

K.M.

Lynch,

Hutchinson,

Kantor,

Burgard,

L.E.

Kavraki and

Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, 2005.

18.

[18]

E.M.

Clarke,

Grumberg and

D.A.

Peled, Model Checking, MIT Press, 2000.

19.

[19]

J.A.

DeCastro and

Kress-Gazit, Synthesis of nonlinear continuous controllers for verifiably correct high-level, reactive behaviors, The International Journal of Robotics Research 34(3) (2015), 378–394.

20.

[20]

Doherty,

Kvarnström and

Heintz, A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems, Autonomous Agents and Multi-Agent Systems 19(3) (2009), 332–377.

21.

[21]

Donald,

Xavier,

Canny and

Reif, Kinodynamic motion planning, Journal of the ACM 40 (1993), 1048–1066.

22.

[22]

Edelkamp and

Plaku, Multi-goal motion planning with physics-based game engines, in: IEEE Conference on Computational Intelligence and Games, 2014, pp. 115–122.

23.

[23]

E.A.

Emerson and

J.Y.

Halpern, Decision procedures and expressiveness in the temporal logic of branching time, Journal of Computer and System Sciences 30(1) (1985), 1–24.

24.

[24]

E.A.

Emerson and

C.S.

Jutla, Tree automata, mu-calculus and determinacy, in: Proceedings of the Symposium on Foundations of Computer Science, 1991, pp. 168–377.

25.

[25]

Erdem,

Haspalamutgil,

Palaz,

Patoglu and

Uras, Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation, in: IEEE International Conference on Robotics and Automation, 2011, pp. 4575–4581.

26.

[26]

G.E.

Fainekos,

Girard,

Kress-Gazit and

G.J.

Pappas, Temporal logic motion planning for dynamic mobile robots, Automatica 45(2) (2009), 343–352.

27.

[27]

Ferguson and

Stentz, Anytime RRTs, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 5369–5375.

28.

[28]

Gochev,

Safonova and

Likhachev, Planning with adaptive dimensionality for mobile manipulation, in: IEEE International Conference on Robotics and Automation, 2012, pp. 2944–2951.

29.

[29]

Guo,

K.H.

Johansson and

D.V.

Dimarogonas, Revising motion planning under linear temporal logic specifications in partially known workspaces, in: IEEE International Conference on Robotics and Automation, 2013, pp. 5025–5032.

30.

[30]

Hart and

Sharir, Probabilistic propositional temporal logics, Information and Control 70(2) (1986), 97–155.

31.

[31]

Hsu,

Kindel,

J.C.

Latombe and

Rock, Randomized kinodynamic motion planning with moving obstacles, International Journal of Robotics Research 21(3) (2002), 233–255.

32.

[32]

Johnson and

Kress-Gazit, Probabilistic guarantees for high-level robot behavior in the presence of sensor error, Autonomous Robots 33(3) (2012), 309–321.

33.

[33]

Kaelbling and

Lozano-Pérez, Hierarchical task and motion planning in the now, in: IEEE International Conference on Robotics and Automation, 2011, pp. 1470–1477.

34.

[34]

Karaman and

Frazzoli, Sampling-based motion planning with deterministic μ-calculus specifications, in: IEEE Conference on Decision and Control, 2009, pp. 2222–2229.

35.

[35]

Karaman and

Frazzoli, Optimal kinodynamic motion planning using incremental sampling-based methods, in: IEEE Conference on Decision and Control, 2010, pp. 7681–7687.

36.

[36]

Karaman and

Frazzoli, Sampling-based algorithms for optimal motion planning with deterministic μ-calculus specifications, in: American Control Conference, 2012, pp. 735–742.

37.

[37]

Karaman,

M.R.

Walter,

Perez,

Frazzoli and

Teller, Anytime motion planning using the RRT^∗, in: IEEE International Conference on Robotics and Automation, 2011, pp. 1478–1483.

38.

[38]

L.E.

Kavraki,

Švestka,

J.C.

Latombe and

M.H.

Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation 12(4) (1996), 566–580.

39.

[39]

Keller, Numerical Methods for Two-Point Boundary-Value Problems, Dover, New York, NY, 1992.

40.

[40]

Kloetzer and

Belta, Temporal logic planning and control of robotic swarms by hierarchical abstractions, IEEE Transactions on Robotics 23(2) (2007), 320–331.

41.

[41]

Koenig and

Likhachev, Fast replanning for navigation in unknown terrain, IEEE Transactions on Robotics 21(3) (2005), 354–363.

42.

[42]

Koymans, Specifying real-time properties with metric temporal logic, Real-time Systems 2(4) (1990), 255–299.

43.

[43]

Kress-Gazit,

G.E.

Fainekos and

G.J.

Pappas, Temporal logic-based reactive mission and motion planning, IEEE Transactions on Robotics 25(6) (2009), 1370–1381.

44.

[44]

Kress-Gazit,

Wongpiromsarn and

Topcu, Correct, reactive robot control from abstraction and temporal logic specifications, IEEE Robotics & Automation Magazine 18(3) (2011), 65–74.

45.

[45]

Kuffner,

Kagami,

Nishiwaki,

Inaba and

Inoue, Dynamically-stable motion planning for humanoid robots, Autonomous Robots 12(1) (2002), 105–118.

46.

[46]

Kupferman and

Vardi, Model checking of safety properties, Formal Methods in System Design 19(3) (2001), 291–314.

47.

[47]

Kvarnström and

Doherty, TALplanner: A temporal logic based forward chaining planner, Annals of Mathematics and Artificial Intelligence 30(1–4) (2000), 119–169.

48.

[48]

Lagriffoul,

Dimitrov,

Saffiotti and

Karlsson, Constraint propagation on interval bounds for dealing with geometric backtracking, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2012, pp. 957–964.

49.

[49]

Lahijanian,

S.B.

Andersson and

Belta, Temporal logic motion planning and control with probabilistic satisfaction guarantees, IEEE Transactions on Robotics 28(2) (2012), 396–409.

50.

[50]

S.M.

LaValle, Planning Algorithms, Cambridge Univ. Press, Cambridge, MA, 2006.

51.

[51]

S.M.

LaValle and

J.J.

Kuffner, Randomized kinodynamic planning, International Journal of Robotics Research 20(5) (2001), 378–400.

52.

[52]

Leonard,

How,

Teller,

Berger,

Campbell,

Fiore,

Fletcher,

Frazzoli,

Huang,

Karaman,

Koch,

Kuwata,

Moore,

Olson,

Peters,

Teo,

Truax,

Walter,

Barrett,

Epstein,

Maheloni,

Moyer,

Jones,

Buckley,

Antone,

Galejs,

Krishnamurthy and

Williams, A perception driven autonomous urban vehicle, Journal of Field Robotics 25(10) (2008), 727–774.

53.

[53]

S.C.

Livingston,

R.M.

Murray and

J.W.

Burdick, Backtracking temporal logic synthesis for uncertain environments, in: IEEE International Conference on Robotics and Automation, 2012, pp. 5163–5170.

54.

[54]

Marthi,

Russell and

Wolfe, Angelic semantics for high-level actions, in: International Conference on Automated Planning and Scheduling, 2007, pp. 232–239.

55.

[55]

M.C.

Mayer,

Limongelli,

Orlandini and

Poggioni, Linear temporal logic as an executable semantics for planning languages, Journal of Logic, Language and Information 16(1) (2007), 63–89.

56.

[56]

McMahon and

Plaku, Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, pp. 3726–3733.

57.

[57]

McMahon and

Plaku, Robot motion planning with task specifications via regular languages, Robotica (2015), to appear. DOI: 10.1017/S0263574715000417.

58.

[58]

Molloy and

Shehu, Elucidating the ensemble of functionally-relevant transitions in protein systems with a robotics-inspired method, BMC Structural Biology 13 (2013), S8.

59.

[59]

R.M.

Murray and

S.S.

Sastry, Nonholonomic motion planning: Steering using sinusoids, IEEE Transactions on Automatic Control 38(5) (1993), 700–716.

60.

[60]

Plaku, Planning in discrete and continuous spaces: From LTL tasks to robot motions, in: Towards Autonomous Robotic Systems, LNCS, Vol. 7429, 2012, pp. 331–342.

61.

[61]

Plaku, Region-guided and sampling-based tree search for motion planning with dynamics, IEEE Transactions on Robotics 31 (2015), 723–735.

62.

[62]

Plaku and

G.D.

Hager, Sampling-based motion and symbolic action planning with geometric and differential constraints, in: IEEE International Conference on Robotics and Automation, 2010, pp. 5002–5008.

63.

[63]

Plaku,

Kavraki and

Vardi, Falsification of LTL safety properties in hybrid systems, International Journal on Software Tools and Technology Transfer 15(4) (2013), 305–320.

64.

[64]

Plaku,

L.E.

Kavraki and

M.Y.

Vardi, Falsification of LTL safety properties in hybrid systems, in: International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Vol. 5505, 2009, pp. 368–382.

65.

[65]

Plaku,

L.E.

Kavraki and

M.Y.

Vardi, Motion planning with dynamics by a synergistic combination of layers of planning, IEEE Transactions on Robotics 26(3) (2010), 469–482.

66.

[66]

Plaku and

McMahon, Motion planning and decision making for underwater vehicles operating in constrained environments in the littoral, in: Towards Autonomous Robotic Systems, LNCS, Vol. 8069, 2014, pp. 328–339.

67.

[67]

Pnueli, The temporal logic of programs, in: IEEE Symposium on Foundations of Computer Science, 1977, pp. 46–57.

68.

[68]

Rashidian,

Plaku and

Edelkamp, Motion planning with rigid-body dynamics for generalized traveling salesman tours, in: ACM SIGGRAPH Motion in Games, 2014, pp. 87–96.

69.

[69]

Reif, Complexity of the mover’s problem and generalizations, in: IEEE Symposium on Foundations of Computer Science, 1979, pp. 421–427.

70.

[70]

Russle and

Norvig, Artificial Intelligence: A Modern Approach, 2nd edn, Prentice-Hall, 2002.

71.

[71]

Sarid,

Xu and

Kress-Gazit, Guaranteeing high-level behaviors while exploring partially known maps, in: Robotics: Science and Systems, 2012, pp. 377–384.

72.

[72]

J.T.

Schwartz and

Sharir, A survey of motion planning and related geometric algorithms, Artificial Intelligence 37 (1988), 157–169.

73.

[73]

Sistla, Safety, liveness and fairness in temporal logic, Formal Aspects of Computing 6 (1994), 495–511.

74.

[74]

I.A.

Şucan and

L.E.

Kavraki, Mobile manipulation: Encoding motion planning options using task motion multigraphs, in: IEEE International Conference on Robotics and Automation, 2011, pp. 5492–5498.

75.

[75]

I.A.

Şucan and

L.E.

Kavraki, A sampling-based tree planner for systems with complex dynamics, IEEE Transactions on Robotics 28(1) (2012), 116–131.

76.

[76]

Tapia,

Thomas and

N.M.

Amato, A motion planning approach to studying molecular motions, Communications in Information and Systems 10(1) (2010), 53–68.

77.

[77]

Thomas, Automata on infinite objects, Handbook of Theoretical Computer Science 2 (1990), 133–192.

78.

[78]

Tilbury,

R.M.

Murray and

S.S.

Sastry, Trajectory generation for the N-trailer problem using Goursat normal form, IEEE Transactions on Automatic Control 40(5) (1995), 1–18.

79.

[79]

Ulusoy,

Marrazzo and

Belta, Receding horizon control in dynamic environments from temporal logic specifications, in: Robotics: Science and Systems, 2013.

80.

[80]

C.I.

Vasile and

Belta, Sampling-based temporal logic path planning, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 4817–4822.

81.

[81]

Wallar,

Plaku and

Sofge, Reactive motion planning for unmanned aerial surveillance of risk-sensitive areas, IEEE Transactions on Automated Science and Engineering 12 (2015), 969–980.

82.

[82]

Wolfe,

Marthi and

Russell, Combined task and motion planning for mobile manipulation, in: International Conference on Automated Planning and Scheduling, 2010, pp. 254–258.

83.

[83]

E.M.

Wolff,

Topcu and

R.M.

Murray, Optimal control with weighted average costs and temporal logic specifications, in: Robotics: Science and Systems, 2012.

84.

[84]

E.M.

Wolff,

Topcu and

R.M.

Murray, Automaton-guided controller synthesis for nonlinear systems with temporal logic, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 4332–4339.

85.

[85]

Wongpiromsarn,

Topcu and

R.M.

Murray, Receding horizon control for temporal logic specifications, in: ACM International Conference on Hybrid Systems: Computation and Control, 2010, pp. 101–110.