at Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague
Malostranské náměstí 2/25, 118 00 Praha 1, Czech Republic


People  |  Research  |  Projects  |  Software  |  Events  |  Contact

The group performs basic and applied research in the areas of satisfiability and discrete optimisation problems by applying techniques such as constraint and Boolean satisfiability, (constraint) logic programming, and knowledge reasoning. We do research on general problem solving techniques including search and consistency algorithms (motivated by artificial intelligence), on algorithms for solving particular combinatorial optimisation problems such as scheduling, and on formal properties of problems such as problem complexity. Currently the main application areas of our research are planning and scheduling.

The group continues the tradition of Constraint & Logic Programming Research Group whose history goes back to 1991 (established by Prof. Petr Štěpánek) and extends further its research and application topics.


People:


prof. RNDr. Roman Barták, Ph.D.

e-mail: bartak@ktiml.mff.cuni.cz
WWW: http://ktiml.mff.cuni.cz/~bartak
research interests: Constraint Satisfaction, Artificial Intelligence, Planning, Scheduling

PhD Students:

Tomáš Balyo
Vladimír Duša
Filip Dvořák
Daniel Toropila
Václav Vlček
Jindřich Vodrážka

Alumni:

Pavel Cejnar
Martin Hejna
Lukáš Chrpa (U. of Huddersfield)
David Kronus
Roman Mecl
Tomáš Müller (Purdue U.)
Petr Vilím (ILOG/IBM)


doc. RNDr. Ondřej Čepek, Ph.D.

e-mail: cepek@ktiml.mff.cuni.cz
WWW: http://ktiml.mff.cuni.cz/~cepek
research interests: Boolean Functions,Scheduling


RNDr. Petr Kučera, Ph.D.

e-mail: kucerap@ktiml.mff.cuni.cz
WWW: http://ktiml.mff.cuni.cz/~kucerap
research interests: Boolean Functions


RNDr. Pavel Surynek, Ph.D.

e-mail: surynek@ktiml.mff.cuni.cz
WWW: http://ktiml.mff.cuni.cz/~surynek
research interests: Boolean Satisfiablility, Planning


Research topics:

Constraint Satisfaction:
We deal with various aspects of constraint satisfaction technology including modelling combinatorial problems as constraint satisfaction problems, designing novel domain filtering algorithms and global constraints motivated by real-life problems, and design of search techniques and corresponding heuristics. We also apply these techniques to optimisation problems and problems with soft constraints.

Boolean Satisfiability:
We focus on novel techniques for solving Boolean satisfiability problems motivated by constraint satisfaction techniques and knowledge extraction from logical formulas. We are also interested in specifying particular classes of logical formulas that are polynomially solvable.

AI Planning:
Our research covers classical AI planning. We apply constraint satisfaction techniques to planning problems and we deal with knowledge engineering aspects of planning such as problem re-formulation and learning planning domain features useful for problem solving. Our ultimate goal is proposing a generic planning engine that integrates scheduling constraints.

Scheduling:
Constraint-based scheduling is our main application area. We focus on formal modelling of scheduling problems including modelling languages, problem formulation and automated extraction of knowledge from models that is useful for solving. We also propose solving algorithms both for specific problems and universally applicable to "any" scheduling problem. Our main research topic is integration of temporal, resource, and logical reasoning.

Industry co-operation: Visopt Ltd. (Israel), ManOPT (Ireland)

Academic co-operation: Masaryk University (Czech Republic), Czech Technical University (Czech Republic), Czech Academy of Sciences (Czech Republic), University of Limerick (Ireland), Cork Constraint Computation Centre/University College Cork (Ireland), Aalborg University (Denmark), Rutgers University (U.S.A.)


Research projects:

RealPlan: Towards Real-World Automated Planning
Grant Holder: Filip Dvořák (Charles University)
From: Grant Agency of Charles University
Period: 2011 - 2013

PlanEx: Bridging Planning and Execution
Grant Holder: Roman Barták (Charles University)
From: Czech Science Foundation
Period: 2010 - 2014

KnowSched: Knowledge Techniques in Scheduling
Grant Holder: Roman Barták (Charles University)
From: Czech Science Foundation
Period: 2010 - 2013

CPAI: Constraint Programming and Boolean Satisfiability for Artificial Intelligence
Grant Holder: Pavel Surynek (Charles University)
From: Czech Science Foundation
Period: 2009 - 2011

RobOrg: Design of Automated Control Systems for Robotic Organisms
Grant Holder: Daniel Toropila (Charles University)
From: Grant Agency of Charles University
Period: 2009 - 2011

ValuePOLE: An extended Value Chain model for performance Prediction and Optimisation of product and process Lifecycles for SMEs
Grant Holder: Con Sheahan (University of Limerick)
Co-operation: Aalborg University (Denmark), Charles University (Czech Republic)
From: EU - Commission of the European Communities (FP7)
Period: 2008 - 2010 (extended to 2011)

LeCoS: merging machine LEarning and COnstraint Satisfaction
Grant Holder: Filip Železný (Czech Technical University), Roman Barták (Charles University)
From: Czech Science Foundation
Period: 2008 - 2010

DynSched: Dynamic Aspects of Scheduling
Grant Holder: Roman Barták (Charles University), Hana Rudová (Masaryk University)
From: Czech Science Foundation
Period: 2007 - 2009

