Towards Configuration Planning with Partially Ordered Preferences: Representation and Results

Abstract

Configuration planning for a distributed robotic system is the problem of how to configure the system over time in order to achieve some causal and/or information goals. A configuration plan specifies what components (sensor, actuator and computational devices), should be active at different times and how they should exchange information. However, not all plans that solve a given problem need to be equally good, and for that purpose it may be important to take preferences into account. In this paper we present an algorithm for configuration planning that incorporates general partially ordered preferences. The planner supports multiple preference categories, and hence it solves a multiple-objective optimization problem: for a given problem, it finds all possible valid, non-dominated configuration plans. The planner has been able to successfully cope with partial ordering relations between quantitative preferences in practically acceptable times, as shown in the empirical results. Preferences here are represented as c-semirings, and are used for establishing dominance of a solution over another in order to obtain a set of configuration plans that will constitute the solution of a configuration planning problem with partially ordered preferences. The dominance operators tested in this paper are Pareto and Lorenz dominance. Our solver considers one guiding heuristic for obtaining the first solution, and then switches to a dominance based monotonically decreasing heuristic used for pruning dominated partial configuration plans. In our empirical results, we perform a statistical study in the space of problem instances and establish families of problems for which our approach is computationally feasible.