Multi-Robot Path Planning with Boolean Specification Tasks under Motion Uncertainties

This paper studies the path planning problem of multi-robot systems under motion uncertainties with high- level tasks that are expressed as Boolean specifications. The specification imposes logical constraints on robot trajectories and final states. First, a global Markov decision process model of the multi-robot system is constructed to provide its current state. In order to tackle the state explosion problem, at each stage, we construct a local Markov decision process for every individual agent in sequence to compute the local optimal movement strategy and update the global Markov decision process accordingly (i.e., compute locally and update globally). Next, we propose a heuristic reward function design method that provides different rewards for visiting different task points by introducing the estimated distance to complete the global task. Finally, a series of numerical experiments are conducted to demonstrate the computational efficiency and scalability of our developed approach. Discrete event systems, Markov decision process, Multi- robot system, High-level task, Reinforcement learning. I. INTROUDCTION A. Motivation Multi-robot systems (MRS) are widely used in many appli- cations, such as search and rescue, autonomous warehouses, and manufacturing systems [1]. One of the central challenges for the controlling and coordination of MRS is the path planning that typically intends to complete some tasks by minimizing costs such as time, distance, or energy. The goal is to determine an optimal route for each robot to complete assigned tasks sequentially and achieve the global task ultimately [2]. Traditionally, most existing path planning algorithms focus on collision avoidance, target access, and path smoothing [3]–[5]. With the increasing complexity of tasks, considerable attention has been paid to multi-robot path planning with high-level tasks in recent years [6]. Particularly, linear tem- poral logic (LTL) and Boolean specifications are widely used as the formal language to express the high-level task requirements [7], [8], e.g., “finish job A in the regions a or b, avoid reaching some unsafe regions, and finally staying in the region c”. In addition, MRS operating in complex environments are often subject to a variety of uncertainties (e.g., potential sensing noise or actuation failures). In [9], [10], the path planning problem under motion uncertainties is investigated and a control strategy that maximizes the probability of LTL task satisfaction is proposed. For the path planning of MRS with Boolean specifications, it aims to find the optimal paths with minimal cost such that the Boolean specifications are satisfied. In particular, Petri net models are employed to model the MRS and integer linear programming methods are proposed [11]. In this paper, we study the path planning problem of multi-robot systems with Boolean specification tasks under motion uncertainties. We model the mobility of an MRS as an Markov decision process (MDP) and employ a rein- forcement learning technique to determine a control strategy that satisfies the Boolean specifications. An iterative rein- forcement learning strategy that eliminates the dependence of state computations on the number of robots is developed to improve the computational efficiency. Moreover, in order to improve the solution quality, a heuristic reward function is designed. The scalability and computational efficiency of the proposed method is demonstrated by numerical experiments. B. Related works In [12], [13], the authors consider the optimal path plan- ning problem with linear temporal logic constraints. In [14], [15], path planning problem with Boolean specifications are discussed by using Petri net models. A simulated anneal- ing based algorithm is presented in [16] to find a near- optimal solution with relative low computational cost. More recently, the security-preserving multi-robot path planning with Boolean specifications is discussed in [17], which aims to plan an optimal path for each robot such that the Boolean tasks are finished, while some key information of the systems are hidden for an external intruder. In summary, the existing optimal approaches [15] have high computational cost since the numbers of constraints and variables of the integer linear programming problem increase significantly as the task quantity and map size increase. The heuristic approach developed in [16] has relative low computational cost, but the accuracy decreases as the map size and task quantity increase. Moreover, theses approaches are limited by the fact that the modeling approach cannot be applied to MRSs with motion uncertainties. Thus, finding an efficient method for large-scaled MRSs with high-level tasks and under motion uncertainties is still a challenging problem. II. PRELIMINARIES An MDP is a tuple P = (S, s0, Sf, A, P), where S is a finite set of states, s0 ∈S is an initial state, Sf ⊆S is a finite set of final states, A is a finite set of actions, and P : S × A × S →[0, 1] is the transition probability function. It captures the motion uncertainties of MRSs. Let A : S →2A denote the set of actions enabled at state s ∈S (i.e., A(s) = {a ∈A|∃s′∈S ∈P(s, a, s′) > 0}). The reward function R : S × A × S →R represents the task objective. 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) October 14-18, 2024. Abu Dhabi, UAE 979-8-3503-7769-9/24/$31.00 ©2024 IEEE 3433