Reverse Thinking Approach to Deceptive Path Planning Problems

Abstract

Deceptive path planning (DPP) aims to find routes that reduce the chances of observers discovering the real goal before its attainment, which is essential for addressing public safety, strategic path planning, and preserving the confidentiality of logistics routes. Currently, no single metric is available to comprehensively evaluate the performance of deceptive paths. This paper introduces two new metrics, termed “Average Deception Degree” (ADD) and “Average Deception Intensity” (ADI) to measure the overall performance of a path. Unlike traditional methods that focus solely on planning paths from the start point to the endpoint, we propose a reverse planning approach in which paths are considered from the endpoint back to the start point. Inverting the path from the endpoint back to the start point yields a feasible DPP solution. Based on this concept, we extend the existing ${\pi }_{d1~4}$ method to propose a new approach, ${e\_\pi }_{d1~4}$, and introduce two novel methods, Endpoint DPP_Q and LDP DPP_Q, based on the existing DPP_Q method. Experimental results demonstrate that ${e\_\pi }_{d1~4}$ achieves significant improvements over ${\pi }_{d1~4}$ (an overall average improvement of 8.07%). Furthermore, Endpoint DPP_Q and LDP DPP_Q effectively address the issue of local optima encountered by DPP_Q. Specifically, in scenarios where the real and false goals have distinctive distributions, Endpoint DPP_Q and LDP DPP_Q show notable enhancements over DPP_Q (approximately a 2.71% improvement observed in batch experiments on 10 × 10 maps). Finally, tests on larger maps from Moving-AI demonstrate that these improvements become more pronounced as the map size increases. The introduction of ADD, ADI and the three new methods significantly expand the applicability of ${\pi }_{d1~4}$ and DPP_Q in more complex scenarios.

1. Introduction

Deception has long been a focal point in computer science, representing a significant hallmark of intelligence [1]. In fields like multi-agent systems and robotics, path planning serves as a foundational element for achieving collaborative task objectives. Deception becomes pivotal in enabling agents to gain strategic advantages in games and adversarial settings. In adversarial environments, deceptive planning empowers both human and AI agents to obscure their true intentions and manipulate the situational awareness of opponents. Beyond gaming contexts, deception is prevalent in diverse multi-agent applications, including negotiations [2,3] and fugitive pursuit scenarios [4]. In adversarial contexts, deceptive planning allows intelligence operatives to obfuscate their true intentions and confound the awareness of adversaries, thereby finding practical use in domains such as network security [5], robot soccer competitions [6], privacy preservation [7], and other real-world challenges. Deceptive path planning (DPP) has thus emerged as a pivotal task within this broader landscape.

Imagine a scenario in urban surveillance in which SWAT teams have located traces of terrorists on city streets. If SWAT teams reveal their intentions and proceed directly to the hideout of terrorists, they risk alarming them, potentially leading to escape. Therefore, the teams can strategize a decoy route, departing from a designated point and feigning a circuitous advance towards other locations to mislead the adversaries. This strategy aims to deceive terrorists into believing that SWAT teams’ objective is not their actual hiding place. Ultimately, the SWAT teams can reach and apprehend or eliminate terrorists. The purpose of this approach is to deceive the surveillance systems and observers of terrorists, thereby concealing the true objective of the SWAT teams to the fullest extent possible.

Consider a scenario in wildlife conservation in where researchers select suitable areas within a vast protected area to reintroduce endangered species. Poachers are monitoring the movement of these animals for their illegal hunting activities. Directly approaching the habitat of these animals can jeopardize their safety. Conversely, planning a circuitous route would deceive potential poachers, ensuring the safety of the animals while minimizing the risk of detection.

Previous research on DPP problems has raised several issues and opportunities for improvement. Firstly, while Masters et al. proposed three metrics (extent, magnitude, and destiny) for evaluating deceptive paths [8], each has its limitations. Extent and destiny merely assess whether grid points along a path are deceptive or not, a binary evaluation without quantifying deception on a scale from 0 to 1. Although magnitude quantifies deception, it lacks normalization. DPP_Q [9], incorporating the concept of “average deceptiveness”, considers paths under specific time constraints where all paths have equal costs, failing to address how paths with varying time costs should be compared. Therefore, unified metrics for comprehensively evaluating the performance of deceptive paths are lacking.

Secondly, DPP_Q tends to fall into local optima when the number of false goals increases. Our experiments indicate that agents trained using the DPP_Q method exhibit a tendency to initially move towards false targets from the starting point. While this approach may yield substantial rewards initially, the fixed time constraints of DPP_Q prevent agents from balancing deception in the subsequent planning phases. Figure 1a illustrates this phenomenon using a heatmap based on a 49 × 49 grid map from the Moving-AI dataset, devoid of obstacles. The orange square (with a black border) represents the start point, the blue square (with a black border) is the real goal, and the teal squares (with black borders) are two false goals. The heatmap visualizes the posterior probability of the real goal at each grid point, ranging from 0 to 1, influencing the agent to bypass the lighter-colored points for greater deception (reward). When the agent begins exploring from the starting point, it tends to follow the direction indicated by the red arrow initially, which is detrimental to subsequent planning. Conversely, following the green arrow direction may not yield immediate rewards but offers greater potential rewards later. In Figure 1b, starting planning from the real goal allows the agent to avoid biased initial exploration tendencies influenced by the heatmap.

Thirdly, the initial exploration tendency exhibited by the agent in DPP_Q resembles that of ${\pi }_{d1}$ [8]. ${\pi }_{d1}$ guides the agent towards false goals initially before proceeding to the real goal, contrasting with ${\pi }_{d2~4}$ methods lacking such tendencies. This distinction typically results in ${\pi }_{d1}$ achieving greater deceptive effects compared to ${\pi }_{d2~4}$ methods and explains why paths generated by ${\pi }_{d1}$ entail longer costs. Therefore, we propose that the ${\pi }_{d2~4}$ methods could be further optimized based on the tendency of the ${\pi }_{d1}$ method. One potential improvement involves adjusting the Last Deceptive Point (LDP), a concept to be detailed later.

This article has three main technical contributions. Firstly, we introduced the concept of Average Deception Degree (ADD), based on which we proposed the Average Deception Intensity (ADI) and analyzed its rationality, applying it to evaluate subsequent methods. Secondly, for ${\pi }_{d1~4}$ methods that do not consider time constraints, we proposed ${e\_\pi }_{d1~4}$, which can significantly enhance traditional ${\pi }_{d1~4}$ methods. Thirdly, for DPP_Q which considers time constraints, we propose Endpoint DPP_Q and LDP DPP_Q, both resolving issues of suboptimal DPP problems under specific distributions of goals.

The structure of this paper is as follows: In Section 2, we review the relevant literature on probabilistic goal recognition and DPP problems. Section 3 provides foundational definitions of these concepts. Section 4 defines ADD and ADI briefly, introduces ${\pi }_{d1~4}$ methods and subsequently proposes ${e\_\pi }_{d1~4}$. Subsequently, in Section 4 we introduce DPP_Q, outlining the operational mechanisms of the new methods Endpoint DPP_Q and LDP DPP_Q. In Section 5, based on the ADI, we validate the feasibility of our methods through experiments. Lastly, we conclude with a summary and outlook for this paper.

2. Related Work

2.1. Plan Recognition and Probabilistic Goal Recognition

In the study of agent goal recognition, two key factors are often considered: the competitive dynamics and the level of rationality exhibited by the observed agents. The relationship between the observer and the observed can be categorized into Keyhole scenarios [10], where observed agents are indifferent to the observer’s behavior due to the absence of competitive or cooperative interactions; Adversarial scenarios [11], where observed agents adopt a hostile stance towards the observer’s actions; and Intended scenarios [12], where observed agents cooperate openly with the observer, sometimes assisting in the recognition process. DPP problems primarily focus on adversarial scenarios.

The problem of goal recognition has been explored using various approaches, including graph coverage on planning graphs [13], parsing using grammar methods [14,15,16,17], deduction and probabilistic reasoning on static or dynamic Bayesian networks [18,19], and inverse planning models [20,21]. Bui et al. [22] introduced an online probabilistic plan recognition framework based on Abstract Hidden Markov Models (AHMM). Ramirez and Geffner aligned observed outcomes with predefined plans, computing costs separately for each potential goal [23]. Assuming agent rationality allows for the evaluation of goal types. Masters et al. [24] proposed a traditional cost-difference-based goal recognition model that, estimates goal probabilities based on cost disparities between optimal paths matching current observations and those that ignore specific nodes in the observation sequence.

2.2. Deception and Deceptive Path Planning

Initially, “deceptive information” emerged as a significant focus in deception research. Floridi proposed that “misinformation is structurally well-formed, meaningful false data, whereas deceptive information is intentionally transmitted false information designed to mislead the recipient” [25]. Fetzer [26] categorized five types of deceptive information: intentional misinformation created by information producers to distort and mislead targets, deceptive information formed through selective filtering and sophistry against existing information, deceptive information disseminated by information disseminators attacking information producers based on reasons unrelated to or misleading from the stance represented by the information producer, deceptive information generated based on irrational beliefs, and deceptive information resulting from incompetent commentary. Fallis [27] summarized three characteristics of deceptive information: it is a type of information with the basic attributes of information, it is misleading information, and it is not accidental or unintentional.

Deception also has a long history in computer science, especially holding prominence in artificial intelligence research and game theory. In particular, the article “Deceptive AI” [28] provides a detailed analysis of common types of deception, different characteristics, and typical application scenarios. By referencing examples from various branches of artificial intelligence, this article categorizes deception research into five new categories and describes them based on human-like features: imitating, obfuscating, tricking, calculating, and reframing. Bell et al. proposed a balanced approach to belief manipulation and deception [29], where agents have only a coarse understanding of their opponents’ strategies and little knowledge of details. This method can be viewed as a game theory setting, expressed in terms of social psychology as “fundamental attribution error.” It is often applied to bargaining problems, revealing that deceptive strategies may be more easily executed. Arkin et al. [30] mentioned that deception has always been used as a means to gain military advantage.

Masters et al. [8] formalized Deceptive Path Planning (DPP) problems in path planning domains, demonstrating that qualitative comparisons of posterior probabilities of goals do not necessarily require the entire observation sequence but only the last node. They introduced the concept of the Last Deceptive Point (LDP) and proposed traditional DPP methods based on the A* algorithm and heuristic pruning. These methods prioritize “dissimulation” without precise quantification of each grid’s deceptiveness and do not explicitly model time constraints. Cai et al. [31] researched DPP in dynamic environments using two-dimensional grid maps. Xu et al. [32] applied mixed-integer programming to estimate grid deceptiveness based on magnitude, proposing a method that combines time consumption and quantified deceptiveness. Liu et al. [33] introduced the Ambiguity Model, which integrates optimal Q-values of path planning with deceptiveness to derive ambiguous paths. Lewis [34] addressed the limitations of the Ambiguity Model when learning Q-functions through model-free methods, proposing the Deceptive Exploration Ambiguity Model, which demonstrated improved performance. Chen et al. [9] proposed a method called DPP_Q for solving DPP problems under specific time constraints and extended it to continuous domains as well (DPP_PPO).

3. Preliminaries

Before explaining the specific details of $e\_{\pi }_{d1~4}$, Endpoint DPP_Q and LDP DPP_Q, it is necessary to explain its basic techniques. In this section, we first present the definition of path-planning domains, followed by the definition of path-planning problems [8]. Next, we introduced the Precise Goal Recognition Model (PGRM) [9], which serves as a goal recognition model for the observer, and finally, we defined DPP problems [8].

Definition 1. 

A path planning domain is a triple $D=⟨N,E,c⟩$:

• N is a set of non-empty nodes (or locations);
• $E\subseteq N\times N$ is a set of edges between nodes;
• $c:E\mapsto {\mathbb{R}}_0^{+}$ returns the cost of traversing each edge.

A path $\pi$ in a path planning domain is a sequence of nodes such as $\pi =n_0,n_1,\dots ,n_k$, in which $\left(n_i,n_{i+1}\right)\in E$ for each $i\in \{0,1,\dots ,k-1\}$. The cost of $\pi$ is the cost of traversing all edges in $\pi$, which is $cost\left(\pi \right)=\sum _{i=0}^{k-1}c\left(n_i,n_{i+1}\right)$, from the start node to the goal node.

A path planning problem in a path planning domain is the problem of finding a path from the start node to the goal node. Based on Definition 1, we define the path planning problem as follows.

Definition 2. 

A path planning problem is a tuple $⟨D,s,g⟩$:

• $D=⟨N,E,c⟩$ is a path planning domain;
• $s\in N$ is the start node;
• $g\in N$ is the goal node.

The solution path for a path planning problem is a path $\pi =n_0,n_1,\dots ,n_k$, in which ${s=n}_0$ and ${g=n}_k$. An optimal path is a solution path with the lowest cost among all solution paths. The optimal cost for two nodes is the cost of an optimal path between them, which is denoted by $optc\left(n_i,n_j\right)$. The A* algorithm [35], a well-known best-first search algorithm, is used by typical AI approaches to find the optimal path between two nodes.

When the number of targets exceeds one, an observer assigns a probability value to each target. Assuming that the path planning domains are discrete, fully observable, and deterministic, we introduce the PGRM as follows:

Definition 3. 

Precise Goal Recognition Model (PGRM) is a quadruple $⟨D,G,O,P⟩$:

• D is a path planning domain;
• $G=\left\{g_r\right\}\cup G_f$ is a set of goals, consisting of the real goal g_r and a set of false goals G_f;
• $O=o_1,o_2, \dots , o_{\left|O\right|}$ is the observation sequence, representing the sequence of all grid points that the observed has passed through from the start node to the current node.
• P is a conditional probability distribution $P\left(G\right|O)$ across G, given the observation sequence O.

