INTERACTIVE ROUTE-PLANNING AND MOBILE SENSING WITH A TEAM OF MULTIPLE ROBOTIC VEHICLES TO SATISFY LINEAR TEMPORAL LOGIC SPECIFICATIONS

Fang, Jie

Etd

INTERACTIVE ROUTE-PLANNING AND MOBILE SENSING WITH A TEAM OF MULTIPLE ROBOTIC VEHICLES TO SATISFY LINEAR TEMPORAL LOGIC SPECIFICATIONS

Público

Unmanned aerial and terrestrial vehicles (UXV) are envisioned to serve a broad variety of civilian and military applications including mountain search and rescue, cargo pickup/drop off, target tracking and source localization etc. To encode high level behavioral specifications on such vehicles, linear temporal logic (LTL) formula are widely used. To satisfy such specifications by a team of multiple robotic vehicles, two main technical problems are commonly considered. On the one hand, the planning problem addresses the collaboration among a team of vehicles and route planning to satisfy the given global mission. A practical example is the package delivery with least total traveled distance. The solution to this problem is based on the accurate knowledge of the environment. On the other hand, the sensing problem addresses the deployment of a set of sensors to measure subregions of unknown environment which is crucial for the planning problem. An example for this problem is search and rescue in an unknown region. A heterogeneous multi-vehicle team is considered where one set of vehicles called sensors are deployed to explore/map the environment, while the other set called actors are deployed to carry out intelligent collaborative tasks based on the map generated by the sensors. A traditional solution to the problem is to decouple the planning and sensing and solve each problem separately. Here, the sensors are required to rebuild the whole map as much as possible. However, this decoupled approach is wasteful in sensory resources (numbers of sensors and measurements). Instead, we propose a bootstrapping, iterative, and interactive route-planning and sensor placement technique that finds near-optimal routes for actors which are required to work collaboratively to satisfy a global task. The goal of this dissertation is to investigate the benefit of this coupled planning and sensing algorithm to the problem of route-planning in an unknown/uncertain environment. The contributions of this work are as follows. 1. We consider the problem of optimal planning under the assumption that accurate knowledge of the environment is available. The objective of this problem is to decompose the global specification into local specifications called tasks and compute the optimal route for each actor such that the total traveled distance is minimized. A decentralized network eliminates the possibility of a single centralized decision maker in the team. Instead, actors communicate and converge to a conflict-free task assignment. A novelty of this work is that, besides independent tasks which only require a single actor, the proposed planning algorithm also assigns collaborative tasks, i.e., tasks simultaneously assigned to multiple actors. This algorithm synchronizes the actors’ routes with minimum total waiting duration. To address vehicle’s kinematic constraints, the lifted graph technique is implemented to update the rewards in the proposed task assignment algorithm. 2. An interactive planning and sensing algorithm is developed for the aforesaid planning problem in an unknown environment. This problem now requires a set of sensors to explore the most “informative” regions iteratively and use the measurements to construct the unknown environment. The concept of information gain is used to quantify the potential benefits of taking new sensor measurements. At each iteration, optimal actors’ routes are computed to accomplish the intelligent task based on latest knowledge of environment. The task-driven information gain is evaluated and used to guide the sensors to reduce the uncertainty of current actors’ routes. The interactive between the planning and sensing will not stop until certain terminate condition is satisfied, i.e., enough confidence of obstacle-free routes for actors is achieve. This coupled planning and sensing strategy aims to doing the planning and sensing simultaneously and will converge with far fewer measurements than is required when planning and sensing are separate. Future work considers different extension of the proposed interactive planning and sensing framework including: sensor reconfiguration cost, taking measurement along the trajectory and more complex LTL global specification.

Creator