Contextual Multi-Objective Path Planning

Many critical robot environments, such as healthcare and security, require robots to account for contextdependent criteria when performing their functions (e. g. , navigation). Such domains require decisions that balance multiple factors, making it difficult for robots to make contextually appropriate decisions. Multi-Objective Optimization (MOO) methods offer a potential solution by trading off between objectives; however concepts like Pareto fronts are not only expensive to compute but struggle with differentiating among solutions on the Pareto front. This work introduces the Contextual Multi-Objective Path Planning (CMOPP) algorithm, which enables the robot to trade off different complex costs dependent on context. The key insight of this work is to separate the path planning and path cost estimation into two independent steps, thus significantly reducing computation cost without impacting the quality of the resulting path. As a result, CMOPP is able to accurately model path costs, which provide meaningful trade-offs when choosing a path that best fits the context. We show the benefits of CMOPP on case studies that demonstrate its contextual path planning capabilities. CMOPP finds contextually appropriate paths by first reducing the search space up to 99. 9% to a near-optimal set of paths. This reduction enables the generation of accurate path cost models, using up to 90% less computation than similar methods.

Authors

• Anna Nickelson
• Kagan Tumer
• William D. Smart

Keywords

• Costs
• Navigation
• Computational modeling
• Estimation
• Medical services
• Path planning
• Security
• Multi-objective Path Planning
• Best Fit
• Search Space
• Multi-objective Optimization
• Pathfinding
• Cost Model
• Pareto Front
• Planning Algorithm
• Cost Of Accuracy
• Cost Path
• Multi-objective Optimization Method
• Alternative Methods
• Markov Chain Monte Carlo
• Weight Function
• Gaussian Mixture Model
• Global Plan
• Optimal Path
• Space In Order
• Reduced Search Space
• Robot Operating System
• Set Of Costs
• Dominant Point
• Expensive Cost
• Traditional Search