Home | Publications | CS Home

Applications of Macro Learning to Path Planning

---

Shaul Markovitch. Applications of Macro Learning to Path Planning. Technical report CIS9907, Technion, 1999.

---

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.

---

Keywords: Speedup Learning, Macro Learning

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @techreport{Markovitch:1999:AML,
  Author = {Shaul Markovitch},
  Title = {Applications of Macro Learning to Path Planning},
  Year = {1999},
  Number = {CIS9907},
  Type = {Technical report},
  Institution = {Technion},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-CIS9907.pdf},
  Keywords = {Speedup Learning, Macro Learning},
  Secondary-keywords = {Path Planning, Deductive Learning},
  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.
  }

  }