Based on Definition 3, the formula for calculating the cost-difference is:

$$costdiff(s,O,g)=optc(s,O,g)-optc(s,O,g), for all g\in G$$

(1)

where $costdiff(s,O,g)$ represents the cost-difference for each g in G; $optc(s,O,g)$ represents the optimal cost for the observed to reach g from s given the observation sequence O; $optc(s,O,g)$ represents the optimal cost for the observed to reach g from s without the need to satisfy the observed sequence O.

From Equation (1), the cost-difference for all goals in the set G can be computed. Subsequently, Equation (2) allows us to calculate their posterior probability distribution. The formula for computing $P\left(G\right|O)$ for each goal is as follows:

$$P\left(G\right|O)=\alpha e^{-\beta costdiff(s,O,G)}/{(1+e}^{-\beta costdiff(s,O,G)})$$

(2)

where $\alpha$ is a normalization factor, $\beta$ is a positive constant, satisfying $1\ge \beta \ge 0$. $\beta$ is used to describe the degree to which the behavior of the observer tends toward rational or irrational, namely “soft rationality”. $\beta$ indicates the sensitivity of the observer to whether the observed is rational. When the observed is fully rational, it will choose the least costly method (the optimal path) to reach its real goal. The larger $\beta$, the more the observer believes that the behavior of the observed is rational. When $\beta =0$, $P\left(g_i\right|O)=P(g_j\left|O\right), \forall g_i,g_j\in G$, which means that the observed is considered completely irrational, so that the posterior probabilities of all goals are equal.

Based on Definition 3, we define the deceptive path planning problem.

Definition 4. 

A deceptive path planning (DPP) problem is a quintuple $⟨D,s,g_r,G,P⟩$:

• D is a discrete path planning domain;
• $s\in N$ is the start node;
• $g_r\in N$ is the real goal node;
• $G=\left\{g_r\right\}\cup G_f$ is a set of possible goal nodes, in which g_r is a single real goal and G_f is the set of false goals;
• $P\left(G|O\right)$ is the posterior probability distribution of G based on the observation sequence O. Its calculation is determined by the goal recognition model of the observer.

Here, PGRM will serve as the recognition model of the observer to calculate the $\mathrm{P}\left(\mathrm{G}|\mathrm{O}\right)$. DPP presents a departure from conventional path planning. While typical path planning endeavors to find the most cost-effective route to a destination, c In this context, the objective extends beyond mere navigation to the goal; it includes minimizing the likelihood of an observer identifying the real goal among a set of possibilities.

4. Method

This section was divided into three parts. Firstly, we present the definitions of Average Deception Degree (ADD) and Average Deception Intensity (ADI). Secondly, we introduce ${\pi }_{d1~4}$ methods, and then proposed $e\_{\pi }_{d1~4}$. Finally, we introduced DPP_Q [9] and propose Endpoint DPP_Q and LDP DPP_Q.

4.1. Average Deception Degree (ADD) and Average Deception Intensity (ADI)

Masters et al. stated that “The quality of the solution depends on the magnitude, density, and extent of the deception” [8], yet these three metrics do not account for the cost of the path. With a sufficient time budget, we should be able to plan paths that achieve better deception effects. We exclude cases where the number of grid points covered by a path is less than or equal to 2, meaning the distance between the start point and the real goal must be greater than one grid point distance (either $\sqrt{2}$ or 1). Otherwise, DPP problems would be meaningless. To comprehensively evaluate a deceptive path, we introduce two new evaluation metrics: Average Deception Degree (ADD) and Average Deception Intensity (ADI). Here, we define ADI as follows:

Definition 5. 

The average deception degree of a path $\pi$ is $\overline{D}={\displaystyle \frac{{\sum }_{i=1}^{k-1}(1-P(g_r\left|O_i\right))}{k-1}}$, such that:

• $\pi =n_0,n_1,..,n_k, k\ge 2$ is a path (a solution to a DPP problem);
• $P\left(g_r\right|O_i)$ is the posterior probability of the real goal of n_i calculated by PGRM, $0\le i\le k$;
• $O_i=n_0,\dots ,n_i$, for each node n_i the observed passed through, there exists the observation sequence $O_i, 0\le i\le k$.

Since the deception value is defined at each node, the quantifiable average deceptiveness of a path, referred to as ADD, is calculated as the sum of the deception values at each node divided by the total number of nodes (excluding the start and end nodes). When two paths consume the same amount of time, ADI serves as a direct measure to quantify the overall deceptive magnitude of a path. Based on Definition 5, we propose Definition 6:

Definition 6. 

The average deception intensity of a path $\pi$ is $I=\overline{D}/c^{\mu }$, such that:

• $\overline{D}$ is the average deception degree of the path;
• c is $cost\left(\pi \right)=\sum _{i=0}^{k-1}c\left(n_i,n_{i+1}\right), \pi =n_0,n_1,\dots ,n_k, k\ge 2$.

$\mathsf{\mu }$ represents the degree of importance placed on time. Typically, $\mathsf{\mu }$ ranges from 0 to 1. $\mathsf{\mu }=0$ indicates that the observed does not care about the time consumed by the path.

ADI measures the contribution of a path per unit of time to ADD. In the absence of considering path cost, a higher ADD for a path indicates better deceptive effectiveness. When considering path cost, the overall effectiveness of a path relates to the emphasis on the observed on time. ADI not only synthesizes the contribution of each node on a path to its ADD but also accounts for time constraints. It serves as a highly comprehensive indicator that reflects the overall deceptive effectiveness of a path. Overall, ADI is a reliable and direct standard for measuring the deceptive effectiveness of the two paths.

4.2. Deceptive Path Planning (DPP) via ${\pi }_{d1~4}$ and $e\_{\pi }_{d1~4}$

Firstly, ${\pi }_{d1~4}$, as detailed by Masters et al. [8], aim to maximize the Last Deceptive Point (LDP). The methods involve two main steps, as illustrated in the left half of Figure 2. Step A identifies g_min from the false goals, which is the most important false goal in the DPP problem, and Step B determines the LDP based on g_min. The paths planned by ${\pi }_{d1~4}$ will be illustrated by the red arrows in the right half of Figure 2. Based on these, we introduce the ${\pi }_{d1~4}$ as follows:

