Markov decision processes (MDPs) [1]havebeenwidely applied in robotics motion planning, assuming the environment was fully observable. However, in some realworld applications, the agent may not have access to complete or reliable information about the state of the environment. Therefore, partially observable Markov decision processes (POMDPs) [2] need to be adopted. POMDPs are particularly useful when sensors or perception systems are prone to errors or uncertainty. By incorporating the observation probability model into the POMDP framework, it is possible to quantify the effects of perception errors on the agent's decision-making performance. On the other hand, there has been increasing interest in considering complex tasks in robotics motion planning other than simple go-to-goal missions, especially dealing with uncertain and dynamic environments.
Reinforcement learning (RL) methods [3]h a v ebe e n employed to solve robotics motion planning in partially observable environments. Model-based RL approaches assume that the agent knows the probabilistic characteristics of transition and observation. Therefore, a belief s t a t ec a nb eu p d a t e dv i at h eB a y e s i a nt h e o r y [ 2,4]t o denote a probability distribution over all possible states. Consequently, a POMDP problem with the original state space becomes an MDP problem with a corresponding CONTACT Junchao Li junchao-li@uiowa.edu belief space. In this case, the policy is a function of belief states for action selection. One commonly-used approach is the value iteration algorithm to solve POMDP problems as a form of dynamic programing.
Early works aim to determine exact value functions in the belief space for small POMDP problems, e.g. enumeration algorithms [2,5].Basedo nSo ndik'so ne-pas s algorithm [5], Cheng [6] proposed a simple linear support algorithm, which started at a random belief state and generated a vector for its value function. Also, the witness algorithm [7] simplified the POMDP problem by considering one action and one observation at a time. Furthermore, Zhang and Liu [8] integrated the enumeration a n dwi tn es salg o ri thm sa n dp r o posedaso-calledin cr em e n t a lp r u n i n ga l g o r i t h m .H o w e v e r ,i nl a r g eP O M D P problems with complex dimensions, finding the optimal policy precisely in the belief space can be computationally intensive. Therefore, point-based value iteration (PBVI) algorithms [9] were proposed for infinite-horizon POMDP problems by approximating optimally reachable belief spaces to address this issue. This approach updated value functions locally for a finite subset of the belief space. One of the point-based solvers [10], SAR-SOP (Successive Approximations of the Reachable Space under Optimal Policies) [11,12], could handle POMDP problems with large state spaces.
Another approach is employing Q-learning to learn the optimal policy on the belief state space of a POMDP. It shall be noted that Q-learning [13]i sam o d e l -f r e e approach that allows the agent to learn to act optimally in MDP problems. However, since the belief states need to be calculated from the transition and observation probabilities, this approach is still model-based. On the other hand, because the belief state spaces are usually continuous in POMDP problems, classical Q-learning algorithms such as tabular Q-learning [13]a r en ol o n g e r applicable. Consequently, deep Q-network [14]( D Q N ) is employed in this paper to map POMDP belief states to state-action values. Some other works [15,16]h a v e utilized DQN to achieve the optimal policy regarding a sequence of observations. However, they were model-free approaches to POMDPs, which is not our focus in this study.
Manyworkshavebeendonetoconsidercomplextasks o t h e rt h a ns i m p l eg o -t o -g o a lm i s s i o n si nM D Pp r o blems by adopting formal languages [17], such as linear temporal logic (LTL), to formulate user-defined highlevel specifications. Then, the LTL formula is commonly c o n v e r t e dt oa nω-automaton over infinite words with a Büchi or a Rabin acceptance condition [18]. Consequently, robotics motion planning problems can be solved via control synthesis for a product of MDP and automaton with model checking [17]. It has been shown that a limit-deterministic Büchi automaton (LDBA) has more advantages than a deterministic Rabin automaton (DRA). Hahn et al. [19]implementedLDBAandDRAin model-free RL with mild restrictions, respectively. They c o n c l u d e dt h a tL D B Aw a sm o r es u i t a b l ef o rb o t hq u a litative and quantitative analysis of MDPs under all ωregular objectives. In another work, Hasanbeig et al. [20] stated that converting the LTL specification into an LDBA might result in a smaller automaton state space than a DRA. However, LDBA suffers the sparsity of reward and may highly slow the RL's convergence [21].
Similarly, model checking provides the formal approach to verifying complex task objectives when solving POMDP problems with certain temporal logic constraints. Chatterjee et al. [22] studied the undecidability of the qualitative model checking in a POMDP problem with the infinite horizon. They proposed a finitememory approach for the verification and synthesis of POMDPs with LTL constraints. It relied on exploring the entire belief space and was most suitable to the problems with small state spaces. In other works [23,24], LTL specifications were converted to a DRA, and then a p r od ucto fPO MD Pa ndD RAwasco n structed.S pecifically, Sharan et al. [23] employed finite state controllers to limit the policy search via the value iteration methods. On the other hand, Bouton et al. [24]u t i l i z e dt h e approximate POMDP solver, SARSOP [11], to search for an optimal policy on the finite belief state space of the product POMDP. Finally, it shall be noted that Wang et al. [25]e m p l o y e dL D B Aa n dc o n v e r t e daP O M D Pt o the corresponding belief MDP before building a product of belief MDP and LDBA. However, simulation examples are expected to demonstrate the feasibility of the proposed method.
T h efi r s tc o n t r i b u t i o no ft h i sp a p e ri sf o r m u l a ting a complex task via LTL, converting it to a limitdeterministic generalized Büchi automaton (LDGBA), and constructing a product of POMDP with LDGBA. Although the strategy of representing complex tasks by LTL and then automaton is not new, most works focused on MDP instead of POMDP problems. In addition, this studyemploysLDGBAforthefirsttimeinPOMDPprobl e m s ,s i n c ei tc a nl e a dt oas m a l l e rp r o d u c ts t a t es p a c e [19]t h a nD R A [ 23,24] and can address the sparsity of rewards caused by LDBA [21]. The second contribution is to reformulate the original problem of finding a policy that satisfies LTL specifications in a POMDP as finding an optimal policy to maximize the collected reward on the corresponding product of POMDP and LDGBA. Therefore, model-based RL approaches can be employed. In addition to a modified PBVI solver, we propose convolutional neural network (CNN)-enhanced deep Q networks to approximate the state-action value functions at a given belief product state. The last contribution is redesigning the reward function and introducing a frontier set in LDGBA to record non-visited accepting sets so that the proposed methods can efficiently handle surveillance tasks.
Model-predictive Control (MPC), Rapidly-exploring Random Trees (RRT), and Probabilistic Roadmaps (PRM) are classical motion and trajectory planning algorithms. Recently, some works like [26]u t i l i z e dR R Tt o map a belief state to possible paths that connect the start state to a goal state for pathfinding. Therefore, RRT (and PRM) can address the observation uncertainty. Although this approach could be extended to solve the product POMDP problems proposed in this study to handle complex tasks, no such works were reported based on the authors' best knowledge. On the other hand, the belief state space in POMDP is infinite. When model-based motion planning algorithms, such as RRT and PRM, search the paths on belief state spaces, they can be computationally expensive. On the other hand, an online M P Cs o l v e rw i l lb em o r ea p p r o p r i a t ew h e nt h eo b s e rvation uncertainty is considered. However, the optimal control policy needs to be updated frequently based on the new measurements. This method can be computat i o n a l l yi n t e n s i v e ,t o o .C o m p a r e dw i t hM P C ,R R T ,a n d PRM, one of our approaches utilizes the SARSOP solver, which explores a belief tree on the optimally reachable belief space to improve computational efficiency.
The organization of this paper is described as follows. Section 2 reviews POMDP problems and stateof-art solutions, including PBVI/SARSOP and Deep Qlearning. Section 3 introduces LTL, LDGBA, and product POMDP. Then, we redefine the POMDP problem with LTL specifications and depict reward design and tracking frontier function. Section 4 proposes the approaches to product POMDP problems and provides detailed algorithms. Finally, two simulations and results are included in Section 5,followedbytheconclusionandfutureworks.
The POMDP is a mathematical framework to model a problem in which the environment is not fully observable.
Considering the action and observation uncertainties and the labels of states, a POMDP can be denoted by a tuple P = (S, A, T, s 0 , R, O, , , L),where:
• S ={s 1 , ..., s n } is a finite set of states.
• A ={a 1 , ..., a m } is a finite set of actions. Specifically, A(s) represents the set of available actions that can be takenbytheagentatstates. At every time step during the learning, the agent is at state s ∈ S and selects an action a ∈ A(s),whichtransits the agent to the next state s ′ ∈ S. Since we consider the motion uncertainty, the probability of such a transition is T(s, a, s ′ ). After the agent reaches the next state (s ′ ), it then can perceive an observation o ∈ O(s ′ ) with the probability of (s ′ , a, o) to gather the information of this state. On the other hand, after the transition, the agent also collects a reward given by the function R(s ′ ).T h eg o a lo f the agent choosing a sequence of actions is to maximize its expected return, i.e. the accumulated rewards, starting from state s at the current time t = 0as
where s t denotes the agent's state at time t. γ ∈ [0, 1] is the discount factor to balance the importance between immediate and future rewards.
In model-based approaches to solving POMDPs, it is common to find an optimal policy in the belief state space instead of the state space defined in the POMDP, i.e. S. A belief state, b ∈ B where B = Dist(S) is the belief state space, represents the probability distribution over all the possible states s ∈ S. Specifically, b t (s) denotes the probability of the agent being at state s at time step t.T h e initial belief state, b 0 , depends on the agent's knowledge of its initial state s 0 . If the agent is aware of its initial state, b 0 (s 0 ) = 1a n db 0 (s) = 0f o rs = s 0 .O t h e r w i s e ,b 0 is a uniform probability distribution. If the agent's current belief state is b t (s),a f t e rt a k i n ga c t i o na t and obtaining observation o t+1 ,thenewbeliefstateb t+1 (s) can be updated by Icarte et al. [27]:
Consequently, the belief state holds the experience of a complete history [27], and a policy can map the belief state b t ∈ B to the action a t ∈ A.T h e n ,t h ee x p e c t e d return in (1) under a policy ξ can be rewritten as
where R(b t ) = s∈S b t (s)R(s) i st h er e w a r dt h a tt h e agent can collect depending on the current belief state. Finally, the POMDP problem becomes finding the optimal policies in a corresponding MDP with the belief state space to maximize the expected return, i.e. ξ * = argmax ξ U ξ (b).
Since the belief state space is infinite and most belief points are very unlikely to be reached, the PBVI algorithms [9] prune away belief points by selecting the best action on every trajectory to generate the next belief point. Specifically, the PBVI algorithms introduce a set of alpha vectors V ={α 0 , α 1 , ..., α m } to approximate the value functions as [9]:
It shall be noted that each alpha vector is an |S|dimensional hyper-plane and constrained by the boundary of the belief state space, i.e. B.Anumberofalphavectors form the approximated value function V(b),which is a piece-wise linear and convex function [9]. Only one alpha vector on each belief point is maintained during the valuebackup,whichisdefinedas[9]
In addition, the PBVI algorithms use a precision parameter, the difference between an upper bound and a lower bound of the value function, to guarantee policy convergence [9]. Another reported approach [14]toPOMDPproblems is utilizing deep neural networks (DNNs) to approximate the state-action values. Mnih et al. [ 16]fi r s t l yi n t r oduced Deep Q-learning (DQN) to solve MDP problems. Their DQN architecture consists of two DNNs (called Qnetworks), an evaluation Q-network Q e (s, a; θ e ) and a target Q-network Q t (s, a; θ t ) to keep the learning more stable and effective. During the learning process, ǫ-greedy exploration strategy [3] and experience replay memory [28] are used for the action selection and the collection of the training samples, respectively. M. Egorov [14] leveraged DQN to solve POMDP problems by mapping POMDP beliefs to the state-action values. Instead of the model-free algorithm commonly used in MDP problems, his approach updates the belief state as the input feature to Q networks. Consequently, this approach is still model-based, and the derived policy is a function of belief states.
Linear temporal logic is a high-level language to describe user-specified tasks. Basically, an LTL specification can be formulated inductively via the combination of Boolean operators, such as negation (¬) and conjunction (∧), and two temporal operators, including next ( )a n du n t i l (U ). The formula φ c a nb er e a da s' φ is true at the next state' while φ 1 Uφ 2 as 'φ 2 is true at some future states and φ 1 is true at each state until then.' Consequently, the syntax of an LTL formula is defined inductively as [29] φ
where a ∈ is an atomic proposition. Other common Boolean and temporal operators are derived as follows:
or :
Let |= denote the satisfaction relationship. The semantics of an LTL formula is interpreted over words, which is an infinite sequence w = w 0 w 1 ... with w i ∈ 2 for all i ≥ 0, and defined as:
GivenanLTLthatspecifiesacomplextask,itssatisfaction can be evaluated by an LDGBA [30].
An LDGBA is a tuple A = (Q, , δ, q 0 , F),where Q is a finite set of states, = 2 i safi n i t ea l p h a b e t ,δ :
• The state transitions in Q D are total and restricted within it, i.e. |δ(q, α)|=1andδ(q, α) ⊆ Q D for every state q ∈ Q D and α ∈ , • The ǫ-transition is not allowed in the deterministic set, i.e. for any q ∈ Q D , δ(q, ǫ) =∅, • The ǫ-transitions are only defined for state transitions from Q N to Q D ,w h i c hd on o tc o n s u m et h ei n p u t alphabet, and • The accepting sets are only in the deterministic set, i.e.
A run of an LDGBA, subject to an input word w = w 0 w 1 ...,canberepresentedasq = q 0 q 1 ...,andinf(q) represents the infinite portion of q. If there exists inf(q) ∩ F i =∅, ∀i ∈{1, ...f },w es a yt h a tq satisfies the LDGBA acceptance condition. In other words, the LDGBA accepts the word w.W er e c o m m e n dO w l [ 18] to readers for more details about automaton generation.
Consequently, this study aims to solve the POMDP problems with LTL specifications defined below.
Problem 3.1: Given a POMDP with its belief state space B t h a tc a nb ed e r i v e dv i a( 2 )a n dat a s ke x p r e s s e da s a nL T Lf o r m u l a .T h eo b j e c t i v ei st ofi n dap o l i cyξ * (b) that can complete the task by satisfying the acceptance condition of the LTL-induced LDGBA.
Therefore, we introduce a framework for solving a POMDP problem by exploiting the fact that an LTL formula can be transformed into an LDGBA representing the task variables and safety constraints of the POMDP.
The problem of satisfying a given LTL objective φ in a POMDP P canbereducedtotheproblemofsatisfyinga repeated reachability (Büchi) objective φ B in the product POMDP.
The product POM DP P × = P × A of a POMDP P = (S, A, T, s 0 , R, O, , , L) and an LDGBA A = (Q, , δ, q 0 , F) is defined as
where:
• S × = S × Q is the finite set of labeled states, i.e. s × = s, q ∈S × where s ∈ S and q ∈ Q.
T(s, a, s ′ ) q ′ = δ q, l , l ∈ L(s ′ ) and a ∈ A 1 a × ∈ {ǫ} and q ′ ∈ δ(q, ǫ) and s ′ = s, 0o t h e r w i s e .
(7) • s × 0 = s 0 , q 0 ∈S × is the initial state, where s 0 ∈ S and
where s ′ ∈ S and a × ∈ A. On the other hand, if a × ∈ {ǫ}, the agent stays at the same s, i.e. s ′ = s,a n dt h e belief state won't be updated.
A random path (s 0 , q 0 )(s 1 , q 1 )...of the product POMDP corresponds uniquely to the combination of a path s 0 , s 1 ... of the POMDP and a path q 0 , q 1 ... of the LDGBA. On the other hand, the belief product state denoted as b × ∈ B × ,w h e r eB × = Dist(S × ),r e p r e s e n t s the probability distribution over all the possible product POMDP states. Similarly, the new belief product state can be updated by the formula derived from (2):
It is noted that the product POMDP shares the same observation space of POMDP. The initial belief state is
The expected return under a policy ξ × can be written as below, similar to (1).
where the reward function remains as
The constructed product POMDP P × can be interpreted as the POMDP P with the augmented state space to account for the temporal logic specifications represented by LDGBA A. All the feasible paths on P × share the intersections between all the accessible paths over P and all words accepted by A. Specifically, a path σ ξ × = (s 0 , q 0 )(s 1 , q 1 )..., generated by a random policy ξ × on the product POMDP
The belief state b t (s) represents the probability distribution of the agent in POMDP state s ∈ S given the history up to time t. b t+1 is then updated from the previous belief state b t , the executed action a t ,a n dt h er e s u l t i n g observation o t+1 by (2) for all s ′ ∈ S.Basedonthat,b t ∈ B also has the Markovian property. Therefore, finding the optimalpolicyasafunctionofbeliefstatesinaPOMDP problem is equivalent to solving an MDP problem with a continuous belief state space. Moreover, according to previous studies on MDP problems with LTL specifications [29,[31][32][33], the optimal policy ξ × * (b × ) on the product POMDP P × is also the optimal policy ξ * (b) on the POMDP P satisfying LTL specifications. Consequently, Problem 3.1 can be reformulated as follows.
Problem 3.2: Given a product POMDP defined in Section 3.3 as P × = P × A of a POMDP P and an LDGBA A generated from LTL specifications φ,thecorresponding belief state space can be derived via (10). The objective is to find a policy ξ × * (b × ) so that the expected return is maximized.
When directly applying the constructed LDGBA in solving a product POMDP problem defined in Problem 3.2, it may fail to find the deterministic policy that satisfies the LTL specifications [20,21].Forexample,tocompletethe task that an agent shall visit states labeled with 'a' and 'b' once at a time for infinitely many times, the LTL formula can be written as
Rabinizer 4 [18] is used to convert the LTL formula into an LDGBA. We augment the accepting states in order to separate 'a' and 'b' transitions. In addition, we simplify the automaton by only keeping single labeled transitions, which is sufficient to explain this example. The full automaton after states augmentation is shown in Figure 1, and the set of accepting sets is F ={{q 0 }, {q 1 }}. Theoretically, this automaton may accept a word of (b * a * ) ω where * ω * ω matche the preceding character(s) finite times and infinite times. However, since the typical reward design in (8) depends on the product states corresponding to the LDGBA accepting states, the agent may tend to keep visiting one of the labeled states infinitely many times to collect more rewards. Consequently, the specified task cannot be accomplished.
To address the above issue for surveillance tasks, we redesign the reward function as below by adding a constraint to (8) such that the agent can visit the accepting sets repeatedly.
and q ′ = q 0o t h e r w i s e .
(15) where q = q ′ prevents the repeated transitions, which lead to the same automaton accepting state by removing the rewards on the associated labeled POMDP states. After applying this constraint to the reward function, the derived optimal policy satisfies the desired task specification. We provide the simulation of this example with the model-based SARSOP solver on the POMDP environment in Section 5.1.
In addition, we introduce another approach that implements a frontier set T to keep track of non-visited accepting sets based on the previous work by M. Cai [32]. In most cases, T is initialized as F.I fas t a t eo fo n e or more accepting sets has been visited, those sets will be removed from the frontier set T . Mathematically, the tracking-frontier function T F is defined and updated as [32]:
Once the frontier set T be c o m e se m p t y ,i tw i l lber e s e t as F if the specification requires the infinite visits of all accepting sets. Consequently, the accepted words in Figure 1 can be (ab) * , (ba) * .Itshallbenotedthatthevisited LDGBA accepting sets are removed from the frontier set T , and at the same time, the rewards on the associated labeled states are disabled. Therefore, it prevents the repeated visiting of the same automaton state. Furthermore, the original definition of reward in ( 8) is redefined as
The above tracking-frontier function T F can be revised according to different task specifications. For example, additional constraints can be added to T F that only removes F i in order, forcing the agent to visit the labeled statesinaspecificsequence.Thisapproachisnoteasily directly implemented in the SARSOP solver but in DQN. Therefore, we only applied the frontier set to DQN in this study.
Ap r o d u c tP O M D Pc a nb ev i e w e da saP O M D Pb u t simultaneously satisfies the task constraints provided by the LTL-induced automaton. The transitions in the product POMDP are restricted and prevented by the automaton transitions. Therefore, the proposed product POMDP problem can be solved by the methods that have been successfully applied to POMDP problems. It shall be notedthatthestatespaceisextendedduetotheproduct of POMDP and LDGBA.
One of our approaches uses SARSOP [11]toapproximate the optimal value functions on product POMDP. To achieve this, SARSOP introduces a lower-bound target level L and an upper-bound target level U.At a r g e t gap size ε between L and U at b × 0 is initialized. When the sampling process follows the belief tree T R , the target levels, i.e. L and U,areupdatedasL t and U t where t is the depth of the node in the tree. The sampling path will be terminated once the gap size between L t and U t for all the leaves in T R reaches γ -t ε where γ is the discount factor [11].
To update the lower and upper-bound target levels (L t and U t )f r o mL t-1 and U t-1 ,t h ef o l l o w i n ge q u a t i o ni s utilized first to calculate the lower bound of the optimal Qvalue [11]onceanactionisselected.
where V, obtained by the fixed-action policy [34], is the lowerboundoftheoptimalvaluefunctionV * at b × ′ .The upper bound of the optimal Q value, Q,isobtainedsimilar to (18), and its upper bound V can be acquired by sawtooth approximation [34]. In addition, P(o|b × , a × ) is defined as [10]
Then, Q is used to find an intermediate lower-bound target level L ′ as the maximum value between L t-1 and Q. Similarly, an intermediate upper-bound target level U ′ isthemaxim umval uebetweenU t-1 and Q + γ -t ε. Finally, the target level L t for the next belief node b × ′ can be calculated, and it is needed for Q to achieve its target level L ′ .Similarly,U t is acquired by computing Q with U ′ [11].
Next, the standard backup process for α-vectors in Ŵ is performed with the value function approximation. The last step is the pruning process [11]i nw h i c ht h e sub-optimal belief nodes and α-vectors are pruned away. Finally, a more strict requirement of dominance check, called δ-dominance [11], is used to eliminate the suboptimal α-vectors. Algorithm 1 describes the implementation of this approach to determine a set of α vectors, Ŵ, whichisusedtoapproximatetheoptimalvaluefunctions of the product POMDP P × . Initialize the set of α vectors Ŵ, upper and lower bounds V and V of V * . V is set as the prediction of (5).
if
Prune away α 2 . end if end while Return Ŵ.
Another approach for solving product POMDP problems is deep Q-learning (DQN). This approach employs neural networks to map a belief product state to the corresponding state-action values, i.e. Q values, for the agent choosing the best action. Compared to the SAR-SOPsolver,DQNrequiresmorecomputationtimesince i tu s e sM o n t eC a r l os i m u l a t i o n .H o w e v e r ,i ti se a sier to implement the tracking-frontier function (16) T F (q, T ) inDQNthanintheSARSOPsolver .Asstated in Section 3.4, the LTL-induced LDGBA with the frontier set T canhandlemorecomplextaskswithoutadding extra computational complexity [32] to the original derived automaton. In this study, the tracking-frontier function that can record the visited or non-visited accepting sets in each round is implemented in DQN.
Figure 2 illustrates the Q networks' architecture, similar to a convolutional neural network (CNN). The Q networks consist of 'Convolutional' layers, 'Flatten' layers, 'Fully-Connected' layers with linear activation functions at the end to generate the outputs as the approximated Q values of individual actions corresponding to the input belief state. In this study, a considered POMDP has a twodimensional state space, and the LTL-induced LDGBA state space provides an additional dimension. Consequently, a belief state of the product POMDP is a threedimensional array as the input to Q networks. Compared with artificial neural networks (ANNs), CNNs can automatically detect important features without any human supervision. In our Q network architecture, there are no 'maxpooling' layers because every belief point is important, and any missing information may cause a dramatic accuracy drop in the trained network.
In DQN, two identical Q networks are initialized: the evaluation network (Q e )andthetargetnetwork(Q t ). The target network is utilized for the next action selection and Q value prediction. The evaluation network is trained every M steps by a number (i.e. batch size) of experiences b × i , a × i , r i , b × i+1 . After every K steps,thetargetnetwork is updated by copying the weight coefficients of the evaluation networks. Using two neural networks can prevent the bootstrapping of the DQN with a single neural network. In the so-called model replay, once the random sample set U(D) is collected, the new Q value is computed bytheequationas [16] 16) and (17).
Calculate the rewards r i by (13).
Randomly select the samples U(D) with length as M.
while (20).
Train Q e by the set of Q new .
Pass the weights of Q e to Q t .
Training end and save the evaluation network Q e
We evaluate our methodologies on two simulations with the discrete POMDP state spaces. We first carry out the simulations over a partially observable grid world. The product POMDP models are generated in Python 3.9 with Rabinizer 4 [35] and then solved by Julia SARSOP solver [11] and DQN (via Python), respectively. Furthermore, the grid-world simulation is scaled to different sizes of state and observation spaces to evaluate the scalability of the value iteration approach via SARSOP. Then, we apply the value iteration approach to a more realistic office scenario with TurtleBot2 via Pybullet 3.0 [36]. All simulations are completed on a desktop with a 3.20 GHz eight-core CPU and 32GB of RAM. Some source codes and supplementary materials are provided. 1
Here considers a grid-world workspace with a size of 10 × 10, as shown in Figure 3.T h el a b e l e dc e l l sa r e marked with different colors representing different areas of interest. For example, 'a' and 'b' are labeled on the goal states that an agent may visit multiple times according to t h es p e c i fi e dt a s k .' c 'i st h el a b e lo nt h et r a p p i n gs t a t e s where an agent cannot escape once entered. 'B' represents theblockstates,i.e.obstacles,thattheagentisnotableto pass.
Theagent,e.g.themobilerobot,inthegridworldcan take four actions at each state: up, left, down,a n dright. After taking each action, the agent can move towards the desired state with a probability of 0.9 and move sideways with an equally weighted probability distribution o t h e rw i s e .I ft h en e x ts t a t ei so u t s i d et h eg r i dw o r l do r the obstacle, the agent will stay at the current state. In addition, the agent can observe the current state with a probability of 0.9 and adjacent states with a total probability of 0.1 uniformly distributed. The obstacles (i.e. states labeled with 'B') cannot be observed. The discount factor γ is all set as 0.95.
In the grid world, the agent is required to visit states labeled 'a' and 'b' once at a time for infinitely many times, as stated in Section 3.4. The LTL formula is written as (14), and the induced LDGBA is shown in Figure 1. The POMDP environment has 100 states, and its corresponding product POMDP consists of 300 states. The set of accepting sets of the derived LDGBA is F = {{q 0 }, {q 1 }}, and the standard rewards in (8) are assigned with the labeled states transitions to q 0 and q 1 .
We first use the SARSOP solver to obtain the optimal value functions of belief states and then derive the optimal policy. Figure 4(a) illustrates an induced path from as t a r ts t a t e ,m a r k e da sal a r g ep u r p l es o l i dc i r c l e .T h e agent moves to 'a' straightly, and the LDGBA state transits from q 0 to q 1 .InFigure4(b), it can be seen that the agent keepsvisitingstates'a'sinceq 1 has a recurrent transition by consuming the symbol 'a' in the LDGBA (Figure 1). Theagentmustvisit'a'onq 1 infinite times to maximize the collected reward. Therefore, the specified task cannot be accomplished.
To address the above issue discussed in Section 3.4, we apply the redesigned reward in (15) by only assigning rewards to the transitions that lead to the accepting states from a different automaton state. Then, after solving the problem again via SARSOP and obtaining the optimal policy, we generate another path, shown in Figure 5. It illustrates a successful run in which the agent visits states'a'then'b'andkeepsvisitingthemalternativelyfor infinite times.
Starting from the initial state, shown in Figure 5(a), the agent moves left straightly to reach the area labeled 'a', which leads the automaton transition from q 0 to q 1 . A bend in the route indicates the agent pauses there f o ra ne x t r at i m ed u et ot h ea c t i o nu n c e r t a i n t y .F i g u r e 5(b) shows the induced path on the POMDP at automaton state q 1 .T h ea g e n tl e a v e sa r e a' a 'a n dm o v e sr i g h t then up to reach the green area labeled as 'b'. Up to this point, the agent successfully completes one round, and the automaton state transits back to q 0 .InFigure5(c), the agent moves from 'b' to 'a' again to start another round.
We also tested the algorithm on the same grid-world problem with various workspace sizes to show the computational complexity. The simulation results are listed in Table 1. It shows the times in seconds used to learn optimal policies.
A similar scalability study was performed in [24], in which the LTL formula was converted to DRA. They investigated grid worlds with state spaces up to 10 by 10, and the simulation time for the size of 10 by 10 is comparable to the one in Table 1.
We tested another model-based approach using DQN with the tracking-frontier function to the same grid-world problem. The input shape for Q networks is (10 × 10 × 3). The dimensions correspond to the size of a belief product state, including the row and column numbers of the workspace in the POMDP and the number of automaton states of LDGBA, respectively.
T h eQn e tw o r ka r c h i t ect u r ei ss h o wni nF i g u r e2.I n this study, two convolutional layers extract the features from the input belief state. One layer uses eight (4 × 4) filters with stride (2, 2), and the other uses 16 (2 × 2) filters with stride (1, 1). The outputs are converted to a 1D array by a 'Flatten' layer. Then, two fully-connected layers with 128 and 64 neurons are used to predict the corre-spondingQvalues.TheRectifiedLinearUnit(i.e.ReLU) is utilized as the activation function in the Q networks. The learning process includes 500 steps per episode for 8,000 episodes. Two Q networks, the evaluation network Q e and the target network Q t ,a r er a n d o m l yi n i t i a l i z e d . The training batch size for the evaluation network is 3 2 ,a n dt h et a r g e tn e t w o r ki su p d a t e db yc o p y i n gt h e weight coefficients of Q e every 50 steps. Since DQN uses Monte Carlo simulation, it is computationally intensive. The computing time for this simulation is 49450.4041 seconds. The frontier set T is initialized as {{q 0 }, {q 1 }}.T h e rewards are assigned on the states labeled either 'a' or 'b', resulting in the automaton transitions to q 0 or q 1 ,respectively. Once the automaton state in an accepting set of T is visited, this accepting set will be removed from T , and the corresponding reward is disabled too, as indic a t e di n( 1 6 ) .A f t e rl e a r n i n g ,t h ee v a l u a t i o nQn e t w o r k canpredicttheoptimalQvaluesforagivenbeliefstate. Consequently, the optimal policy can be derived. Figure 6 shows an induced path resulting in a successful run in that the agent recurrently visited states 'a' and 'b' once at a time for infinitely times. It shall be noted that the generated path differs from the one in Figure 5 because of action uncertainty.
This section considers an office environment generated from PyBullet3.0 [36], a virtual robotic platform, as shown in Figure 7. First, we map this virtual office environmenttoagridworldtolearntheoptimalpolicy.Then, the policy is applied to TurtleBot2 in PyBullet, where we can implement the robotic dynamics and a PID controller to ensure the robot follows the path generated from the derived policy.
T h ee n v i r o n m e n th a sf o u ro ffi c er o o m sd e n o t e da s 'a', 'b', 'c', and 'd', the storage room as 'S', the printer's room as 'Print', and the supply station for the robot to r ec h a r g en o t eda s' S p l y ' .tw ob i gwi n d o w s( f a c i n gw e s t ) are located at offices 'a' and 'd'. In addition, the robot can also observe 'wall', 'hallway', and 'door'. The sensor and actuator uncertainties can be modeled as the observation and action probabilities in the POMDP abstraction, as discussed in [37,38]. We consider two different observation settings in this example. We also assume that the TurtleBot can successfully follow its navigation controller by moving in the intended direction, with a probability of 0.9. Otherwise, the agent will accidentally move toward any other direction with the same probability (the total probability is 0.1). Moving toward the wall will keep the robot staying at the same location.
Theofficespaceisdividedin toa4b y4gridwith16 states. There are two big windows (facing west) located at offices 'a' and 'd' that the TurtleBot (i.e. the agent) can sense by its embedded sensors. In addition, the agent can also observe 'wall', 'hallway', and 'door'. Given a specified task, we can formulate this office scenario as a product POMDPproblemandapplytheSARSOPsolvertoobtain the optimal policy. Two different observation settings are considered in this study.
In this setting, the agent can observe the surrounding information of the current state in all four directions without a specific order. There are a total of 8 observations, and each state has only one observation. For In Case 1, starting from an initial position, the Turtle-Bot visits the printer's room to collect the documents and then carries the documents to offices 'a' or 'c' recurrently. Meanwhile, TurtleBot shall avoid the storage room. This task can be formulated via LTL as below, and the induced LDGBA with only single-label transitions has four automaton states.
Figure 8(a) shows that, following the optimal policy, the TurtleBot starts from the end of the hallway (i.e. its initial position) and arrives at the printer's room first, as t h er e dr o u t ei n d i c a t e s .T h ea g e n tt h e nl e a v e si m m e d iately after picking up the documents and heads to office room 'c', as the yellow route shows. Figure 8(b) shows that the TurtleBot leaves office 'c' and continuously completesthesecondround.SinceT urtleBotcanobserveall fourdirections,itmadethebeliefcon vergencefast,and the agent can plan the path accordingly. The path appears that TurtleBot efficiently completed the task with small action uncertainty indicated as the to-and-fro part of the yellow path.
C a s e2r e q u i r e st h eT u r t l e Bo tt ov i s i tt h es u p p l ys t ation right after it accomplishes the delivery task in Case 1, and the storage room must also be avoided during the entire task. The LTL formula of Case 2 in ( 22) is extended from part of the formula (21) used in Case 1, denoted as ϕ 1 . Different from the task in Case 1, we only require the agent to complete one run in Case 2.
As shown in Figure 9, the TurtleBot starts from office 'b' (as the initial state), moves to the print room, and delivers the documents to office 'a'. Then, it arrives at the 'Sply'stationtocompletethistask.T wostatesonthered r o u t ea r ev i s i t e dm o r et h a no n c eb e c a u s eo ft h ea c t i o n uncertainty.
In another observation setting, the agent can only observeononedirectionateachstateitvisits.Theobservation set is 'wall', 'hallway', 'door', 'window'. Assuming each observation has the same chance of being detected by the agent's sensors, the observation probabilities can be calculated. For example, the agent can observe 'door', 'wall', and 'window' with probabilities of 0.25, 0.5, and 0.25, respectively, in office 'a'. It can be seen that the observation uncertainty is much higher than that in the previous observation setting. Consequently, the computation time is longer for the agent to learn the optimal policies, as shown in Table 2.
Compared with the path with all four-directional observations, a single observation element provides the agent less sense of what the current state is, the increased observation uncertainty brought the difficulty of the optimalpathplanning.AsFigures10 and 11 show, the agent encountered difficulty in selecting the suitable actions especially around the 'hallway' states between the office r oo m s' c ' ,' d ' ,a n dp r i n t e r ' sr oo m ,wh i c ha p pe a r sa st h e bends and edges in the planned paths.
This paper tends to solve POMDP problems with highlevel and complex tasks that can be formulated via LTL andthenconvertedtoLDGBAs.Suchamotionplanning p r o b l e mb e c a m ee q u i v a l e n tt ofi n d i n ga no p t i m a lp o licy on the product of POMDP and the induced LDGBA. Two model-based RL approaches are adopted to derive th eo p tim alpo licya safun ctio no fth ebe liefs ta t e .On e approach is based on the PBVI methods, and we utilize th eSARSO Pso l v ero nth ep r od uctPO MD Pt oa p p r o ximate the optimal value functions. In another approach, we employ a CNN architecture for Q-networks in DQN to map the relationship between a belief state and its optim a ls t a t e -a c t i o nv a l u e s( i . e .Qv a l u e s ) .T oa d d r e s st h e issue that LDGBA may fail to find the deterministic policy for some task specifications. We redesign the reward function and introduce a frontier-tracking function for the above-mentioned approaches, respectively. The simulations demonstrate that the agent could accomplish the specified tasks by following the derived optimal policies. In addition, we perform the scalability study on the value iteration approach. In contrast, DQN is more computationally intensive because many episodes are needed for convergence while updating the belief state at each step. However, with the implementation of the frontier-tracking function, DQN is adaptive to various task specifications. In future works, our proposed DQN approach can be potentially extended to a hybrid framework accommodating both model-free and model-based approaches, in which the belief state can be updated based on the approximation of transition and observation likelihoods. Furthermore, this DQN approach can also be combined with Inverse reinforcement learning (IRL) in POMDPs to use the learned Q-values as a feature to extract the rewards in problems with large state spaces. Thisapproachhasbeenexploredinotherworks [39,40] and can be further researched.
This study focuses on high-level motion planning to find the optimal policy for the agent to accomplish user-specified complex tasks. Although we use a virtual TurtleBot2 on PyBullet3.0 to validate the derived policy, it would be interesting to incorporate the internal controllers of a robot in real-world applications. Fainekos et al. In that case, the discrete action needs to be mapped to the desired linear and angular velocities, by considering the robot's dynamics and kinematics. The low-level controllers, such as a PID controller, can send the control signals to the actuators (e.g. the motors) to drive the wheels. At the same time, the observations captured by the agent's embedded sensors serve dual purposes in the POMDP framework. Firstly, they provide feedback to the trajectory control between the states. Secondly, the observations can also be used to update the agent's belief state for the high-level decision-making process.
The proposed model-based approaches have limitationsbecausethetransitionandobservationprobabilities must be provided to update the belief state. Model-free RL methods will be considered for POMDPs with LTL specifications in future works. In that case, the decisionmaking will depend on the history of observations or actions.
1. https://github.com/JunchaoLi001/LDGBA-Model\_
Checking.
No potential conflict of interest was reported by the author(s).
Li, Wang, and Xiao would like to thank US Department of Education (ED#P116S210005) and US National Science Foundation NSF (#2226936) for supporting this research.