GRASP Special Seminar: Stephen L. Smith, University of Waterloo, “Balancing Expressivity and Efficiency in Robot Path Planning Languages”

Abstract: Robot path planners consist of a language for specifying tasks, and a solver for generating paths. There is generally a tradeoff between the expressivity of the language and efficiency of the solver. On one hand, specialized and fast planners have been developed for specific tasks including point-to-point motion and simple combinatorial tasks. On the other hand, multi-purpose planners based on linear temporal logics (LTL) can handle a wide range of robot tasks. This expressivity, however, comes at a cost, and these planners often struggle to solve large-scale problems.  This talk will present a new language for path planning problems called SAT-TSP, which seeks to strike a balance between expressivity and efficiency. The language, while not as expressive as LTL, allows a user to naturally express many motion planning problems for single and multiple robots.  The talk will summarize solver approaches for problems in this language and give a performance comparison. Several solvers show a link to the Generalized Traveling Salesman Problem (GTSP) and recent work on developing GTSP solvers will also be discussed.