${\pi }_{d1}$ uses a “showing false” strategy where the observed navigates from the start point to g_min, and then continues to the real goal g_r. The path generated by ${\pi }_{d1}$ is a combination of two parts: ${\pi }_{d1}={\pi }_{A*}(s\to g_{min})+{\pi }_{A*}(g_{min}\to g_r)$. Similar to ${\pi }_{d1}$, ${\pi }_{d2}$ focuses on identifying key node LDP on the optimal path from g_min to g_r. Instead of navigating directly to g_min, it first heads towards LDP, then to g_r. The path generated by ${\pi }_{d2}$ is a combination of two parts: ${\pi }_{d2}={\pi }_{A*}(s\to LDP)+{\pi }_{A*}(LDP\to g_r)$. Based on ${\pi }_{d2}$, ${\pi }_{d3}$ also heads toward LDP first, but it introduces a modified heuristic approach biased toward the false goal g_min to increase the deceptive potential of the path. The path generated by ${\pi }_{d3}$ is a combination of two parts: ${\pi }_{d3}={\pi }_{A*\left(heuristic\right)}(s\to LDP)+{\pi }_{A*}(LDP\to g_r)$. ${\pi }_{d4}$ utilizes a pre-computed probability “heatmap” to enhance path deception, significantly increasing the cost of $\pi (s\to LDP)$ to improve its deception. The path generated by ${\pi }_{d4}$ is a combination of two parts: ${\pi }_{d4}=\pi (s\to LDP)+{\pi }_{A*}(LDP\to g_r)$. In Figure 2, ${\pi }_{d3}$ shows a clear tendency to approach the false goal g_min, indicating higher deception compared to ${\pi }_{d2}$ with the same cost consumption. ${\pi }_{d4}$, although potentially less deceptive than ${\pi }_{d1}$ in terms of deception level, it significantly reduces path duration compared to ${\pi }_{d1}$ in the same DPP problem.

To further introduce $e\_{\pi }_{d1~4}$ methods, as depicted in the right half of Figure 2, the process of $e\_{\pi }_{d1~4}$ involves several steps. First, following Step A, once g_min is identified, Step C transforms the positions of “start” and “real goal”. Here, the original real goal becomes the new start point, and the original start point is designated as the new real goal. Simultaneously, all false goals except g_min are removed. This sets up a new DPP problem where the original real goal is the starting point, the original start point is the new real goal, and g_min remains as the sole false goal.

Building upon the new DPP problem, Step D identifies the new g_min (which, due to the deletions of other false goals, corresponds to g_min from the original path planning problem), followed by Step E to find the LDP for the new DPP problem. Subsequently, path planning proceeds based on ${\pi }_{d1~4}$. This approach yields four deceptive paths from “(start)” to “(real goal)” in Figure 2 based on this new path planning problem. These paths are then reversed to obtain four paths for the original deceptive path planning problem, as indicated by the green arrow on the right half of Figure 2.

To facilitate further understanding of the differences between ${\pi }_{d1~4}$ and ${e\_\pi }_{d1~4}$, we also present the new DPP problem where additional false goals are not deleted in Figure 3. In contrast to the original DPP problem, in Figure 3, after Step A, g_min is different from the original DPP problem. Consequently, the LDP point also changes: from (6,5) in Figure 2 to (6,3) in Figure 3 (where the horizontal axis represents the x-coordinate and the vertical axis represents the y-coordinate, starting from 0). The resulting four paths generated by the ${\pi }_{d1~4}$ method are depicted in the right half of Figure 3 as indicated by red arrows.

4.3. Deceptive Path Planning (DPP) via DPP_Q, Endpoint DPP_Q and LDP DPP_Q

We will provide a unified introduction to DPP_Q, Endpoint DPP_Q, and LDP DPP_Q. The core of these three methods is based on reinforcement learning modeling using Count-Based Q-learning. Below, we first introduce the state space, action space, and reward function of the observed as follows:

4.3.1. The State Space

The state space of the observed includes its current coordinate $(x,y)$, as well as the number of straight and diagonal movements made by itself (denoted as $n_{Straight}$ and $n_{diagonal }$ respectively). The state space S is defined as a four-dimensional vector:

$$S=\{x,y,n_{Straight},n_{diagonal }\}$$

(3)

4.3.2. The Action Space

The observed can take actions of two types: straight movements (up, down, left, right) and diagonal movements (up–left, down–left, up–right, down–right). The time required for straight movements is 1, while that of diagonal movements takes $\sqrt{2}$. Specifically, the action space is a matrix:

$$Actions=\left[\right[0, 1, 1, 0], [0,-1, 1, 0], [-1, 0, 1, 0], [1, 0, 1, 0],[-1,-1, 0, 1], [-1, 1, 0, 1], [1,-1, 0, 1], [1, 1, 0, 1\left]\right]$$

(4)

It means the observed has eight actions. Each of them was represented as a 4-dimensional vector corresponding to the state space S. The first two dimensions update the current coordinate of the observed (x, y), while the last two dimensions update the counts of straight and diagonal movements made by the observed. Given the state s_T, the next state s_T+1 can be obtained by simple vector addition:

$${s_T=s}_{T-1}+Actions\left[i\right]$$

(5)

i = 0, 1, 2, …, 7 represents the index of the action taken by the observed.

4.3.3. The Reward Function

Chen et al. [9] proposed an Approximate Goal Recognition Model (AGRM) based on PGRM and conducted comparative experiments using two different reward mechanisms, demonstrating the reliability of AGRM in computing rewards for the observed. Different from PGRM matching full of the observation sequence $O=o_1,o_2, ..., o_{\left|O\right|}$, the observer based on AGRM only matches the current node of the observed $o_{\left|O\right|}$. Specifically, the formula for calculating the cost-difference is:

$$costdiff(s,o_{\left|O\right|},g)=optc(s,o_{\left|O\right|})+optc(o_{\left|O\right|},g)-optc(s,g)$$

(6)

The formula for computing $\mathrm{P}\left(\mathrm{G}\right|{\mathrm{o}}_{\left|\mathrm{O}\right|})$ for each goal is as follows:

$$P\left(G\right|o_{\left|O\right|})=\alpha e^{-\beta costdiff(s,o_{\left|O\right|},G)}/(1+e^{-\beta costdiff(s,o_{\left|O\right|},G)})$$

(7)

The observed is trained by AGRM. While training with PGRM is also feasible, AGRM allows for the advanced allocation of fuzzy rewards to each grid point, thereby circumventing the time-consuming reward computation during subsequent training in reinforcement learning. Specifically, assuming the current state s_T of the observed, the formula for its basic reward is as follows:

$$R=1-P\left(g_r\right|\left(s_T\right[0],s_T[1\left]\right))$$

(8)

where $\left(s_T\right[0],s_T[1\left]\right)$ represents the current coordinate of the observed n_current, that is, $o_{\left|O\right|}$.

We employed the count-based method to encourage the observed to explore unknown states. The count-based method can guide the observed to explore state-action pairs with higher uncertainty to confirm their high rewards. The uncertainty of the observed relative to its environment can be measured by $\delta /\sqrt{N(s, a)}$ [36], where $\delta$ is a constant and $N(s, a)$ represents the number of times the state-action pair $(s, a)$ has been visited. Specifically, $\delta /\sqrt{N(s, a)}$ is set as an additional reward used to train the observed:

