A Study on the Real - time Search Algorithm based on Dynamic Time Control


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 4, No. 10, pp. 2470-2476, Oct. 1997
10.3745/KIPSTE.1997.4.10.2470,   PDF Download:

Abstract

We propose a new real-time search algorithm and provide experimental evaluation and comparison of the new algorithm with mini-min lookahead algorithm. Many other real-time heuristic-search approached often divide the problem space to several sub-problems. In this paper, the proposed algorithm guarantees not only the sub-problem deadline but also total deadline. Several heuristic real-time search algorithms such as RTA*, SARTS and DYNORA have been proposed. The performance of such algorithms depend on the quality of their heuristic functions, because such algorithms estimate the search time based on the heuristic function. In real-world problem, however, we often fail to get an effective heuristic function beforehand. Therefore, we propose a new real-time algorithm that determines the sub-problem deadline based on the status of search space during sub-problem search process. That uses the cut-off method that is a dynamic stopping-criterion-strategy to search the sub-problem.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
A. J. Il and C. T. Choong, "A Study on the Real - time Search Algorithm based on Dynamic Time Control," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 4, no. 10, pp. 2470-2476, 1997. DOI: 10.3745/KIPSTE.1997.4.10.2470.

[ACM Style]
Ahn Jong Il and Chung Tae Choong. 1997. A Study on the Real - time Search Algorithm based on Dynamic Time Control. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 4, 10, (1997), 2470-2476. DOI: 10.3745/KIPSTE.1997.4.10.2470.