Abstract

This paper presents Multi-State Real-Time Bidirectional Search, a method that improves the efficiency of the heuristic search algorithm for finding approximate solutions. Real-Time A* is a representative heuristic search algorithm for finding approximate solutions. The Multi-State Commitment method was introduced into RTA* and dramatically improved the performance in problems such as the N-puzzle. As well, Real-Time Bidirectional Search also improved RTA* by changing a unidirectional search into a bidirectional one. This paper proposed a method that introduces MSC into RTBS. The experimental results showed that compared with RTBS and MSC our proposed method, MSRTBS, improved executed time and solution quality in the N-Puzzle.