
Research
Abstracts  2006 
Generalized Conflict Learning For Hybrid Logic/Linear Optimization Problems[1][2]Hui Li & Brian WilliamsIntroductionConflictdirected search algorithms have formed the core of practical, modelbased reasoning systems for the last three decades, including the analysis of electrical circuits, the diagnosis of thousandcomponent circuits, and the modelbased 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 modelbased 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 modelbased execution of continuous, nonholonomic systems, and demonstrates this capability for coordinated air vehicle search and rescue, using a realtime hardwareintheloop testbed. In this framework the air vehicle control trajectories are generated and updated in realtime, 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 conflictdirected A* algorithm [4]. We introduce an algorithm called Generalized ConflictDirected Branch and Bound (GCDBB) applied to the solution of DLPs. GCDBB extends traditional Branch and Bound (B&B), by first constructing a conflict from each search node that is found to be infeasible or suboptimal, and then by using these conflicts to guide the forward search away from known infeasible and suboptimal states. Disjunctive Linear ProgramsA 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.
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.
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 GCDBB algorithm, though introduced in the context of DLPs, can be generalized to other formulations. Our focus is on the generalization of forward conflictdirected search to these hybrid problems, not on the DLP encoding in particular. The GCDBB AlgorithmThe GCDBB 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 suboptimality; second, Forward ConflictDirected 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: Bestfirst Search (BFS) versus Depthfirst Search (DFS). Branch and Bound for DLPsGCDBB 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 suboptimal, 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 LearningIn 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 suboptimal. 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 suboptimality 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 suboptimality conflict is a set of active constraints of a suboptimal subproblem. An inequality constraint gi(x) ≤ 0 is active at a feasible point x* if gi(x*) = 0. An example of a suboptimality 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 suboptimality, 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 NPcomplete. Forward Conflictdirected SearchWe use forward conflictdirected 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 dependencydirected backtracking [10], backjumping [11], conflictdirected 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 conflictdirected 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 suboptimal. Our experimental results show that forward conflictdirected search significantly outperforms backtrack search with conflicts on a range of cooperative vehicle plan execution problems. Induced Unit Clause RelaxationRelaxation 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 nonunit 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 nonunit clauses through the continuous relaxation from binary to realvalued variables, in contrast to ignoring all the nonunit 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 nonunit 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: Bestfirst versus DepthfirstGiven a fixed set of heuristic information, [14] shows that bestfirst 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 conflictdirected 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 GCDBB is that the concept of suboptimality 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. ConclusionThis paper presented a novel algorithm, Generalized ConflictDirected Branch and Bound, that efficiently solves DLP problems through a powerful threefold method, featuring generalized conflict learning, forward conflictdirected search and induced unit clause relaxation. The key feature of the approach reasons about infeasible or suboptimal 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 modelbased temporal plan execution for cooperative vehicles demonstrated an order of magnitude speedup over BIPBB. 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 351, 1979. [4] Williams, B. and Ragno, R., Conflictdirected A* and its Role in Modelbased Embedded Systems. J. of Discrete Applied Math. 2005. [5] T. Schouwenaars, B. De Moor, E. Feron, J. How.,T Mixed integer programming for multivehicle 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 9697 395442, 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 dependencydirected backtracking in a system for computeraided circuit analysis, Artificial Intelligence 9 135–196, 1977. [11] J. Gaschnig Experimental Case Studies of Backtrack vs. Waltztype vs. New Algorithms for Satisficing Assignment Problems. The 2nd Canadian Conference on AI 268277, 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 Bestfirst Search Strategies and the Optimality of A*. J. of ACM. 32 506536, 1985. [15] Léauté, T. and Williams, B., Coordinating Agile Systems Through The Modelbased Execution of Temporal Plans. in Proceedings of AAAI. 2005. 

