  We propose a novel method for multi-objective motion planning problems by
leveraging the paradigm of lexicographic optimization and applying it for the
first time to graph search over probabilistic roadmaps. The competing resources
of interest are penalized hierarchically during the search. Higher-ranked
resources cause a robot to incur non-negative costs over the paths traveled,
which are occasionally zero-valued. This is intended to capture problems in
which a robot must manage resources such as visibility of threats, availability
of communications, and access to valuable measurements. This leaves freedom for
tie-breaking with respect to lower-priority resources; at the bottom of the
hierarchy is a strictly positive quantity consumed by the robot, such as
distance traveled, energy expended or time elapsed. We compare our method with
two other multi-objective approaches, a naive weighted sum method and an
expanded graph search method, demonstrating that a lexicographic search can
solve such planning problems efficiently without a need for parameter-tuning in
unintuitive units. The proposed method is also demonstrated on hardware using a
laser-equipped ground robot.
