Minh B. Do

IJCAI Conference 2009 Conference Paper

• Tuan A. Nguyen
• Minh B. Do
• Subbarao Kambhampati
• Biplav Srivastava

In many real-world planning scenarios, the users are interested in optimizing multiple objectives (such as makespan and execution cost), but are unable to express their exact tradeoff between those objectives. When a planner encounters such partial preference models, rather than look for a single optimal plan, it needs to present the pareto set of plans and let the user choose from them. This idea of presenting the full pareto set is fraught with both computational and user-interface challenges. To make it practical, we propose the approach of finding a representative subset of the pareto set. We measure the quality of this representative set using the Integrated Convex Preference (ICP) model, originally developed in the OR community. We implement several heuristic approaches based on the Metric- LPG planner to find a good solution set according to this measure. We present empirical results demonstrating the promise of our approach.

AAAI Conference 2008 Conference Paper

On-line Planning and Scheduling: An Application to Controlling Modular Printers

• Minh B. Do

This paper summarizes recent work reported at ICAPS on applying artificial intelligence techniques to the control of production printing equipment. Like many other real-world applications, such as mobile robotics, this complex domain requires real-time autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. At the heart of our system is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. For example, our planning-graph-based planning heuristic takes resource contention into account when estimating makespan remaining. We suggest that this general architecture may prove useful as more intelligent systems operate in continual, online settings. Our system has enabled a new product architecture for our industrial partner and has been used to drive several commercial prototypes. When compared with stateof-the-art off-line planners, our system is hundreds of times faster and often finds better plans.

IJCAI Conference 2007 Conference Paper

• Wheeler Ruml
• Minh B. Do

In many shortest-path problems of practical interest, insufficient time is available to find a provably optimal solution. One can only hope to achieve a balance between search time and solution cost that respects the user's preferences, expressed as a utility function over time and cost. Current state-of-the-art approaches to this problem rely on anytime algorithms such as Anytime A* or ARA*. These algorithms require the use of extensive training data to compute a termination policy that respects the user's utility function. We propose a more direct approach, called Bugsy, that incorporates the utility function directly into the search, obviating the need for a separate termination policy. Experiments in several challenging problem domains, including sequence alignment and temporal planning, demonstrate that this direct approach can surpass anytime algorithms without requiring expensive performance profiling.

IJCAI Conference 2005 Conference Paper

Over-Subscription Planning with Numeric Goals

• J. Benton
• Minh B. Do
• Subbarao

By relaxing the hard-goal constraints from classical planning and associating them with reward values, over-subscription planning allows users to concentrate on presenting what they want and leaves the task of deciding the best goals to achieve to the planner. In this paper, we extend the over-subscription planning problem and its limited goal specification to allow numeric goals with continuous utility values and goals with mixed hard and soft constraints. Together they considerably extend the modeling power of goal specification and allow the user to express goal constraints that were not possible before. To handle these new goal constraints, we extend the Sapaps planner’s planning graph based techniques to help it choose the best beneficial subset of goals that can include both hard or soft logical and numeric goals. We also provide empirical results in several benchmark domains to demonstrate that our technique helps return quality plans.

AAAI Conference 2004 Conference Paper

Effective Approaches for Partial Satisfaction (Over-Subscription) Planning

• Menkes van den Briel
• Minh B. Do

In many real world planning scenarios, agents often do not have enough resources to achieve all of their goals. Consequently, they are forced to find plans that satisfy only a subset of the goals. Solving such partial satisfaction planning (PSP) problems poses several challenges, including an increased emphasis on modeling and handling plan quality (in terms of action costs and goal utilities). Despite the ubiquity of such PSP problems, very little attention has been paid to them in the planning community. In this paper, we start by describing a spectrum of PSP problems and focus on one of the more general PSP problems, termed PSP NET BEN- EFIT. We develop three techniques, (i) one based on integer programming, called OptiPlan, (ii) the second based on regression planning with reachability heuristics, called AltAltps, and (iii) the third based on anytime heuristic search for a forward state-space heuristic planner, called Sapaps. Our empirical studies with these planners show that the heuristic planners generate plans that are comparable to the quality of plans generated by OptiPlan, while incurring only a small fraction of the cost.

AIJ Journal 2001 Journal Article

Planning the project management way: Efficient planning by effective integration of causal and resource reasoning in RealPlan

• Biplav Srivastava
• Subbarao Kambhampati
• Minh B. Do

In most real-world reasoning problems, planning and scheduling phases are loosely coupled. For example, in project planning, the user comes up with a task list and schedules it with a scheduling tool like Microsoft Project. One can view automated planning in a similar way in which there is an action selection phase where actions are selected and ordered to reach the desired goals, and a resource allocation phase where enough resources are assigned to ensure the successful execution of the chosen actions. On the other hand, most existing automated planners studied in Artificial Intelligence do not exploit this loose-coupling and perform both action selection and resource assignment employing the same algorithm. The current work shows that the above strategy severely curtails the scale-up potential of existing state of the art planners which can be overcome by leveraging the loose coupling. Specifically, a novel planning framework called RealPlan is developed in which resource allocation is de-coupled from planning and is handled in a separate scheduling phase. The scheduling problem with discrete resources is represented as a Constraint Satisfaction Problem (CSP) problem, and the planner and scheduler interact either in a master-slave manner or in a peer-peer relationship. In the former, the scheduler simply tries to assign resources to the abstract causal plan passed to it by the planner and returns success. In the latter, a more sophisticated “multi-module dependency directed backtracking” approach is used where the failure explanation in the scheduler is translated back to the planner and serves as a nogood to direct planner search. RealPlan not only preserves both the correctness as well as the quality (measured in length) of the plan but also improves efficiency. Moreover, the failure-driven learning of constraints can serve as an elegant and effective approach for integrating planning and scheduling systems. Beyond the context of planner efficiency, the current work can be viewed as an important step towards merging planning with real-world problem solving where plan failure during execution can be resolved by undertaking only necessary resource re-allocation and not complete re-planning.