Hardness measures for gridworld benchmarks and performance analysis of real-time heuristic search algorithms

被引:0
|
作者
Masataka Mizusawa
Masahito Kurihara
机构
[1] Hokkaido University,Graduate School of Information Science and Technology
来源
Journal of Heuristics | 2010年 / 16卷
关键词
Real-time search; Gridworlds; Benchmark; Phase transition;
D O I
暂无
中图分类号
学科分类号
摘要
Gridworlds are one of the most popular settings used in benchmark problems for real-time heuristic search algorithms. However, no comprehensive studies have been published so far on how the difference in the density of randomly positioned obstacles affects the hardness of the problems. This paper presents two measures for characterizing the hardness of gridworld problems parameterized by obstacle ratio, and relates them to the performance of the algorithms. We empirically show that the peak locations of those measures and actual performance degradation of the basic algorithms (RTA* and LRTA*) almost coincide with each other for a wide variety of problem settings. Thus the measures uncover some interesting aspects of the gridworlds.
引用
收藏
页码:23 / 36
页数:13
相关论文
共 50 条
  • [41] Real-time performance measures of perceptual audio coding
    Pasero, E
    Montuori, A
    ITRE 2004: 2ND INTERNATIONAL CONFERENCE INFORMATION TECHNOLOGY: RESEARCH AND EDUCATION, PROCEEDINGS, 2004, : 213 - 217
  • [42] A dynamic model and parallel tabu search heuristic for real-time ambulance relocation
    Gendreau, M
    Laporte, G
    Semet, F
    PARALLEL COMPUTING, 2001, 27 (12) : 1641 - 1653
  • [43] Real-time performance of dynamic memory allocation algorithms
    Puaut, I
    EUROMICRO RTS 2002: 14TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2002, : 41 - 49
  • [44] Performance Evaluation of Real-Time Multiprocessor Scheduling Algorithms
    Alhussian, Hitham
    Zakaria, Nordin
    Abdulkadir, Said Jadid
    Fageeri, Sallani Osman
    2016 3RD INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCES (ICCOINS), 2016, : 310 - 315
  • [45] Real-Time Energy Management for a Hybrid Electric Vehicle Based on Heuristic Search
    Yang, Ningkang
    Han, Lijin
    Xiang, Changle
    Liu, Hui
    Ma, Tian
    Ruan, Shumin
    IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 2022, 71 (12) : 12635 - 12647
  • [46] Challenge Benchmarks for Verification of Real-time Programs
    Kalibera, Tomas
    Parizek, Pavel
    Haddad, Ghaith
    Leavens, Gary T.
    Vitek, Jan
    PLPV'10: PROCEEDINGS OF THE 2010 ACM SIGPLAN WORKSHOP ON PROGRAMMING LANGUAGES MEETS PROGRAM VERIFICATION, 2010, : 57 - 62
  • [47] Performance Evaluation of Real-Time Object Detection Algorithms
    Srisuk, Sanun
    Suwannapong, Chanwit
    Kitisriworapan, Songrit
    Kaewsong, Apiwut
    Ongkittikul, Surachai
    2019 7TH INTERNATIONAL ELECTRICAL ENGINEERING CONGRESS (IEECON 2019), 2019,
  • [48] Improving heuristic function of cost-based abduction system using real-time heuristic search
    Koshino, Makoto
    Okamine, Tadashi
    Kimura, Haruhiko
    Hirose, Sadaki
    Systems and Computers in Japan, 2004, 35 (06) : 89 - 97
  • [49] A family of real-time Java']Java benchmarks
    Kalibera, Tomas
    Hagelberg, Jeff
    Maj, Petr
    Pizlo, Filip
    Titzer, Ben
    Vitek, Jan
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2011, 23 (14): : 1679 - 1700
  • [50] On real-time algorithms for the location search of discontinuous conductivities with one measurement
    Hanke, Martin
    INVERSE PROBLEMS, 2008, 24 (04)