Author name cluster

Léon Planken

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

AAAI Conference 2025 Conference Paper

Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags

Kim van den Houten
Léon Planken
Esteban Freydell
David M.J. Tax
Mathijs de Weerdt

This study investigates scheduling strategies for the stochastic resource-constrained project scheduling problem with maximal time lags (SRCPSP/max). Recent advances in Constraint Programming (CP) and Temporal Networks have re-invoked interest in evaluating the advantages and drawbacks of various proactive and reactive scheduling methods. First, we present a new, CP-based fully proactive method. Second, we show how a reactive approach can be constructed using an online rescheduling procedure. A third contribution is based on partial order schedules and uses Simple Temporal Networks with Uncertainty (STNUs). Our statistical analysis shows that the STNU-based algorithm performs best in terms of solution quality, while also showing good relative offline and online computation time

PDF Details DOI

ICAPS Conference 2013 Conference Paper

Distributed Algorithms for Incrementally Maintaining Multiagent Simple Temporal Networks

James C. Boerkoel Jr.
Léon Planken
Ronald Wilcox
Julie Shah

When multiple agents want to maintain temporal information, they can employ a Multiagent Simple Temporal Network (MaSTN). Recent work has shown that the constraints in a MaSTN can be efficiently propagated by enforcing partial path consistency (PPC) with a distributed algorithm. However, new temporal constraints may arise continually due to ongoing plan construction or execution, the decisions of other agents, and other exogenous events. For these new constraints, propagation is again required to re-establish PPC. Because the affected part of the network may be small, one typically wants to exploit the similarities between the new and previous version of the MaSTN. To this end, we propose two new distributed algorithms for incrementally maintaining PPC. The first is inspired by TriSTP, the seminal PPC algorithm for STNs; the second is a distributed version of IPPC, which represents the current state of the art for incrementally enforcing PPC in a centralized setting. The worst-case time performance of these algorithms is similar to their centralized counterparts. We empirically compare our distributed algorithms, analyzing their performance under various assumptions, and demonstrate significant speedup over their centralized counterparts.

Details

ICAPS Conference 2011 Conference Paper

Computing All-Pairs Shortest Paths by Leveraging Low Treewidth

Léon Planken
Mathijs de Weerdt
Roman van der Krogt

Considering directed graphs on n vertices and m edges with real (possibly negative) weights, we present two new, efficient algorithms for computing all-pairs shortest paths (APSP). These algorithms make use of directed path consistency (DPC) along a vertex ordering d. The algorithms run in O(n2wd) time, where wd is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. We show empirically that also in many general cases, both constructed and from realistic benchmarks, the algorithms often outperform Johnson's algorithm, which represents the current state of the art with a run time of O(nm + n2log n). These algorithms can be used for temporal and spatial reasoning, e. g. for the Simple Temporal Problem (STP), which underlines its relevance to the planning and scheduling community.

Details

ICAPS Conference 2010 Conference Paper

Incrementally Solving STNs by Enforcing Partial Path Consistency

Léon Planken
Mathijs de Weerdt
Neil Yorke-Smith

Efficient management and propagation of temporal constraints is important for temporal planning as well as for scheduling. During plan development, new events and temporal constraints are added and existing constraints may be tightened; the consistency of the whole temporal network is frequently checked; and results of constraint propagation guide further search. Recent work shows that enforcing partial path consistency provides an efficient means of propagating temporal information for the popular Simple Temporal Network (STN). We show that partial path consistency can be enforced incrementally, thus exploiting the similarities of the constraint network between subsequent edge tightenings. We prove that the worst-case time complexity of our algorithm can be bounded both by the number of edges in the chordal graph (which is better than the previous bound of the number of vertices squared), and by the degree of the chordal graph times the number of vertices incident on updated edges. We show that for many sparse graphs, the latter bound is better than that of the previously best-known approaches. In addition, our algorithm requires space only linear in the number of edges of the chordal graph, whereas earlier work uses space quadratic in the number of vertices. Finally, empirical results show that when incrementally solving sparse STNs, stemming from problems such as Hierarchical Task Network planning, our approach outperforms extant algorithms.

Details

ICAPS Conference 2008 Conference Paper

P3C: A New Algorithm for the Simple Temporal Problem

Léon Planken
Mathijs de Weerdt
Roman van der Krogt

The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called Triangle-STP, is based on partial path consistency and starts from a chordal constraint graph. In this paper, we analyse this algorithm and show that there exist instances for which its time complexity is quadratic in the number of triangles in the constraint graph. We propose a new algorithm, P3C, whose worst-case time complexity is is linear in the number of triangles. We show both formally and experimentally that P3C outperforms Triangle-STP significantly.

Details