1. Introduction

No matter if we're dealing with probes sent to the distant surface of Mars to take pictures, or with the less peaceful Quake-bots programmed to take your virtual life in a computer-simulated arena, motion planning and pathfinding are crucial elements to these applications. It is easy to come up with a variety of other examples, some in present day and some in future technologies, where algorithms to automatically find a path, a roadmap or a sequence of movements an entity of some sort has to follow, play an important role.