Research Abstracts - 2006

Generalized Conflict Learning For Hybrid Logic/Linear Optimization Problems[1][2]

Hui Li & Brian Williams

Introduction

Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades, including the analysis of electrical circuits, the diagnosis of thousand-component circuits, and the model-based autonomous control of a deep space probe. A conflict, also called nogood, is a partial assignment to a problem's state variables, representing sets of search states that are discovered to be infeasible, in the process of testing candidate solutions.

In the arena of model-based autonomy, there are not only purely discrete systems, but a large number of more agile systems, such as rovers, airplanes and legged robots. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear as well as logical constraints. In particular, [15] introduces an approach for model-based execution of continuous, non-holonomic systems, and demonstrates this capability for coordinated air vehicle search and rescue, using a real-time hardware-in-the-loop testbed.

In this framework the air vehicle control trajectories are generated and updated in real-time, by encoding the plan's logical constraints and the vehicle's continuous dynamics as a disjunctive linear program (DLP). A DLP [3] generalizes the constraints in linear programs (LPs) to clauses comprised of disjunctions of linear inequalities. Under the DLP formulation, we explore the development of algorithms for solving hybrid logic/linear optimization problems (HLLOPs) that use conflicts in the forward search direction, similar to the conflict-directed A* algorithm [4].

We introduce an algorithm called Generalized Conflict-Directed Branch and Bound (GCD-BB) applied to the solution of DLPs. GCD-BB extends traditional Branch and Bound (B&B), by first constructing a conflict from each search node that is found to be infeasible or sub-optimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states.

Disjunctive Linear Programs

A DLP is defined in Eq.1, where x is a vector of decision variables, f(x) is a linear cost function, and the constraints are a conjunction of n clauses, each of which (clause i) is a disjunction of mi linear inequalities, Cij(x) ≤ 0.

Eq.1

For example, in Fig.1 a vehicle has to go from point A to C, without hitting the obstacle B, while minimizing fuel use. Its DLP formulation is Eq.2.

Fig.1. A simple example of a hybrid logic/linear optimization problem

Eq.2

Here V denotes logical or, and x is a vector of decision variables that includes, at each time step t (=1,...,n), the position, velocity and acceleration of the vehicle. f(x) is a linear cost function in terms of fuel use, and g(x) ≤ 0 is a conjunction of linear inequalities on vehicle dynamics, and the last constraint keeps the vehicle outside obstacle B, at each time step t.

Note that HLLOPs can also be formulated in other ways: BIPs [5,6,7], MLLPs [8] and LCNF [9]. Our GCD-BB algorithm, though introduced in the context of DLPs, can be generalized to other formulations. Our focus is on the generalization of forward conflict-directed search to these hybrid problems, not on the DLP encoding in particular.

The GCD-BB Algorithm

The GCD-BB algorithm builds upon B&B and incorporates three key innovative features: first, Generalized Conflict Learning learns conflicts comprised of constraint sets that produce either infeasibility or sub-optimality; second, Forward Conflict-Directed Search guides the forward step of the search away from regions of state space corresponding to known conflicts; and third, Induced Unit Clause Relaxation uses unit propagation to form a relaxed problem and reduce the size of its unassigned problem. In addition, we compare different search orders: Best-first Search (BFS) versus Depth-first Search (DFS).

Branch and Bound for DLPs

GCD-BB builds upon B&B, which is frequently used by BIPs and MIPs, to solve problems involving both discrete and continuous variables. Instead of exploring the entire feasible set of a constrained problem, B&B uses bounds on the optimal cost, in order to avoid exploring subsets of the feasible set that it can prove are sub-optimal, that is, subsets whose optimal solution is not better than the incumbent, which is the best solution found so far.

At each node in the search tree, the selected unit clause set and the objective function form the relaxed LP to be solved. While the search tree of B&B for BIPs branches by assigning values to the binary variables, B&B for DLPs branches by splitting clauses; that is, a tree node is expanded by selecting one of the DLP clauses, and then selecting one of the clauses' disjuncts for each of the child nodes.

Generalized Conflict Learning

In the B&B search structure for DLPs, we exploit the opportunities for learning and pruning by introducing the concept of generalized conflict learning, which extracts a description from each fathomed subproblem that is infeasible or sub-optimal. This avoids exploring subproblems with the same description in the future.

A conflict is defined to be one of two types: an infeasibility conflict, or a sub-optimality conflict. An infeasibility conflict is a set of inconsistent constraints of an infeasible subproblem. An example is the constraint set {a,b,c,d} in Fig.2a. A sub-optimality conflict is a set of active constraints of a sub-optimal subproblem. An inequality constraint gi(x) ≤ 0 is active at a feasible point x* if gi(x*) = 0. An example of a sub-optimality conflict is the constraint set {a,b,d} in Fig.2b.

Fig.2. Examples of conflicts

A conflict is minimal if none of its proper subsets is a conflict. For example, the constraint set {a,c,d} in Fig.2a is a minimal conflict, as it is an inconsistent constraint set and every proper subset of it is consistent. Constraint set {a,d} in Fig.2b is also a minimal conflict. Note that there can be more than one minimal conflict (possibly with different cardinalities) involved in one infeasibility or sub-optimality, and a minimal conflict is not guaranteed to have the minimum cardinality. We extract minimal conflicts instead of any conflicts, since minimal conflicts can prune larger portion of the state space. However, we do not try to extract the minimum conflict of a subproblem, because it is NP-complete.

Forward Conflict-directed Search

