Escaping depressions in LRTS based on incremental refinement of encoded quad-trees

DOI10.1155/2017/1850678MaRDI QIDQ1992415zbMATH OpenOpenAlexWikidataFDO

Authors Yue Hu, Long Qin, Quanjun Yin, Lin Sun

Publication date 5 November 2018

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2017/1850678

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Artificial intelligence for robotics (68T40)

Review text

Summary: In the context of robot navigation, game AI, and so on, real-time search is extensively used to undertake motion planning. Though it satisfies the requirement of quick response to users' commands and environmental changes, learning real-time search (LRTS) suffers from the heuristic depressions where agents behave irrationally. There have introduced several effective solutions, such as state abstractions. This paper combines LRTS and encoded quad-tree abstraction which represent the search space in multiresolutions. When exploring the environments, agents are enabled to locally repair the quad-tree models and incrementally refine the spatial cognition. By virtue of the idea of state aggregation and heuristic generalization, our EQ LRTS (encoded quad-tree based LRTS) possesses the ability of quickly escaping from heuristic depressions with less state revisitations. Experiments and analysis show that (a) our encoding principle for quad-trees is a much more memory-efficient method than other data structures expressing quad-trees, (b) EQ LRTS differs a lot in several characteristics from classical PR LRTS which represent the space and refine the paths hierarchically, and (c) EQ LRTS substantially reduces the planning amount and curtails heuristic updates compared with LRTS on uniform cells.

Recommendations

• Avoiding and escaping depressions in real-time heuristic search
• Graph abstraction in real-time heuristic search
• Learning in real-time search: a unifying framework
• Minimax real-time heuristic search
• Controlling the learning process of real-time heuristic search

Cites work

• Avoiding and escaping depressions in real-time heuristic search
• Case-based subgoaling in real-time heuristic search for video game pathfinding
• Controlling the learning process of real-time heuristic search
• Dynamic control in real-time heuristic search
• Graph abstraction in real-time heuristic search
• Incremental construction of generalized Voronoi diagrams on pointerless quadtrees
• Learning in real-time search: a unifying framework
• Real-time heuristic search

Cited in

(1)

• Avoiding and escaping depressions in real-time heuristic search

This page was built for publication: Escaping depressions in LRTS based on incremental refinement of encoded quad-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1992415)