$$r_{add}(s, a)=\delta /\sqrt{N(s, a)}$$

(9)

Intuitively, if the observed visited a state-action $(\mathrm{s},\mathrm{a})$ pair less frequently (i.e., $\mathrm{N}(\mathrm{s},\mathrm{a})$ is smaller), the corresponding additional reward will be larger. Thus it should be more inclined to visit this state-action pair to confirm whether it has a high reward. The rules for the observed to receive rewards are as follows:

• If the remaining time exceeds the shortest time the observed takes to reach the target, indicating it cannot arrive at the target within the time constraint. This scenario is denoted as Condition A, with a reward of −9 given.
• The observed successfully reaches the target, which is denoted as Condition B, with a reward of +100 given.
• Typically, the observed receives the deceptiveness of each grid point it traverses.

Specifically, the observed receives exploration rewards to encourage it to explore unknown state-action pairs. The reward function is shown as follows:

$$r(s, a)=\left\{\begin{array}{c}-9+r_{add}(s, a), Condition A \\ +100+r_{add}(s, a), Condition B\\ R+r_{add}(s, a), else\end{array}\right.$$

(10)

Below, we provide pseudocode for DPP_Q, Endpoint DPP_Q and LDP DPP_Q, using a 10 × 10 grid map as an example, accompanied by detailed explanations.

Algorithm 1 introduces the DPP problem and initializes it. It first sets up the learning rate, discount factor, and epsilon-greedy value, and initializes matrices D and D_s. D is a 10 × 10 matrix storing the shortest path lengths (equivalent to optimal time cost) from each grid point to the real goal g_r. D_s is a 10 × 10 matrix storing the optimal time cost from each grid point to the start point s₀. Furthermore, Algorithm 1 reads in various elements of the DPP problem: time constraints, obstacle coordinates, starting point coordinates, real goal coordinates, and coordinates of all fake goal points (line 1). Then, it initializes the Q-table and the counting matrix N-table, setting Q-values of illegal actions to −1000 (lines 2 to 3).

Algorithm 1 DPP via Q-learning (Initialization and Problem Setup)

$\mathbf{Require}: \mathrm{A} \mathrm{DPP} \mathrm{problem} \mathrm{with} \mathrm{a} 10 \times 10 \mathrm{gird} \mathrm{map}.$ $\mathbf{Parameter}: \mathrm{learning} \mathrm{rate} \alpha$$, \mathrm{discount} \mathrm{factor} \gamma$$, \mathrm{epsilon} \mathrm{greedy} \epsilon$.     1: Initialize distance matrix D and Ds, time constraint TC, collection of obstacle Wall,         start node s0$, \mathrm{real} \mathrm{goal} g_r, \mathrm{false} \mathrm{goal} \mathrm{set} G_f \mathrm{of} \mathrm{the} \mathrm{DPP} \mathrm{problem}.$     $2: \mathrm{Initialize} \text{Q-table} \mathrm{and} \text{N-table} \mathrm{with} \mathrm{zeros}.$     $3: \mathrm{Set} Q(s_i,a_i)=-1000$$\mathrm{for} \mathrm{all} \mathrm{illegal} (s_i,a_i)$ resulting in the agent out of the map.

Algorithm 2 describes the training process of the observed. First, the observed checks the legality of eight actions (lines 1 to 5). Then, the observed selects an action according to $\epsilon -greedy$ policy, and the state-action pairs are counted (lines 6 to 9). Subsequently, the observed receives a reward and updates the Q-table and the state (lines 10 to 13).

Algorithm 2 DPP via Q learning (Training Framework)

1:  $\mathbf{for} a$$\mathrm{in} \mathit{Actions}:$  2:     $\mathbf{if} s+a \mathrm{in} \mathit{Wall}:$  3:        $Q(s,a)=-1000$  4:      $\mathbf{end} \mathbf{if}$  $5: \mathbf{end} \mathbf{for}$  $6: \mathrm{Choose} \mathrm{an} \mathrm{action} a \mathrm{satisfying} Q(s,a)\ne -1000$:  7:     $\mathrm{Select} \mathrm{the} \mathrm{action} \mathrm{with} \mathrm{maximum} \text{Q-value} \mathrm{with} \mathrm{probability} 1-\epsilon$  8:     $\mathrm{Select} \mathrm{a} \mathrm{random} \mathrm{action} \mathrm{with} \mathrm{probability} \epsilon$  9:  $N(s,a)=N(s,a)+1$ $10: \mathrm{Calculate} r(s,a)$ $11: s^{\prime }=s+a$ $12: Q(s, a)=(1-\alpha )Q(s, a)+\alpha (r+\gamma \underset{{\mathit{a}}^{\prime }}{\max }Q(s^{\prime }, a^{\prime }))$ $13: s=s^{\prime }$

Algorithm 3 describes the DPP_Q method. It first initializes the problem according to Algorithm 1. Then, it sets the initial start point of the observed as s₀ and initializes its values for the next two dimensions to 0 (line 2). Each training round includes checking the termination condition: whether the remaining time exceeds the shortest observed time to reach the target (the real goal g_r), indicating that the observed cannot reach the real goal within the time constraint $TC-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D\left[s\right[0],s[1\left]\right]$, or the current coordinate of the observed coincide with the coordinate of the target (the real goal g_r) s_coord = g_r (line 5). Finally, the optimal path can be collected using the method of tracking the maximum value of the Q-table (line 10).

Algorithm 3 DPP_Q

Algorithm 1 $1: \mathbf{for} \mathit{episode}\mathrm{in} \mathrm{Episodes} \mathrm{do}$ 2:     $\mathbf{Initialize} s={[s}_0\left[0\right], s_0\left[1\right], 0, 0]$ 3:     $\mathbf{while} \mathrm{True}:$ 4:         Algorithm 2 5:         $\mathbf{if} TC-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D\left[s\right[0],s[1\left]\right]$$\mathrm{or} s_{\mathit{coord}}=g_r:$ 6:             $\mathrm{break}$ 7:         $\mathbf{end} \mathbf{if}$ 8:     $\mathbf{end} \mathbf{while}$ $9: \mathbf{end} \mathbf{for}$ $10: \mathrm{collect} \mathrm{the} \mathrm{solution} \mathrm{path} {\pi }_{s_0\to g_r}$

Algorithm 4 describes the Endpoint DPP_Q method. It first initializes the problem according to Algorithm 1. Then, it sets the initial exploration start point of the observed as the real goal g_r, and initializes its values for the next two dimensions to 0 (line 2). Each training round includes checking the termination condition: whether the remaining time exceeds the shortest observed time to reach the start node s₀, indicating that the observed cannot reach the real goal within the time constraint $TC-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D_s\left[s\right[0],s[1\left]\right]$, or the current coordinate of the observed coincides with the coordinate of the target (the start node s₀) s_coord = s₀. After collecting the path (line 10), performing a reversal operation yields a solution for the DPP problem (line 11).

Algorithm 4 Endpoint DPP_Q

Algorithm 1 $1: \mathbf{for} \mathit{episode}\mathrm{in} \mathrm{Episodes} \mathbf{do}$ 2:     $\mathbf{Initialize} s=\left[g_r\right[0], g_r[1], 0, 0]$ 3:    $\mathbf{while} \mathrm{True}:$ 4:        Algorithm 2 5:         $\mathbf{if} TC-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D_s\left[s\right[0],s[1\left]\right]$ or scoord = s0: 6:            break 7:        end if 8:    end while 9: end for 10: $\mathrm{collect} \mathrm{the} \mathrm{solution} \mathrm{path} {\pi }_{g_r\to s_0}$ 11: $\mathrm{reverse}({\pi }_{g_r\to s_0}$)

Algorithm 5 describes the LDP DPP_Q method. It begins by initializing the problem according to Algorithm 1. Then, it computes the g_min to determine the coordinates of LDP, and calculatess the shortest cost distance from the LDP point to the false goal g_min: $opt(LDP, g_r)$ (line 1). The initial start point of the observed is set as LDP, with its values initialized to 0 for the next two dimensions (line 2). Subsequently, the algorithm divides into two steps that can be executed in parallel or sequentially: one agent starts from LDP to explore paths that can reach the real goal g_r within the time constraint $opt(LDP, g_r)$, while another agent starts from LDP to explore paths that can reach the start node s₀ within the time constraint $TC-opt(LDP, g_r)$. After collecting the paths, performing a reversal and concatenation operation yields a solution for the DPP problem starting from s₀ and ending at g_r (line 21).

Algorithm 5 LDP DPP_Q

Algorithm 1 $1: \mathrm{Find} g_{\mathit{min}} \mathrm{and} \mathit{LDP}, \mathrm{then} \mathrm{calculate} opt(LDP, g_r)$ $2: \mathbf{for} \mathit{episode}\mathrm{in} \mathrm{Episodes} \mathbf{do}$ 3:    $\mathbf{Initialize} s=\left[LDP\right[0], LDP[1], 0, 0]$ 4:    while True: 5:        Algorithm 2 $6: \mathbf{if} opt(LDP, g_r)-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D\left[s\right[0],s[1\left]\right] \mathrm{or} s_{\mathit{coord}}=g_r:$ 7:            break $8: \mathbf{end} \mathbf{if}$ $9: \mathbf{end} \mathbf{while}$ $10: \mathbf{end} \mathbf{for}$ $11: \mathrm{collect} \mathrm{the} \mathrm{solution} \mathrm{path} {\pi }_{LDP\to g_r}$ $12: \mathbf{for} \mathit{episode}\mathrm{in} \mathrm{Episodes} \mathbf{do}$ $13: \mathbf{Initialize} s=\left[LDP\right[0], LDP[1], 0, 0]$ $14: \mathbf{while} \mathrm{True}:$ 15:        Algorithm 2 $16: \mathbf{if} TC-opt(LDP, g_r)-\left(s\right[2]+\sqrt{2}\times s[3\left]\right)<D_s\left[s\right[0],s[1\left]\right]$ or scoord = s0: $17: \mathrm{break}$ $18: \mathbf{end} \mathbf{if}$ $19: \mathbf{end} \mathbf{while}$ $20: \mathrm{collect} \mathrm{the} \mathrm{solution} \mathrm{path} {\pi }_{LDP\to s_0}$ $21: \mathrm{reverse}({\pi }_{LDP\to s_0}$$)+{\pi }_{LDP\to g_r}$

5. Experiments and Results

We divided the experiments into three parts. Firstly, we randomly generated a total of 300 DPP problems based on 10 × 10 grid maps to verify the effectiveness comparison between ${\pi }_{d1~4}$ and $e\_{\pi }_{d1~4}$. Next, we also randomly generated a total of 300 DPP problems based on 10 × 10 grid maps to validate the effectiveness of DPP_Q, Endpoint DPP_Q, and LDP DPP_Q. Finally, we used large maps from Moving-AI to further verify the effectiveness of DPP_Q, Endpoint DPP_Q and LDP DPP_Q.

5.1. Performance Evaluation of $e\_{\pi }_{d1~4}$ (Compared with ${\pi }_{d1~4}$)

5.1.1. Experimental Design

Considering the need to collect sufficient experimental data to ensure the reliability of performance testing results, we investigated the scenarios with 1, 2, and 3 false goals. The experiments were conducted on 300 10 × 10 grid maps, each randomly populated with 4 to 9 obstacle grid cells. For the case with one false goal, we generated 100 maps where one start node was randomly placed in the lower-middle area, one real goalwas randomly located in the upper-left corner and one false goal was randomly positioned in the upper-right corner (as shown in Figure 4a). For the case with two false goals, another set of 100 maps was generated where one start node was randomly placed in the bottom-right corner, one real goal was randomly placed in the upper-left corner and two false goals were randomly placed in the upper-right and lower-left corners respectively (as shown in Figure 4b). For the scenario with three false goals, building upon the distribution seen in Figure 4b for two false goals, we randomly added a third false goal positioned in the middle area (as illustrated in Figure 4c). This experimental design emphasizes the unique characteristics of DPP problems when there is a certain distance between the start node, real goal, and false goals.

5.1.2. Experimental Results

As shown in Figure 5, we randomly select one map each for the experiments with 1, 2, and 3 false goals to demonstrate the results. Here, f denotes the number of false goals. In Figure 5, the black squares represent obstacles, the orange dot represents the start point, the blue dot represents the real goal, the teal dots denote the positions of false goals, the red arrows indicate the ${\pi }_{d1~4}$ path, and the green arrows represent the $e\_{\pi }_{d1~4}$ path.

Table 1. The five-number summary describes the improvements of ADI of paths generated by $e\_{\pi }_{d1~4}$ compared with ${\pi }_{d1~4}$, where $\mu =1$.

	Paths	Median /(10−2)	Q1 /(10−2)	Q3 /(10−2)	Average /(10−2)	Std /(10−2)	Improvements
f = 1	${\pi }_{d1}$	3.605	3.408	3.870	3.637	0.330	−0.16%
	$e\_{\pi }_{d1}$	3.620	3.460	3.803	3.631	0.284
	${\pi }_{d2}$	2.935	2.452	3.330	2.870	0.691	33.07%
	$e\_{\pi }_{d2}$	3.810	3.508	4.070	3.819	0.458
	${\pi }_{d3}$	3.315	2.915	3.793	3.356	0.678	14.00%
	$e\_{\pi }_{d3}$	3.830	3.508	4.062	3.826	0.455
	${\pi }_{d4}$	3.530	3.243	3.843	3.561	0.490	8.26%
	$e\_{\pi }_{d4}$	3.880	3.583	4.128	3.855	0.447
f = 2	${\pi }_{d1}$	3.210	2.980	3.470	3.203	0.341	0.00%
	$e\_{\pi }_{d1}$	3.210	2.980	3.470	3.203	0.340
	${\pi }_{d2}$	2.755	2.423	3.078	2.758	0.423	13.96%
	$e\_{\pi }_{d2}$	3.125	2.900	3.380	3.143	0.361
	${\pi }_{d3}$	2.755	2.423	3.078	2.758	0.423	13.96%
	$e\_{\pi }_{d3}$	3.125	2.900	3.380	3.143	0.361
	${\pi }_{d4}$	2.995	2.660	3.242	2.984	0.372	5.76%
	$e\_{\pi }_{d4}$	3.145	2.900	3.405	3.156	0.375
f = 3	${\pi }_{d1}$	3.350	2.912	3.770	3.346	0.598	0.06%
	$e\_{\pi }_{d1}$	3.340	2.895	3.738	3.344	0.600
	${\pi }_{d2}$	3.210	2.777	3.683	3.221	0.631	3.45%
	$e\_{\pi }_{d2}$	3.335	2.895	3.688	3.332	0.600
	${\pi }_{d3}$	3.210	2.777	3.683	3.221	0.631	3.45%
	$e\_{\pi }_{d3}$	3.335	2.895	3.688	3.332	0.600
	${\pi }_{d4}$	3.255	2.878	3.763	3.294	0.598	1.08%
	$e\_{\pi }_{d4}$	3.335	2.895	3.710	3.335	0.601

demonstrates a significant difference in the ADI of paths generated by ${\pi }_{d1~4}$ compared to $e\_{\pi }_{d1~4}$. The improvements of $e\_{\pi }_{d1~4}$ over traditional ${\pi }_{d1~4}$ are substantial. Experimentally, $e\_{\pi }_{d1}$ shows almost no improvement compared to ${\pi }_{d1}$ (−0.03%), while $e\_{\pi }_{d2}$ averages an improvement of 16.83% compared with ${\pi }_{d2}$, $e\_{\pi }_{d3}$ averages an improvement of 10.47% compared with ${\pi }_{d3}$, and $e\_{\pi }_{d4}$ averages an improvement of 5.03% compared with ${\pi }_{d4}$. Overall, $e\_{\pi }_{d1~4}$ shows an average improvement of 8.07% over ${\pi }_{d1~4}$.

For ${ \pi }_{d1}$ and $e\_{\pi }_{d1}$, their performances are nearly indistinguishable. However, for ${ \pi }_{d2~4}$ and ${ e\_\pi }_{d2~4}$, the improvements are quite significant. Of course, this also relates to the distribution of true and false goals. Although Table 1 suggests that the advantage of ${ e\_\pi }_{d1~4}$ is less pronounced when there are three false goals compared to 1 or 2; this may be due to the specific placement of the third false goal, which is close to both the start node and the real goal. If the third false target were also randomly placed in a corner position, the advantage of ${ e\_\pi }_{d1~4}$ would likely be more pronounced.

5.2. Performance Evaluation of Endpoint DPP_Q and LDP DPP_Q (Compared with DPP_Q)

In this section, we first conduct batch experiments on 10 × 10 maps to verify the advantages of Endpoint DPP_Q and LDP DPP_Q over the baseline DPP_Q. Subsequently, we perform further tests on 49 × 49 maps based on the Moving-AI benchmark.

5.2.1. Experimental Design

Considering the need for sufficient experimental data to ensure the reliability of performance testing for DPP_Q, Endpoint DPP_Q and LDP DPP_Q, we conducted experiments on 300 10 × 10 grid maps. Each map contained randomly generated obstacle grids (4 to 9) following the methodology in Section 5.1. We investigated scenarios with one or two false goals. For maps with one false goal, we randomly placed one start node in the lower-middle area, one real goal in the upper-left corner and one false goal in the upper-right corner (as in Figure 6a), across 100 maps. For scenarios with two false goals, firstly, regarding the symmetric distribution, we randomly placed one start node in the lower-right corner, one real goal in the upper-left corner and two false goals in the upper-right and lower-left corners respectively (Figure 6b). There were also 100 maps generated of this type. For the asymmetric distribution, the position of the real goal varied (Figure 6c), and 100 maps were generated. The * symbol indicates maps with special distributions of real and false goals. These experiments aimed to thoroughly evaluate how these configurations impact the performance of our methods under various conditions.

For the methods used here—time-constrained DPP_Q, Endpoint DPP_Q, and LDP DPP_Q—we aimed to make the experiments more realistic and feasible. For each set of experiments (f = 1, f = 2, and f = 2*), consisting of 100 maps, we employed the method ${\pi }_{d4}$ to generate 100 deceptive paths. We then selected the maximum time cost from these paths, rounded up to the nearest integer, to serve as the time constraints for our experiments. Specifically, for f = 1, the time constraint was set to 15 (derived from a rounded-up maximum of 14.242); for f = 2, the time constraint was set to 16 (rounded up from 15.414) and for f = 2*, the time constraint was set to 13 (rounded up from 12.242).

The choice of ${\pi }_{d4}$ was deliberate because it provides paths with moderate time consumption and generally higher deception levels on average, making it a notable method within traditional approaches. Of course, any other time constraints could be used as long as all path-planning problems under these constraints have feasible solutions.

5.2.2. Experimental Results

For illustration, we randomly selected four maps from each of the three types of DPP problems mentioned above. Figure 7a–d display the paths generated by DPP_Q, Endpoint DPP_Q, and LDP DPP_Q for four random maps from the f = 1 group. Figure 7e–h correspond to four random maps from the f = 2 group, and Figure 7i–l depict four random maps from the f = 2* group. In these figures, paths generated by DPP_Q are indicated by red arrows, paths by Endpoint DPP_Q are indicated by green arrows, and paths by LDP DPP_Q are indicated by magenta arrows, and the black squares represent obstacles, the orange dot represents the start point, the blue dot represents the real goal, the teal dots denote the positions of false goals. The term “cost” denotes the specific time constraint used for path planning, and “map” indicates the map number selected from the 100 maps available. There are notable differences in the paths generated by DPP_Q, Endpoint DPP_Q, and LDP DPP_Q.

From

Table 2. The five-number summary describes the improvements of ADI of paths generated by Endpoint DPP_Q and LDP DPP_Q, compared with DPP_Q, where $\mu =1$. ${\pi }_Q$ represents paths generated by DPP_Q, ${\pi }_{EQ}$ represents paths generated by Endpoint DPP_Q, and ${\pi }_{LQ}$ represents paths generated by LDP DPP_Q.

	Paths	Median /(10−2)	Q1 /(10−2)	Q3 /(10−2)	Average /(10−2)	Std /(10−2)	Improvements
f = 1	${\pi }_Q$	4.970	4.728	5.220	4.986	0.354	–
	πEQ	4.995	4.750	5.223	4.990	0.348	0.08%
	${\pi }_{LQ}$	5.050	4.758	5.230	5.021	0.319	0.70%
f = 2	${\pi }_Q$	4.130	3.778	4.402	4.096	0.416	–
	${\pi }_{EQ}$	4.130	3.760	4.405	4.061	0.472	−0.85%
	${\pi }_{LQ}$	4.145	3.728	4.380	4.060	0.436	−0.88%
f = 2*	${\pi }_Q$	5.225	4.758	5.725	5.230	0.692	–
	${\pi }_{EQ}$	5.385	4.935	5.755	5.372	0.676	2.72%
	${\pi }_{LQ}$	5.340	4.968	5.820	5.371	0.638	2.70%

, it can be observed that the differences between the new and old methods are not significant (less than 1%) when f = 1 and f = 2. However, when f = 2*, the relative effectiveness of Endpoint DPP_Q and LDP DPP_Q compared to DPP_Q becomes more pronounced (approximately 2.7%). These results are based on a 10 × 10 small-scale map.

Below, we conduct experiments on the classic 49 × 49 large maps from Moving-AI, specifically using the maps called “49_empty.map”, “49_small.map”, and “49_large.map”. The start point coordinates are set to (44, 3), with the real goal located at (10, 30). There are two false goals located at (5, 10) and (45, 45), respectively.

Figure 8 displays heatmaps of the exploration of each grid point after training for 10,000,000 iterations. The color bars on the right of each image represent logarithmically scaled values (base 10). The “cost” refers to the time constraints given to the observed, resulting in time costs of 59.28, 62.797, and 59.28 for the DPP problems solved using ${\pi }_{d4}$ on “49_empty.map”, “49_small.map”, and “49_large.map”, respectively. The orange squares (black borders) denote the start point, the blue squares (white borders) denote the real goal, and the teal squares (white borders) denote the locations of the false goals. In Figure 8c,f,i, the purple squares (white borders) indicate the coordinates of the LDP points corresponding to the respective DPP problems.

Figure 8a–c show the exploration patterns of the observed for DPP_Q, Endpoint DPP_Q, and LDP DPP_Q in the “49_empty.map” scenario. Figure 8d–f depict the exploration in the “49_small.map” scenario, while Figure 8g–i display the exploration in the “49_large.map” scenario. Figure 8b,e,h reveal that Endpoint DPP_Q effectively addresses the initial issue of DPP_Q, as shown in Figure 8a,d, and g, where it often gets stuck in local optima early on. Further analysis of Figure 8c,f,i shows that LDP DPP_Q not only resolves the initial local optima problem seen in Figure 8a,d,g but also reduces the exploration space intelligently, potentially speeding up the training process.

Figure 9a,c,e depict heatmaps of reward functions for the three DPP problems. The red, green, and magenta lines represent paths generated by DPP_Q, Endpoint DPP_Q, and LDP DPP_Q, respectively. Similar to Figure 8, the orange squares (black borders) denote the start point, blue squares (white borders) denote the real goal, and teal squares (white borders) denote the false goals. The purple squares (white borders) in Figure 9a,c,e represent the coordinates of LDP of the relative DPP problems.

In Figure 9b,d,f, the x-axis represents the progress along the path (ranging from 0 to 1), while the y-axis represents the posterior probability of the real goal. The red, green, and magenta lines illustrate how the posterior probability of the real goal changes in the path generated by DPP_Q, Endpoint DPP_Q, and LDP DPP_Q, respectively. It is observed that the red line tends to reach around 1.0 earlier than the green and magenta lines in Figure 9b. In Figure 9b, the green and magenta lines almost overlap (with ADD of 0.586 for DPP_Q, 0.703 for Endpoint DPP_Q, and 0.695 for LDP DPP_Q), while in Figure 9d, LDP DPP_Q notably outperforms Endpoint DPP_Q and DPP_Q (with ADD of 0.316 for DPP_Q, 0.423 for Endpoint DPP_Q, and 0.558 for LDP DPP_Q). Figure 9e shows even closer alignment between the green and magenta lines (mean deception scores of 0.530 for DPP_Q, 0.635 for Endpoint DPP_Q, and 0.635 for LDP DPP_Q), demonstrating that LDP DPP_Q effectively enhances ADD, similar to Endpoint DPP_Q. Given the same time constraints, using ADD as a metric provides a more intuitive comparison of the three path-planning strategies.

6. Discussion and Conclusions

In this paper, we introduce two metrics for measuring the solutions of DPP problems: ADD and ADI. Employing a reverse-thinking approach, we propose three new methods (${e\_\pi }_{d1~4}$, Endpoint DPP_Q and LDP DPP_Q) that demonstrate significant improvements compared to the original methods (${\pi }_{d1~4}$ and DPP_Q).

Firstly, we define the concept of ADD. Based on ADD, we further develop the notion of ADI and analyze its validity, applying it to evaluate subsequent methods. Secondly, we enhance ${\pi }_{d1~4}$ without time constraints by introducing ${e\_\pi }_{d1~4}$, which shows substantial improvements over traditional methods. Experimental results indicate negligible improvement for ${e\_\pi }_{d1}$ compared with ${\pi }_{d1}$ (−0.03%), a significant average improvement of 16.83% for ${e\_\pi }_{d2}$ compared with ${\pi }_{d2}$, a 10.47% average improvement for ${e\_\pi }_{d3}$ compared with ${\pi }_{d3}$, and a 5.03% average improvement for ${e\_\pi }_{d4}$ compared with ${\pi }_{d4}$. Overall, ${e\_\pi }_{d1~4}$ outperforms ${\pi }_{d1~4}$ by 8.07%. Finally, addressing methods under time constraints like DPP_Q, we propose Endpoint DPP_Q and LDP DPP_Q. Both methods effectively address the issue of poor path deception in DPP_Q when the real and false goals have specific distributions. Moreover, Endpoint DPP_Q and LDP DPP_Q demonstrate even more significant advantages in overcoming local optima issues on large maps compared to DPP_Q, resulting in substantial improvements.

For future work, we recognize that the training times of methods such as DPP_Q, Endpoint DPP_Q, and LDP DPP_Q are still lengthy. Inspired by the principles of ${\pi }_{d1~4}$, we suggest segmenting paths by incorporating more navigation points that are similar to LDP. Segmenting agent training could accelerate learning while achieving comparable results. Additionally, modeling the goal recognition method of the observer remains challenging. PGRM serves as an assumption model that is potentially inaccurate or flawed. Future research should introduce adversarial elements and more complex opponent goal recognition models. For example, the observed may quickly perceive the identifications or actions of the observer and adjust their planning accordingly to enhance deception strategies. Furthermore, expanding DPP problems to higher dimensions, such as three-dimensional space for drone flight or dynamic environments, promises practical advancements. Incorporating additional elements like images or audio captured by identifiers rather than solely relying on coordinates could make the game more intricate. These directions hold promise for future research, enhancing practical applicability significantly.