A comparative study of sensor-based path-planning algorithms in an unknown maze

Abstract

In general, an unknown maze has few collision-free paths to a destination. Therefore, a robot supervised by the classic sensor-based path-planning algorithms Bug2, Class1, Alg1, Alg2 repeatedly enters into long local and global loops excluding and including a destination (goes out of its true way), respectively. For example, in Alg1 and Alg2, we can point out a case that a robot always enters into a global loop one time, and also in Bug(alter.) and Class1(alter.), we can find another case that a robot frequently joins a local loop many times. A complicated maze usually includes such cases, and therefore a robot arrives at a destination via a very long collision-free path. To overcome this, we revisit an algorithm, HD-I, whose following direction is adequately changed by trial and error. In HD-I, a robot hardly selects an inadequate direction and consequently decreases a probability to enter into global and local loops.