We use forward conflict-directed search to guide the forward step of search away from regions of the feasible space that are ruled out by known conflicts. Backward search methods also use conflicts to direct search, such as dependency-directed backtracking [10], backjumping [11], conflict-directed backjumping [12], dynamic backtracking [13] and LPSAT [9]. These backtrack search methods use conflicts both to select backtrack points and as a cache to prune nodes without testing consistency. In contrast, methods like conflict-directed A* [4] use conflicts in forward search, to move away from known “bad” states. Thus not only one conflict is used to prune multiple subtrees, but also several conflicts can be combined as one compact description to prune multiple subtrees. We generalize this idea to guiding B&B away from regions of state space that the known conflicts indicate as infeasible or sub-optimal. Our experimental results show that forward conflict-directed search significantly outperforms backtrack search with conflicts on a range of cooperative vehicle plan execution problems.

Induced Unit Clause Relaxation

Relaxation is an essential tool for quickly characterizing a problem when the original problem is hard to solve directly; it provides bounds on feasibility and the optimal value of a problem, which are commonly used to prune the search space. Previous research typically solves DLPs by reformulating them as BIPs, where a relaxed LP is formed by relaxing the binary constraint (x = 0 or 1) to the continuous linear constraint (0 ≤ x ≤ 1).

An alternative way of creating a relaxed LP is to operate on the DLP encoding directly, by removing all non-unit clauses from the DLP. Prior work argues for the reformulation of DLP as BIP relaxation, with the rationale that it maintains some of the constraints of the non-unit clauses through the continuous relaxation from binary to real-valued variables, in contrast to ignoring all the non-unit clauses. However, this benefit is at the cost of adding binary variables and constraints, which increases the dimensionality of the search problem.

Our approach starts with the direct DLP relaxation. We overcome the weakness of standard DLP relaxation (loss of non-unit clauses) by adding to the relaxation unit clauses that are logically entailed by the original DLP. In the experiment section we compare our induced unit clause relaxation with the BIP relaxation and show a profound improvement on a range of cooperative vehicle plan execution problems.

Search Order: Best-first versus Depth-first

Given a fixed set of heuristic information, [14] shows that best-first search is the most efficient algorithm in terms of time efficiency. Intuitively, this is because BFS does not visit any node whose heuristic value is worse than the optimum, and all nodes better than the optimum must be visited to ensure that the optimum is not missed. However, BFS can take dramatically more memory space than DFS. Nevertheless, with conflict learning and forward conflict-directed search, the queue of the BFS search tree can be significantly reduced. Our experimental results show that on a range of test problems BFS can take memory space similar to DFS, while taking significantly less time to find the optimum.

An additional issue for GCD-BB is that the concept of sub-optimality is rooted in maintaining an incumbent. Hence, it can be applied to DFS but not to BFS. To evaluate these tradeoffs, our experiments in the next section compare the use of BFS and conflict learning from infeasibility only, with DFS and conflict learning from both infeasibility and from suboptimality.

Conclusion

This paper presented a novel algorithm, Generalized Conflict-Directed Branch and Bound, that efficiently solves DLP problems through a powerful three-fold method, featuring generalized conflict learning, forward conflict-directed search and induced unit clause relaxation. The key feature of the approach reasons about infeasible or sub-optimal subsets of state space using conflicts, in order to guide the forward step of search, by moving away from regions of state space corresponding to known conflicts. Our experiments on model-based temporal plan execution for cooperative vehicles demonstrated an order of magnitude speed-up over BIP-BB.

References:

[1] H. Li and B. Williams, Generalized Conflict Learning For Hybrid Discrete Linear Optimization, in Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP), 2005.

[2] H. Li, Generalized Conflict Learning for Hybrid Discrete Linear Optimization. Master's Thesis, M.I.T. 2005.

[3] E. Balas. Disjunctive programming, Annals of Discrete Mathematics 5 3-51, 1979.

[4] Williams, B. and Ragno, R., Conflict-directed A* and its Role in Model-based Embedded Systems. J. of Discrete Applied Math. 2005.

[5] T. Schouwenaars, B. De Moor, E. Feron, J. How.,T Mixed integer programming for multi-vehicle path planning. European Control Conference, 2001.

[6] T. Vossen, M. Ball, A. Lotem, D. Nau. On the use of integer programming models in AI planning. IJCAI, 1999.

[7] Kautz, H. and Walser, J.P., State space planning by integer optimization. in Proceedings of AAAI. 1999.

[8] J.N.Hooker and M.A.Osorio. Mixed Logical/Linear Programming. Discrete Applied Mathematics 96-97 395-442, 1999.

[9] Wolfman and D. Weld. The LPSAT engine & its application to resource planning. IJCAI, 1999.

[10] R. Stallman and G. J. Sussman. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial Intelligence 9 135–196, 1977.

[11] J. Gaschnig Experimental Case Studies of Backtrack vs. Waltz-type vs. New Algorithms for Satisficing Assignment Problems. The 2nd Canadian Conference on AI 268-277, 1978.

[12] P. Prosser. Hybrid algorithms for the constraint satisfaction problem, Computational Intelligence 3, 268–299, 1993.

[13] M. Ginsberg, Dynamic backtracking, Journal of Artificial Intelligence Research 1 25–46, 1993.

[14] Dechter, R. and Pearl, J., Generalized Best-first Search Strategies and the Optimality of A*. J. of ACM. 32 506-536, 1985.

[15] Léauté, T. and Williams, B., Coordinating Agile Systems Through The Model-based Execution of Temporal Plans. in Proceedings of AAAI. 2005.