Technical Report CIS9907

Title: Applications of Macro Learning to Path Planning
Authors: Shaul Markovitch
Abstract: Many robotics motion-planning techniques use common heuristic graph search algorithms for finding a path from the current state to the goal state. The research described here studies the application of macro-operators learning to the domain of map-driven robot navigation for reducing the search cost. We assume that a robot is placed in an environment where it has to move between various locations (for example, an office-like environment) where it is given tasks of delivering items between offices. We assume that a navigation task consists of a search for a path and movement along the found path. The robot is given a map of the environment ahead of time and has computation resources available. We suggest using this computation time for macro-learning. Macro-learning is a technique for speeding up the search process. Applying macro-learning for navigation brings interesting research problems. Using macros has positive effect on the search cost but negative effect on the solution quality (and therefore the movement cost). The paper describes an extensive set of experiments that study the tradeoff between these two effects and test their combined effect on the total navigation cost.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion