Deceptive Topographic Path Planning

  • Crhistopher Lenhard UFSM
  • Henrique L. Krever UFSM
  • Ricardo K. Schlsener UFSM
  • Rafael H. Bordini PUCRS
  • Luis A. L. Silva UFSM

Resumo


Deception is essential to model real-world agent behaviors in entertainment and serious games. This paper approaches the challenge of planning deceptive routes on topographic terrains where topographic path costs and other deceptive path factors are analyzed. The work explores alternative deceptive strategies tuned to explore the terrain costs to determine how deceptive the path search nodes are and to return paths with low topographic costs. In addition to the A* algorithm, the Theta* algorithm is explored in the search for smoother deceptive routes, which better represent routes used by terrestrial agents in real-world adversarial situations. It also analyzes deceptive topographic paths computed according to the Last Deceptive Point (LDP) and Last Topographic Deceptive Point (LDPT) notions, where examples of returned paths are presented with the help of terrain relief scenarios. Experimental results with the proposed methods are statistically analyzed according to various path search metrics, showing that all deceptive strategies with A* compute topographic paths with higher numbers of deceptive nodes on reduced execution times. Moreover, the strategies with Theta* and LDPT return paths that show a useful combination of topographic path quality and number of deceptive nodes.

Palavras-chave: Deception, Deceptive path planning strategies, Path planning, Topographic planning
Publicado
06/11/2023
LENHARD, Crhistopher; KREVER, Henrique L.; SCHLSENER, Ricardo K.; BORDINI, Rafael H.; SILVA, Luis A. L.. Deceptive Topographic Path Planning. In: SIMPÓSIO BRASILEIRO DE JOGOS E ENTRETENIMENTO DIGITAL (SBGAMES), 22. , 2023, Rio Grande/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 114-123.