BooF: Boolean Functions
Grant Holder: Petr Kučera (Charles University)
From: Czech Science Foundation
Period: 2007 - 2009

PlanCP: Constraint Satisfaction in Planning
Grant Holder: Roman Barták (Charles University)
From: Grat Agency of Charles University
Period: 2006 - 2008

EMPOSME: Enterprise Modelling and Performance Optimisation for SMEs
Grant Holder: Con Sheahan (University of Limerick)
Co-operation: Aalborg University (Denmark), Charles University (Czech Republic), Cork Constraint Computation Centre (Ireland), University of Essen (Germany)
From: EU - Commission of the European Communities (FP6)
Period: 2005 - 2008

CBP&S: Constraint-Based Planning and Scheduling
Grant Holder: Roman Barták (Charles University)
From: Czech Science Foundation
Period: 2004 - 2006

APS: Advanced Planning and Scheduling
Grant Holder: Roman Barták (Charles University), Hana Rudová (Masaryk University)
From: Czech Science Foundation
Period: 2001 - 2003

CLP: Logic Programs with Constraints
Grant Holder: Roman Barták (Charles University)
From: Czech Science Foundation
Period: 1999- 2002


Software:

Interactive Gantt Viewer
visualises schedules defined as a set of activities connected via precedence constraints and allocated to unary resources. During the visualisation the software highlights violated resource and precedence constraints. In addition to visualisation, the software can fully automatically repair violated precedence and unary resource constraints by locally altering the schedule.

Filuta
is a sub-optimal domain-independent planning system that handles time and resource constraints in addition to traditional causal relations between actions.

VIZ
is a graphical user interface for description of planning domains and problems and their export to PDDL modelling language

VisPlan
is a graphical user interface for visualization and verification of plans, particularly with finding and showing the causal relations between the actions, identifying possible flaws in the plan and visualizing them to the user.

GraphRec
is a visualization tool oriented on the animation of moving entities on the generic middle sized graph (several hundred nodes). Typical input for GraphRec is created by some independent software that generates solutions for centralized path planning problems. Animation can be captured to image or video files.


Organized events:

We are organizing and co-organizing research workshops and conferences mainly related to constraint satisfaction, planning, and scheduling.

PSTL 2012: Workshop on Planning and Scheduling with Timelines
@ ICAPS 2012, Atibaia, Brazil

COPLAS 2012: Workshop on Constraint Satisfaction for Planning and Scheduling
@ ICAPS 2012, Atibaia, Brazil

IT Security for the Next Generation - European Cup 2012
@ Prague, Czech Republic

KEPS 2011: Workshop on Knowledge Engineering for Planning and Scheduling
@ ICAPS 2011, Freiburg, Germany

COPLAS 2011: Workshop on Constraint Satisfaction for Planning and Scheduling
@ ICAPS 2011, Freiburg, Germany

KEPS 2010: Workshop on Knowledge Engineering for Planning and Scheduling
@ ICAPS 2010, Toronto, Canada

COPLAS 2010: Workshop on Constraint Satisfaction for Planning and Scheduling
@ ICAPS 2010, Toronto, Canada

AIPS 2010: A Special Track on Artificial Intelligence Planning and Scheduling
@ FLAIRS 2010, Daytona Beach, U.S.A.

ICKEPS 2009: International Competition on Knowledge Engineering Techniques for Planning and Scheduling
@ ICAPS 2009, Thessaloniki, Greece

COPLAS 2009: Workshop on Constraint Satisfaction for Planning and Scheduling
@ ICAPS 2009, Thessaloniki, Greece

AIPS 2009: A Special Track on Artificial Intelligence Planning and Scheduling
@ FLAIRS 2009, Sanibel Island, U.S.A.

KEPS 2008: Workshop on Knowledge Engineering for Planning and Scheduling
@ ICAPS 2008, Sydney, Australia

COPLAS 2008: Workshop on Constraint Satisfaction for Planning and Scheduling
@ CP2008/ICAPS 2008, Sydney, Australia

AIPS 2008: A Special Track on Artificial Intelligence Planning and Scheduling
@ FLAIRS 2008, Coconut Grove, U.S.A.

PLANSIG 2007: 26th Workshop of the UK Planning and Scheduling Special Interest Group
@ Prague, Czech Republic

COPLAS 2007: Workshop on Constraint Satisfaction for Planning and Scheduling
@ CP2007/ICAPS2007, Providence, U.S.A.

ICKEPS 2005: International Competition on Knowledge Engineering Techniques for Planning and Scheduling
@ ICAPS 2005, Monterey, U.S.A.

CP-AI-OR 2005: International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
@ Prague, Czech Republic

iDay 2003: PLANET Technology Information Day
@ Prague, Czech Republic

ERCIM 2001: Sixth Annual Workshop of the ERCIM Working Group on Constraints
@ Prague, Czech Republic


Contact:

Doc. RNDr. Roman Barták, Ph.D.

Department of Theoretical Computer Science and Mathematical Logic
Faculty of Mathematics and Physics, Charles University in Prague

Malostranské nám. 2/25, 118 00 Praha 1
Czech Republic

e-mail: bartak (AT) ktiml.mff.cuni.cz
tel: +420 221 914 242
fax: + 420 221 914 323

Creative Commons License
Last update Friday, April 1, 2011