Planejamento baseado em casos para pathfinding enganoso em terrenos com topografia

Abstract

Deceptive movement plans are fundamental for Agent-Based Simulation Systems (ABSS) that aim to realistically model and solve real-world adversarial problems. Different scenarios where opposing forces are modeled in ABSS require the planning of movement actions with deceptive aspects. In this case, simulated agents have the capabilities to compute and use paths that can deceive adversaries about their real objectives. However, constructing and evaluating deceptive plans is a complex activity for many users. Despite this issue, the Artificial Intelligence (AI) literature shows a lack of techniques that support the creation of reusable memories containing concrete experiences of deceptive movement planning. In this context, the objective of this work is to investigate the development of ABSS that allow users to specify and test deceptive movement plans in scenarios with topographic terrains. Based on Case-Based Reasoning (CBR) techniques adjusted for the problem-solving needs in this application domain, the work designs, implements, and tests the framework Case-Based Planning for Deceptive Pathfinding (CBPDP), which can retain, retrieve, and reuse deceptive movement plans for groups of agents. The work implements a software development API to support the construction of ABSS. By exploring a simulation system implemented to validate this API, the work addresses the challenge of planning deceptive routes in topographic terrains where path costs in the terrain relief and other factors of deceptive paths are analyzed. The work explores alternative deceptive strategies that are adjusted to analyze the topographic costs of the terrain, not only to determine how deceptive the terrain nodes computed by the pathfinding algorithms are but also to obtain deceptive paths with low costs. In addition to the A algorithm, the Theta algorithm is used in the search for smoother and more realistic deceptive routes, which can better model the routes used by real-world terrestrial agents. The work analyzes deceptive topographic paths calculated according to the notions of Last Deceptive Point (LDP) and Last Topographic Deceptive Point (LDPT ), which allow obtaining deceptive topographic paths computed in terrains with pronounced reliefs. Experimental results with the proposed methods are statistically analyzed according to different pathfinding algorithm analysis metrics, showing that the deceptive strategies computed with the use of the A algorithm return topographic paths with a higher number of deceptive nodes (higher deception density) in reduced execution times. Moreover, the computation strategies of deceptive paths computed with the support of the Theta algorithm and LDPT allow obtaining paths that present a relevant trade-off between the number of deceptive nodes and the quality of the topographic path. Experimental results supported by cross-validation techniques and new problem-solving tests demonstrate the effectiveness of the CBPDP framework in retrieving cases relevant to the deceptive movement problems presented to the system.