Efficiently Exploring Ordering Problems through Conflict-directed Search
In planning and scheduling, solving problems with both state and temporal constraints is hard since these constraints may be highly coupled. Judicious orderings of events enable solvers to efficiently make decisions over sequences of actions to satisfy complex hybrid specifications. The ordering problem is thus fundamental to planning. Promising recent works have explored the ordering problem as search, incorporating a special tree structure for efficiency. However, such approaches only reason over partial order specifications. Having observed that an ordering is inconsistent with respect to underlying constraints, prior works do not exploit the tree structure to efficiently generate orderings that resolve the inconsistency. In this paper, we present Conflict-directed Incremental Total Ordering (CDITO), a conflict-directed search method to incrementally and systematically generate event total orders given ordering relations and conflicts returned by sub-solvers. Due to its ability to reason over conflicts, CDITO is much more efficient than Incremental Total Ordering. We demonstrate this by benchmarking on temporal network configuration problems that involve routing network flows and allocating bandwidth resources over time.
Code (0)
등록된 구현이 없습니다.
Tasks
BenchmarkingSchedulingSimilar Papers 제목 키워드 기반
Generalized Conflict-directed Search for Optimal Ordering Problems
Solving planning and scheduling problems for multiple tasks with highly coupled state and temporal constraints is notoriously challenging. An appealing approach to effectively decouple the problem is to judiciously order…
BenchmarkingSchedulingVector Optimization with Gaussian Process Bandits
Learning problems in which multiple conflicting objectives must be considered simultaneously often arise in various fields, including engineering, drug design, and environmental management. Traditional methods for dealin…
Drug DesignLearning to Rank the Initial Branching Order of SAT Solvers
Finding good branching orders is key to solving SAT problems efficiently, but finding such branching orders is a difficult problem. Using a learning based approach to predict a good branching order before solving, theref…
Graph Neural NetworkMotion Ordering in Cellular Polar-polar and Polar-nonpolar Interactions
We examine the difference in motion ordering between cellular systems with and without information transfer to evaluate the effect of the polar--polar interaction through mutual guiding, which enables cells to inform oth…
Learning Directed Acyclic Graphs from Partial Orderings
Directed acyclic graphs (DAGs) are commonly used to model causal relationships among random variables. In general, learning the DAG structure is both computationally and statistically challenging. Moreover, without addit…