Welcome, visitor!

[P]apers

What's new

March '11: Paper at ICAPS
June '10: Paper at CP
July '09: Paper at SPARK
May '09: Paper in J. of Scheduling

Contact

Email: roman@4c.ucc.ie
Office: +353-21-420 5965
Fax: +353-21-420 5369
Mobile: +353-83-33 48084
Address:2-60, Floor 2
Cork Constraint
    Computation Centre
Western Gateway
    Building
University College Cork
Cork, Ireland

Buttons & Banners

Disclaimer

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

You may be interested to see what Google Scholar has in its database.

2012

  1. N.P. Dunphy, J. Little and R.P.J. van der Krogt. A Model for Retrofit Configuration Selection using Multiple Decision Diagrams. In Proceedings of Building Simulation and Optimization (BSO-12), 2012.
    [ view abstract | bibtex ]

    The paper demonstrates the use of Multiple Decision Diagrams (MDDs) in consideration of building energy retrofit options. Candidate retrofit alternatives including associated key performance indicators (KPIs) (e.g. cost, energy, embodied carbon) can be compiled into MDDs where various performance implications can be effectively illustrated and KPI trade-offs explored. We argue MDDs are flexible supporting a wide range of computations around the decision process. Significantly, we show KPIs can also be used as constraints in the search for satisfactory retrofit configurations and conclude that the MDD approach complements existing methods of optimising building energy retrofit options by providing a reduced initial search space.

    Bibtex not available yet

  2. L.R. Planken, M.M. de Weerdt and R.P.J. van der Krogt. Computing All-Pairs Shortest Paths by Leveraging Low Treewidth. In Journal of Artificial Intelligence Research, 43:353-388, 2012.
    [ view abstract | bibtex ]

    We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d <= w_d is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshall's as well as Johnson's algorithm, which represent the current state of the art with a run time of O(n^3) and O(nm + n^2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.

    @article{ planken12jair,
       author = {L{'e}on Planken and Mathijs de Weerdt and Roman van der Krogt},
       title = {Computing All-Pairs Shortest Paths by Leveraging Low Treewidth},
       year = 2012,
       journal = {Journal of Artificial Intelligence Research ({JAIR})},
       volume = {43},
       pages = {353--388}
    }
    

2011

  1. L.R. Planken, M.M. de Weerdt and R.P.J. van der Krogt. Computing All-Pairs Shortest Paths by Leveraging Low Treewidth. In Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS-11), 2011. (Honorable mention for best student paper.)
    [ view abstract | bibtex ]

    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.

    @inproceedings{ planken11icaps,
      author    = {L{'e}on Planken and Mathijs de Weerdt and Roman van der Krogt},
      title     = {Computing All-Pairs Shortest Paths by Leveraging Low Treewidth},
      year      = 2011,
      booktitle = {Proceedings of the Twenty-First International Conference
                   on Automated Planning and Scheduling ({ICAPS}-11)},
      pages     = {170--177}
    }
    
  2. G. Boyle, J. Little, J. Manning and R.P.J. vander Krogt. A Constraint-based Approach to Ship Maintenance for the Irish Navy. In Proceedings of the Irish Transport Research Network Conference (ITRN-11), 2011.
    [ view abstract | bibtex ]

    The Irish Naval Service performs an annual maintenance on each of its ships, known as a "refit". During a refit, the ship is taken out of normal service and maintenance activities are performed for twenty working days. The ship must be available for patrol at the end of the refit period, so timely completion is essential.
    The officer in charge of the dockyard must organise the team of workers, coordinate with the ship's staff and other naval units, and enlist the services of outside contractors when necessary. Naval refits are characterised by constraints that reflect the confined working environment of the ship, which presents numerous mechanical and safety challenges. In the extreme case, there are tasks that require an entire area of the ship to be cleared on health and safety grounds. The nature of such tasks means that delays can have significant knockon effects. Furthermore, many of the estimates of task duration, particularly of engine repair work, cannot be fully confirmed until the engine has been dismantled and a thorough inspection conducted. These facts create considerable uncertainty in the extent of work required, and so the ability to quickly react to changes and reschedule is paramount, in order that the ship be ready to return to patrol duty.
    In this paper we present a scheduling model based on constraint programming that deals with the issues of space and safety, while giving particular focus to the aspect of coping with unexpected changes. It has undergone initial evaluation on a real scenario at the Irish Naval Service dockyard.

    Bibtex not available yet

  • L.R. Planken, M.M. de Weerdt and R.P.J. van der Krogt. Computing All-Pairs Shortest Paths by Leveraging Low Treewidth (abstract). In Proceedings of the Twenty-third Belgian-Netherlands Conference on Artificial Intelligence (BNAIC-11), 2011

2010

  1. R.P.J. van der Krogt, J. Feldman, J. Little and D. Stynes. An Integrated Business Rules and Constraints Approach to Data Centre Capacity Management. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming, 2010.
    [ view abstract | bibtex ]

    A recurring problem in data centres is that the constantly changing workload is not proportionally distributed over the available servers. Some resources may lay idle while others are pushed to the limits of their capacity. This in turn leads to decreased response times on the overloaded servers, a situation that the data centre provider wants to prevent. To solve this problem, an administrator may move (reallocate) applications or even entire virtual servers around in order to spread the load. Since there is a cost associated with moving applications (in the form of down time during the move, for example), we are interested in solutions with minimal changes. This paper describes a hybrid approach to solving such resource reallocation problems in data centres, where two technologies have to work closely together to solve this problem in an efficient manner.
    The first technology is a Business Rules Management System (BRMS), which is used to identify which systems are considered to be overloaded on a systematic basis. Data centres use complex rules to track the behaviour of the servers over time, in order to properly identify overloads. Representing these tracking conditions is what the BRMS is good for. It defines the relationships (business constraints) over time between different applications, processes and required resources that are specific to the data centre. As such, it also allows a high degree of customisation.
    Having identified which servers require reallocation of their processes, the BRMS then automatically creates an optimisation model solved with a Constraint Programming (CP) approach. A CP solver finds a feasible or the optimal solution to this CSP, which is used to provide recommendations on which workload should be moved and whereto. Notice that our use of a hybrid approach is a requirement, not a feature: employing only rules we would not be able to compute an optimal solution; using only CP we would not be able to specify the complex identification rules without hard-coding them into the program. Moreover, the dedicated rule engine allows us to process the large amounts of data rapidly.

    @inproceedings{ krogt10cp,
      author    = {Roman van der Krogt and Jacob Feldman and James Little and David Stynes},
      title     = { An Integrated Business Rules and Constraints Approach to Data Centre Capacity Management},
      year      = 2010,
      booktitle = {Proceedings of the Sixteenth International Conference on Principles
                   and Practice of Constraint Programming ({CP}-10)},
      pages     = {568--582},
      location  = {St Andrews, Scotland}
    }
    
  2. R.P.J. van der Krogt, J. Geraghty, M.R. Salman, J. Little. On Supporting Lean Methodologies using Constraint-Based Scheduling. In Journal of Scheduling, 13(4):301-314. (Springer link)
    [ view abstract | bibtex ]

    Lean Manufacturing —often simply referred to as "Lean"— is a process management philosophy that aims to improve the way in which goods are produced by removing waste and implementing flow. It is widely implemented and receives widespread attention. To a large extent, it relies on visual and simple mechanical aids to improve manufacturing effectiveness. However, when it comes to combining several aspects of Lean or when dealing with complex environments, quantitative modelling becomes essential to achieve the full benefits.
    In this paper, we show through two detailed case studies how various aspects of Lean can be supported using (Constraint-Based) scheduling tools. One study concerns a decision support tool to evaluate possible benefits of a Lean methodology; the other supports the day-to-day scheduling of a complex, Leaned production process.

    @article{ krogt10josh,
      author    = {Roman van der Krogt and John Geraghty and Mustafa Ramzi Salman and James Little},
      title     = {On Supporting Lean Methodologies using Constraint-Based Scheduling},
      year      = 2010,
      journal   = {Journal of Scheduling},
      volume    = {13},
      number    = {4},
      pages     = {301--314}
    }
    
  3. L.A. Swenson, J. Little, J. Manning and R.P.J. van der Krogt. Using Sensitiviy Analysis to Illustrate and Improve Schedule Robustness. In Proceedings of the 28th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-10), 2010.
    [ view abstract | bibtex ]

    Robust schedules are important to industry for reasons, ultimately, of profit and maintaining competitiveness. We propose that sensitivity analysis can be used to improve schedule robustness. We illustrate this using two case studies, the classic bridge building problem and from real life, a semiconductor manufacturing problem. In both cases, we generate a predictive schedule with the performance objective of minimising makespan. Disruptions to the schedule are modelled respectively as duration extensions and release time delays. From a senstivity graph, we can formulate a hypothesis around how to introduce float into the original schedule so that it becomes more robust to the same changes with a possible, though not necessarily obligatory, extention to the manufacturing time.

    @inproceedings{ swenson10plansig,
      author    = {Lisa A. Swenson and James Little and Joseph Manning and Roman van der Krogt},
      title     = {Using Sensitiviy Analysis to Illustrate and Improve Schedule Robustness},
      year      = 2010,
      booktitle = {Proceedings of the twenty-eighth Workshop of the {UK} Planning and
                   Scheduling Interest Group ({PlanSIG}-10)},
      pages     = {177--182}
    }
    

2009

  1. R.P.J. van der Krogt. Quantifying Privacy in Multiagent Planning. In Multiagent and Grid Systems: An International Journal 5(4):451-469. (IOS Press link)
    [ view abstract | bibtex ]

    Privacy is often cited as the main reason to adopt a multiagent approach for a certain problem. This also holds true for multiagent planning. Still, a metric to evaluate the privacy performance of planners is virtually non-existent. This makes it hard to compare different algorithms on their performance with regards to privacy. Moreover, it prevents multiagent planning methods from being designed specifically for this aspect.
    This paper introduces such a measure for privacy. It is based on Shannon's theory of information and revolves around counting the number of alternative plans that are consistent with information that is gained during, for example, a negotiation step, or the complete planning episode. To accurately obtain this measure, one should have intimate knowledge of the agent's domain. It is unlikely (although not impossible) that an opponent who learns some information on a target agent has this knowledge. Therefore, it is not meant to be used by an opponent to understand how much he has learned. Instead, the measure is aimed at agents who want to know how much privacy they have given up, or are about to give up, in the planning process. They can then use this to decide whether or not to engage in a proposed negotiation, or to limit the options they are willing to negotiate upon.

    @article{ krogt09mags,
      author    = {Roman van der Krogt},
      title     = {Quantifying Privacy in Multiagent Planning},
      year      = 2009,
      journal   = {Multiagent and Grid Systems: An International Journal},
      volume    = {5},
      number    = {4},
      pages     = {451--469}
    }
    
  2. R.P.J. van der Krogt and J. Little. Optimising Machine Selection Rules for Sequence Dependent Setups with an Application to Cartoning. In Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing (INCOM-09), 2009.
    [ view abstract | bibtex ]

    Conventional scheduling technology, which tries to optimise performance metrics such as utilisation and makespan, works well in environments where there is a high degree of stability, and hence certainty. However, in uncertain situations, schedules that try to achieve optimality have trouble achieving this target. An often used technique to circumvent the issues with uncertainty that optimal policies display, is the use of rules that are triggered when a job enters the system or a machine becomes available. Such rules are by definition reactive, and can thus deal very well with uncertainty.
    The downside of these rules is that they make local decisions, which may result in non-optimal behaviour. This becomes especially apparent in light of significant sequence dependent setup times. These are, by nature, dependent upon the global sequence, something that rules cannot deal well with. In this paper, we investigate a method to generate custom machine selection rules that lead to improved setup times. We illustrate the advantages of this new type of rule by presenting an experimental analysis of using these rules at the cartoning department of a large manufacturing company.

    @inproceedings{ krogt09incom,
    author = {Roman van der Krogt and James Little},
    title = {Optimising Machine Selection Rules for Sequence Dependent Setups
    with an Application to Cartoning},
    booktitle = {Preprints of the Thirteenth IFAC Symposium on Information Control
    Problems in Manufacturing},
    pages = {1148--1153},
    year = 2009
    }
  3. M.R. Salman, R.P.J. van der Krogt, J. Little and J. Geraghty. Applying Lean Principles to Production Scheduling. In Proceedings of the 19th International Conference on Flexible Automation and Intelligent Manufacturing (FAIM 2009), 2009.
    [ view abstract | bibtex ]

    When exploring the Lean issue, literature appears to have countless definitions to describe that individual topic, causing misinterpretations between academics and professionals alike. The mainstream Lean implementation ventures are merely a compilation of tools and methods that are forced down the organisational hierarchy from higher tiers, due to other organisations publicising lean in improving their enterprise.s effectiveness and efficiency. However, lean implementations have often undesirable outcomes. Firstly, organisations either do not achieve the levels of success they initially yearned. This leads to management either deserting their lean efforts or seeking aimlessly for a new buzz word to adopt. Secondly, an enterprise may find it difficult to sustain the lean improvements, and thus rushing to conclude lean as incompatible with their industry, or unsuited for their organisational structure. These shortcomings can be easily avoided by recognising lean not only as a collection of tools but also a philosophy. The Lean philosophy needs to be applied companywide, with both management and employees onboard, to tackle business issues as they arise with a united way of thinking. In turn, this means that when opportunities or problems occur, and traditional lean tools fail short, the shared way of thinking by the organisation can be used to derive and develop new tailored solutions to address the issue directly. This paper aims to illustrate the possibilities of lean tools being applied in complex production environment, and introduce two case studies supporting the findings. In particular, we argue that the full potential of planning and scheduling in a manufacturing setting can only benefit from the utilisation of lean principles and the support of quantitative modelling.

    @inproceedings{ salman09faim,
    author = {Mustafa Ramzi Salman1 and Roman van der Krogt and James Little and John Geraghty},
    title = {Applying Lean Principles to Production Scheduling},
    booktitle = {Proceedings of the Nineteenth International Conference on Flexible Automation
    and Intelligent Manufacturing},
    pages = {743--750},
    year = 2009
    }
  4. R.P.J. van der Krogt, J. Little and H. Simonis. Scheduling in the Real World: Lessons Learnt. In Proceedings of the ICAPS'09 Scheduling and Planning Applications woRKshop.
    [ view abstract | bibtex ]

    Developing scheduling systems for industry, whether these are prototype systems to explore whether a certain technique can be applied in a certain new area, or production systems that will support the day-to-day running of a factory, is quite different from developing research systems aimed at the vast library of benchmark problems. In particular, we have found that real-world problems do not come with a clear set of requirements such as the benchmark ones and seldom match an existing research problem due to additional constraints on the solution posed by the particular production environment.
    This paper will present some lessons (issues and recommendations) we learnt from our interaction with industry in developing scheduling systems, hopefully providing some insight into the peculiarities of real-world scheduling for people about to apply scheduling (or planning, or any other AI or OR technique) in practice.

    @inproceedings{ krogt09spark,
    author = {Roman van der Krogt and James Little and Helmu Simonis},
    title = {Scheduling in the Real World: Lessons Learnt},
    booktitle = {Proceedings of the {ICAPS}'09 Scheduling and Planning Applications woRKshop ({SPARK}-09)},
    pages = {92--98},
    year = 2009
    }

2008

  1. R.P.J. van der Krogt, M.M. de Weerdt, and Y. Zhang. Of Mechanism Design and Multiagent Planning. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-08), 2008.
    [ view abstract | bibtex ]

    Multiagent planning methods are concerned with planning by and for a group of agents. If the agents are self-interested, they may be tempted to lie in order to obtain an outcome that is more rewarding for them. We therefore study the multiagent planning problem from a mechanism design perspective, showing how to incentivise agents to be truthful. We prove that the well-known truthful VCG mechanism is not always truthful in the context of optimal planning, and present a modification to fix this. Finally, we present some (domain-dependent) poly-time planning algorithms using this fix that maintain truthfulness in spite of their non-optimality.

    @inproceedings{ krogt08ecai,
      author    = {Roman van der Krogt and Mathijs de Weerdt and Yingqian Zhang},
      title     = {Of Mechanism Design and Multiagent Planning},
      year      = 2008,
      booktitle = {Proceedings of the Eighteenth European Conference on Artificial Intelligence},
      pages     = {423--427}
    }
    
  2. R.P.J. van der Krogt. Modification Strategies for SAT-based Plan Adaptation. In Archives of Control Sciences 18(2):203-230. Also published as Technical report TR-03-2008.
    [ view abstract | bibtex ]

    Planning, the generation of a course of action to achieve a set of goals, is an important technique in the development of intelligent agents. Heretofore, planning has been largely considered as a one-shot problem. However, in practice, we are often dealing with situations in which an existing plan has to be adapted. Not only might we be facing a dynamic environment that requires a plan to be repaired, but it may also be that we recognise the new planning problem as being similar to one that we have solved before (i.e. case-based planning).
    This paper investigates a plan adaptation framework based on SAT-encodings of the planning problem. Compilation techniques have been very successfully applied to planning, as evidenced by their success in recent planning competitions. So far, however, such techniques have not been used for plan adaptation purposes. This paper explores whether it is feasible to modify the generated SAT instances such as to encode information that was extracted from the solution to the original planning problem.

    @article{ krogt08acs,
      author    = {Roman van der Krogt},
      title     = {Modification Strategies for {SAT}-based Plan Adaptation},
      year      = 2008,
      journal   = {Archives of Control Sciences},
      volume    = {18},
      number    = {2},
      pages     = {203--230}
    }
    
  3. L.R. Planken, M.M. de Weerdt and R.P.J. van der Krogt. P3C: A New Algorithm for the Simple Temporal Problem. In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS-08), 2008.
    [ view abstract | bibtex ]

    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 Δ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 linear in the number of triangles. We show both formally and experimentally that P3C outperforms ΔSTP significantly.

    @inproceedings{ planken08icaps,
      author    = {L{'e}on Planken and Mathijs de Weerdt and Roman van der Krogt},
      title     = {P3C: A New Algorithm for the Simple Temporal Problem},
      year      = 2008,
      booktitle = {Proceedings of the Eighteenth International Conference
                   on Automated Planning and Scheduling ({ICAPS}-08)},
      pages     = {256--263}
    }
    
  4. R.P.J. van der Krogt and J. Little. Finding Efficient Dispatching Rules using Optimisation and Simulation. In Proceedings of the 19th Irish Conference of Artificial Intelligence and Cognitive Science (AICS-08), 2008.
    [ view abstract | bibtex ]

    The COSAR project ---Combination of Optimisation and Simulation in the Assessment of Risk--- aims to investigate the combination of optimisation and simulation techniques to better deal with uncertainty in manufacturing environments. As a pilot study, we investigated the generation of robust dispatch rules for high-volume cartoning of contact lenses. It is often difficult to determine initially the best set of rules. Here we demonstrate how an initial good set of rules, generated from an optimization model can be improved (manually) through information from a simulation model.

    @inproceedings{ krogt08aics,
      author    = {Roman van der Krogt and James Little},
      title     = {Finding Efficient Dispatching Rules using Optimisation and
                   Simulation},
      year      = 2008,
      booktitle = {Proceedings of the Nineteenth Irish Conference of Artificial
                   Intelligence and Cognitive Science},
      pages     = {262--271}
    }
    

2007

  1. R.P.J. van der Krogt. Privacy in Multiagent Planning: A Classical Definition with Illustration. In Proceedings of the AAMAS-07 Workshop on Coordinating Agents' Plans and Schedules, 2007.
    [ view abstract | bibtex ]

    Privacy is often cited as the main reason to adopt a multiagent approach for a certain problem. This also holds true for multiagent planning. Still, papers on multiagent planning hardly ever make explicit in what ways their systems protect their users' privacy, nor do they give a quantitative analysis. The reason for this is that a theory of privacy loss in multiagent planning is virtually non-existent so far.
    This paper proposes a measure for privacy loss based on Shannon's theory of information. To illustrate our approach, we apply this metric to an existing multiagent planning system to assess its merits when it comes to privacy on two domains. For this, we compare its plans to centrally generated solutions (by a trusted third party) for the same problems. The results clearly establish the need for such an analysis: even though the multiagent planner seemingly exchanges little information, its overall performance with respect to privacy is less than that of the centralised system (not taking into account the privacy loss with respect to the central planner, of course).

    @inproceedings{ krogt07caps,
      author    = {Roman van der Krogt},
      title     = {Privacy in Multiagent Planning: A Classical Definition with
                   Illustration},
      year      = 2007,
      booktitle = {Proceedings of the AAMAS-07 Workshop on Coordinating Agents' Plans
                    and Schedules},
      pages     = {17--24},
      editor    = {Michael Brenner and Brad Clement and Mathijs de Weerdt},
      location  = {Honolulu, Hawaii}
    }
    
  2. R.P.J. van der Krogt, J. Little, K. Pulliam, S. Hanhilammi, and Y. Jin. Scheduling for Cellular Manufacturing. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming, 2007. (Springer link)
    [ view abstract | bibtex ]

    Alcatel-Lucent is a major player in the field of telecommunications. One of the products it offers to network operators is wireless infrastructure such as base stations. Such equipment is delivered in cabinets. These cabinets are packed with various pieces of electronics: filters, amplifiers, circuit packs, etc. The exact configuration of a cabinet is dependent upon the circumstances it is being placed in, and some 20 product groups can be distinguished. However, the variation in cabinets is large, even within one product group. For this reason, they are built to order.
    In order to improve cost, yield and delivery performance, lean manufacturing concepts were applied to change the layout of the factory to one based on cells. These cells focus on improving manufacturing through standardised work, limited changeovers between product groups and better utilisation of test equipment. A key component in the implementation of these improvements is a system which schedules the cells to satisfy customer request dates in an efficient sequence.
    This paper describes the transformation and the tool that was built to support the new method of operations. The implementation has achieved significant improvements in manufacturing interval, work in process inventory, first test yield, headcount, quality (i.e. fewer defects are found during the testing stage) and delivery performance. Although these benefits are mainly achieved because of the change to a cell layout, the scheduling tool is crucial in realising the full potential of it.

    @inproceedings{ krogt07cp,
      author    = {Roman van der Krogt and James Little and Kenneth Pulliam and
                   Sue Hanhilammi and Yue Jin},
      title     = {Scheduling for Cellular Manufacturing},
      year      = 2007,
      booktitle = {Proceedings of the Thirteenth International Conference on Principles
                   and Practice of Constraint Programming ({CP}-07)},
      pages     = {105--117},
      location  = {Providence, Rhode Island}
    }
    
  3. R.P.J. van der Krogt. Privacy Loss in Classical Multiagent Planning. In Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT-07), 2007. (IEEE link)
    [ view abstract | bibtex ]

    Privacy is often cited as the main reason to adopt a multiagent approach for a certain problem. This also holds true for multiagent planning. Still, papers on multiagent planning hardly ever make explicit in what ways their systems protect their users' privacy, nor do they give a quantitative analysis. The reason for this is that a theory of privacy loss in multiagent planning is virtually non-existent so far.
    This paper proposes a measure for privacy loss based on Shannon's theory of information. To illustrate our approach, we apply this metric to an existing multiagent planning system to assess its merits when it comes to privacy on two domains. For this, we compare its plans to centrally generated solutions (by a trusted third party) for the same problems. The results clearly establish the need for such an analysis: even though the multiagent planner seemingly exchanges little information, its overall performance with respect to privacy is less than that of the centralised system (not taking into account the privacy loss with respect to the central planner, of course).

    @inproceedings{ krogt07iat,
      author    = {Roman van der Krogt},
      title     = {Privacy Loss in Classical Multiagent Planning},
      year      = 2007,
      booktitle = {Proceedings of the 2007 {IEEE}/{WIC}/{ACM} International Conference on
                   Intelligent Agent Technology ({IAT}-07)},
      pages     = {168--174},
      location  = {Silicon Valley, California}
    }
    
  • R.P.J. van der Krogt. Scheduling Implant Operations using Constraint-Based Scheduling (abstract). In Proceedings of the 3rd Workshop on Simulation in Manufacturing, Services and Logistics, 2007.
    [ view abstract | bibtex ]

    Our presentation describes recent work on implant scheduling that was undertaken in collaboration with Intel Ireland.

    @inproceedings{ krogt07simsoc,
      author    = {Roman van der Krogt},
      title     = {Scheduling Implant Operations using Constraint-Based Scheduling (abstract)},
      year      = 2007,
      booktitle = {Online Proceedings of the Third Workshop on Simulation in Manufacturing,
                   Services and Logistics}
      location  = {Dublin, Ireland}
    }
    

2006

  1. R.P.J. van der Krogt and J. Little. The PDES Workbench. In Proceedings of the 13th International Conference on Concurrent Engineering: Research and Applications (CE-06), 2006. (IOS Press link)
    [ view abstract | bibtex ]

    Central to the operation of a manufacturing plant is the planning and scheduling of the activities that take place. The quality of the plans and schedules produced has significant impact on the effectiveness and efficiency of a company. These schedules are restricted by the constraints imposed upon them by the design of the plant. However, while expert designers are able to roughly predict the outcome of a design in terms of its overall throughput, quantitative figures on future schedules are not usually produced. By implication, design constraints may be found to be expensive in scheduling terms during the operation of the plant and at a stage when improvements are hard or expensive to make.
    This paper presents the PDES Workbench, a graphical system that is able to generate plans and schedules based on real-life manufacturing plant designs. This allows a manager or planner to assess the schedulability of a particular design at an early stage. When a schedule is found to be flawed in any aspect, it may not be apparent what to change in the design without degrading other aspects of the schedule. Therefore, the system is equipped with a case-based reasoning system that is able to proactively suggest ways of improving the design for improved scheduling results.

    @inproceedings{ krogt06ce,
      author    = {Roman van der Krogt and James Little},
      title     = {The {PDES} Workbench},
      year      = 2006,
      booktitle = {Proceedings of the Thirteenth International Conference
                   on Concurrent Engineering: Research and Applications ({CE}-06)},
      pages     = {619--626},
      location  = {Antibes, France}
    }
    
  2. M.M. de Weerdt and R.P.J. van der Krogt. Inefficiencies in Task Allocation for Multiagent Planning with Bilateral Deals. In Proceedings of the 25th workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-06), 2006.
    [ view abstract | bibtex ]

    Distributed planning in a multiagent environment may give rise to inefficiencies. We study this effect focussing on the task allocation problem. We show that in the worst case, the result of a multiagent approach can be arbitrarily bad in theory when recontracting and multilateral deals are not allowed. This is a more precise result than was previously known, which was that we are not guaranteed to find the optimal solution. We show that the sources of this disappointing result are the impossibility to come back on (bad) contracts in combination with either selfish agents, or agents that have incomplete information on potential costs. Furthermore, we show some preliminary experimental results of the effect of these causes on the optimality of a solution for multiagent task allocation. Interestingly, none of the experiments exhibit the very negative outcomes that are predicted by the theory. Although it is too early to draw conclusions, this might indicate that in practical situations, the circumstances that lead to the theoretical results are very unlikely.

    @inproceedings{ weerdt06plansig,
      author    = {Mathijs de Weerdt and Roman van der Krogt},
      title     = {Inefficiencies in Task Allocation for Multiagent Planning
                   with Bilateral Deals},
      year      = 2006,
      booktitle = {Proceedings of the Twentyfifth workshop of the {UK} Planning and
                   Scheduling Special Interest Group ({PlanSIG}-06)},
      pages     = {33--38},
      editor    = {Rong Qu},
      location  = {Nottingham, {UK}}
    }
    

2005

  1. R.P.J. van der Krogt and M.M. de Weerdt. Plan Repair as an Extension of Planning. In Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS-05), 2005. (AAAI link)
    [ view abstract | bibtex ]

    In dynamic environments, agents have to deal with changing situations. In these cases, repairing a plan is often more efficient than planning from scratch, but existing planning techniques are more advanced than existing plan repair techniques. Therefore, we propose a straightforward method to extend planning techniques such that they are able to repair plans. This is possible, because plan repair consists of two different operations: (i) removing obstructing constraints (such as actions) from the plan, and (ii) adding actions to achieve the goals. Adding actions is similar to planning, but as we demonstrate, planning heuristics can also be used for removing constraints, which we call unrefinement. We present a plan repair template that reflects these two operations, and we present a heuristic for unrefinement that can make use of an arbitrary existing planning technique. We apply this method to an existing planning system (VHPOP) resulting in POPR, a plan repair system that performs much better than replanning from scratch, and also significantly better than another recent plan repair method (GPG). Furthermore, we show that the plan repair template is a generalisation of existing plan repair methods.

    @inproceedings{ krogt05icaps,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {Plan Repair as an Extension of Planning},
      year      = 2005,
      booktitle = {Proceedings of the Fifteenth International Conference
                   on Automated Planning and Scheduling ({ICAPS}-05)},
      pages     = {161--170},
      location  = {Monterey, California}
    }
    
  2. C. Witteveen, N. Roos, R.P.J. van der Krogt and M.M. de Weerdt. Diagnosis of Single and Multi-Agent Plans. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-05), 2005.
    [ view abstract | bibtex ]

    We discuss the application of Model Based Diagnosis in agent-based planning. We model a plan as a system to be diagnosed and assume that agents can monitor the execution of the plan by making partial observations during plan execution. These observations are used by the agents to explain plan deviations (errors) by qualifying some action instances as behaving abnormally. We prefer those qualifications that are maximum informative, i.e. explain as much as possible. Since in a plan several instances of the same action might occur, an error occurring in one instance might be used to predict the occurrence of the same error in an action instance to be executed later on. To account for such correlations, we introduce causal rules to generate diagnoses from action instances qualified as abnormally and we introduce Pareto minimal causal diagnoses as the right extension of classical minimal diagnoses.
    Next, we consider the multi-agent perspective where each agent is responsible for a part of the total plan, we show how plan-diagnoses of these partial plans are related to diagnoses of the total plan and how global diagnoses can be obtained in a distributed way.

    @inproceedings{ witteveen05aamas,
      author    = {Cees Witteveen and Nico Roos and Roman van der Krogt and Mathijs de Weerdt},
      title     = {Diagnosis of Single and Multi-Agent plans},
      year      = 2005,
      booktitle = {Proceedings of the Fourth International Joint Conference on Autonomous Agents and
                   Multi Agent Systems},
      pages     = {805--812},
      location  = {Utrecht, The Netherlands}
    }
    
  3. R.P.J. van der Krogt and M.M. de Weerdt. Self-interested Planning Agents Using Plan Repair. In Proceedings of the ICAPS 2005 Workshop on Multiagent Planning and Scheduling, 2005.
    [ view abstract | bibtex ]

    We present a novel approach to multiagent planning for self-interested agents. The main idea behind our approach is that multiagent planning systems should be built upon (single-agent) plan repair systems. In our system agents can exchange goals and subgoals through an auction, using their own heuristics or utility functions to determine when to auction and what to bid. Some experimental results for a logistics domain demonstrate empirically that this system supports the coordination of self-interested agents.

    @inproceedings{ krogt05icapsws,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {Self-interested Planning Agents Using Plan Repair},
      year      = 2005,
      booktitle = {Proceedings of the {ICAPS} 2005 Workshop on Multiagent
                   Planning and Scheduling},
      pages     = {36--44},
      location  = {Monterey, California}
    }
    
  4. R.P.J. van der Krogt and M.M. de Weerdt. Coordination through Plan Repair. In Proceedings of the 4th Mexican International Conference on Artificial Intelligence (MICAI-05), 2005. (Springer link)
    [ view abstract | bibtex ]

    In most practical situations, agents need to continuously improve or repair their plans. In a multiagent system agents also need to coordinate their plans. Consequently, we need methods such that agents in a multiagent system can construct, coordinate, and repair their plans. In this paper we focus on the problem of coordinating plans without exchanging explicit information on dependencies, or having to construct a global set of constraints. Our approach is to combine a propositional plan repair algorithm for each agent with a blackboard that auctions subgoals on behalf of the agents. Both the details of a first construction and some initial experimental results are discussed.

    @inproceedings{ krogt05micai,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {Coordination through Plan Repair},
      year      = 2005,
      booktitle = {Proceedings of the Fourth Mexican International Conference on
                   Artificial Intelligence ({MICAI}-05)},
      pages     = {264--274},
      location  = {Monterrey, Mexico}
    }
    
  5. R.P.J. van der Krogt and M.M. de Weerdt. Plan Repair using a Plan Library. In Proceedings of the Seventeenth Belgium-Netherlands Conference on Artificial Intelligence (BNAIC-05), 2005.
    [ view abstract | bibtex ]

    Plan library's have proven their added value to the efficiency of planning. In this paper, we present results on the use of a plan library to plan repair. We show that using a relatively simple library, we can already obtain signifficant improvements in efficiency compared to plan repair without a library.

    @inproceedings{krogt05bnaic,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {Plan Repair using a Plan Library},
      booktitle = {Proceedings of the Belgium-Dutch Conference on Artificial Intelligence (BNAIC-05)},
      year      = {2005},
      pages     = {254--259}
    }
    
  6. R.P.J. van der Krogt. Plan Repair in Single-Agent and Multi-Agent Systems. Ph.D. Thesis, Delft University of Technology, 2005.
    [ view abstract | bibtex ]

    Autonomous agents need to be equipped with a planning component that lets them devise a plan to reach their goals. However, this is not enough, as we saw in the various examples that were provided. Often a plan may become ineffective or inefficient because of changes in the environment that the agent did not expect. Also, agents may need other agents to perform certain subtasks that they cannot perform themselves. Therefore, agents also need to be equipped with techniques to deal with the coordination of their actions with other agents and to deal with dynamic environments. This thesis focuses on the latter of these types of techniques, while taking into account the former type: we investigate plan repair in a multi-agent context.

    @PHDTHESIS{krogt05thesis,
      author = {Roman van der Krogt},
      title = {Plan repair in Single-Agent and Multi-Agent Systems},
      school = {Delft University of Technology},
      year = {2005},
      address = {Delft, The Netherlands}
    }

2004

  1. R.P.J. van der Krogt, M.M. de Weerdt, and C. Witteveen. A resource based framework for planning and replanning. In Web Intelligence and Agent Systems 1(3-4):173-186, 2003. (IOS Press link)
    [ view abstract | bibtex ]

    The aim of this paper is to combine standard planning and replanning methods into a rigorous unifying framework, extending an existing logic-based approach to resource-based planning. In this Action Resource Framework (ARF), actions and resources are the primitive concepts. Actions consume and produce resources. Plans are structured objects composed of actions and resource schemes and an explicit dependency function specifying their interrelationships.
    Previous plans can be used both for creating new plans and for modifying plans. Since we are often interested in reusing only a part of these previous plans, we extend the Action Resource Formalism with incomplete plans. To efficiently represent such incomplete plans we use the notion of a gap. We maintain a library of incomplete plans (with gaps), and we present operators to insert plan parts from this plan library into the current plan. We prove this set of plan operators to be complete.
    Generalizing the refinement planning approach, we present a template algorithm for both planning and replanning using the ARF and its plan library and plan operators. Finally, we show that existing (re)planning methods and heuristics nicely fit into this framework.

    @article{ krogt03wias,
      author    = {Roman van der Krogt and Mathijs de Weerdt and Cees Witteveen},
      title     = {A resource based framework for planning and replanning},
      year      = 2003,
      journal   = {Web Intelligence and Agent Systems},
      volume    = {1},
      number    = {3/4},
      pages     = {173--186},
      publisher = {{IOS} Press},
      address   = {Amsterdam, The Netherlands}
    }
  2. R.P.J. van der Krogt and M.M. de Weerdt. The Two Faces of Plan Repair. In Proceedings of the Sixteenth Belgium-Netherlands Conference on Artificial Intelligence (BNAIC-04), 2004.
    [ view abstract | bibtex ]

    Plan repair has two faces. Alternately, a plan repair method looks like a planning method, or looks like a method that does exactly the opposite, i.e., removing actions from a plan. We propose a general framework for plan repair that shows the relation between these two alternating steps. Any plan repair method has this property. This claim is supported by showing how a number of plan repair systems fit into the presented framework. One of the advantages of a general framework is that it helps to understand existing techniques and improve upon them. As an example of this, we present a novel heuristic for plan repair that can make use of existing planning heuristics. Some initial results are provided that indicate that this heuristic is competitive with existing plan repair methods.

    @inproceedings{ krogt04bnaic,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {The two faces of plan repair},
      year      = 2004,
      booktitle = {Proceedings of the Sixteenth Belgium-Netherlands Conference
                   on Artificial Intelligence ({BNAIC}-04)},
      pages     = {147--154},
      location  = {Groningen, The Netherlands}
    }
  3. R.P.J. van der Krogt. Unrefinement Planning: Extending Refinement Planners with Plan Repair Capabilities. In Proceedings of the 23rd Annual Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-04), 2004.
    [ view abstract | bibtex ]

    Kambhampati?s refinement planning framework provides a unifying view on planning algorithms. It shows how a planning problem can be solved by successively applying a refinement operator, which adds more and more detail to the plan. In this paper, we show how this framework can be extended to include plan repair capabilities. This extension relies on the inclusion of unrefinement operators, that remove obsolete or obstructing actions from the plan.
    Based on this general plan repair framework, we develop a generic plan repair heuristic. This heuristic consists of a new unrefinement strategy, and it can make use of existing planning heuristics as the refinement operator. The unrefinement strategy deteriorates a plan in a number of ways, by removing certain combinations of actions. The planning heuristic is then used to find the most promising candidate, which is then given to the planner as the initial partial plan to refine. The big advantage of the heuristic is that it allows to employ existing planning heuristics. This way, it can not only make use of advances in planning technology, but it can also be used to extend existing planners, giving them plan repair capabilities.
    The performance of the heuristic is demonstrated by adapting an existing planner, and comparing the results with planning from scratch and a plan adaptation system. Experiments are presented that show that the new heuristic is very competitive with the other systems.

    @inproceedings{ krogt04plansig,
      author    = {Roman van der Krogt},
      title     = {Unrefinement Planning: Extending Refinement Planners with Plan Repair Capabilities},
      year      = 2004,
      booktitle = {Proceedings of the 23rd Annual Workshop of the UK Planning and Scheduling
                   Special Interest Group ({PlanSIG}-04)},
      pages     = {192--200},
      location  = {Cork, Ireland}
    }
    
  4. R.P.J. van der Krogt and M.M. de Weerdt, Plan Repair: A Framework and a New Heuristic with Applications to Logistics. In Proceedings of the 8th TRAIL Congress, 2004.
    [ view abstract | bibtex ]

    Planning can be a valuable tool for supporting a wide array of real-world problems, such as logistics, manufacturing and control. However, these applications are often highly dynamic, resulting in plans that require updating. In such situations, plan repair methods can be used to adapt the plan.
    In this paper, we propose a general framework for plan repair. This framework is based on an existing general framework for planning, the so-called refinement planning approach. One of the advantages of a general framework is that it helps to understand existing techniques and improve upon them. As an example of this, we show how we can extend an existing planning method into a system that can also deal with plan repair problems. This system is tested on a number of benchmark problems that deal with abstract transportation problems.

    @inproceedings{ krogt04trail,
      author    = {Roman van der Krogt and Mathijs de Weerdt},
      title     = {Plan Repair: A Framework and a New Heuristic with Applications to Logistics},
      year      = 2004,
      booktitle = {Proceedings of the eighth TRAIL Congress},
      location  = {Rotterdam, The Netherlands}
    }

2003

  1. R.P.J. van der Krogt, M.M. de Weerdt, and C. Witteveen. Exploiting Opportunities using Planning Graphs. In Proceedings of the 22nd Annual Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-03), 2003
    [ view abstract | bibtex ]

    Opportunities arise in planning when changes in the environment make new propositions available to the planner. Replanning methods often focus only on the negative effects that changes in the environment have and therefore do not apply well. This paper introduces a method that is specifically focused on the opportunity problem. This method is based on the potential graph structure. This potential graph is basically an annotated version of the planning graph as used in many contemporary planners. We show how this potential graph can be used to discover the positive impact of opportunities. This information can then be used to improve upon the plan by exploiting such opportunities. The benefit of this method over standard planning techniques is two-fold: firstly, it can be used in an any-time algorithm. That is, when only little time is available, little improvements are quickly found. With more time available, greater improvements may be found. Secondly, this technique helps us focus on those parts of the plan that might be improved. Other parts are not changed, which greatly adds to the efficiency of the method. The applicability of the method is demonstrated by some initial experiments.

    @inproceedings{ krogt03plansig,
      author    = {Roman van der Krogt and Mathijs de Weerdt and Cees Witteveen},
      title     = {Exploiting Opportunities using Planning Graphs},
      year      = 2003,
      booktitle = {Proceedings of the 22nd Workshop of the {UK} Planning and
                   Scheduling Special Interest Group ({PLANSIG}-03)},
      editor    = {Julie Porteous},
      pages     = {125 -- 136},
      location  = {Glasgow, UK}
    }
  2. M.M. de Weerdt, R.P.J. van der Krogt, and C. Witteveen. Resource Based Multi Agent Plan Merging: framework and application. In Proceedings of the 22nd Annual Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-03), 2003.
    [ view abstract | bibtex ]

    We discuss a resource-based planning framework where agents are able to merge plans by exchanging resources. In this framework, plans are specified as structured objects composed of resource consuming and resource producing processes (actions). A plan itself can also be conceived as a process consuming input resources and producing output resources. A plan can be improved if we can remove actions from it while maintaining goal realizability.We describe a reduction property that specifies how one agent can improve its plan by using (free) resources from another agent in such a way that goal realizability is preserved. The plan-merging algorithm we use to specify plan merging in a multi-agent context is an iterative, distributed, any-time application of this reduction property. The performance of this algorithm has been evaluated using a planning data set obtained from a taxi company. The quality of the algorithm is measured by the decrease of the total distance driven by all taxis. By allowing passengers to share rides, we create a trade-off between the additional travel time of passengers and the total drive distance. Allowing passengers to be a few minutes later at their destination and share rides, a significant improvement of the plans can be obtained (from 5% up to 30% reduction of the taxi driving distance).

    @inproceedings{ weerdt03plansig,
      author    = {Mathijs de Weerdt and Roman van der Krogt and Cees Witteveen},
      title     = {Resource Based Multi Agent Plan Merging: Framework and
                   Application},
      year      = 2003,
      booktitle = {Proceedings of the 22nd Workshop of the {UK} Planning and
                   Scheduling Special Interest Group ({PLANSIG}-03)},
      editor    = {Julie Porteous},
      pages     = {218 -- 233},
      location  = {Glasgow, UK}
    }
  3. M.M. de Weerdt, R.P.J. van der Krogt, and J. Zutt. Plan Merging: Experimental Results. In Proceedings of the Fifteenth Belgium-Netherlands Conference on Artificial Intelligence (BNAIC-03), 2003.
    [ view abstract | bibtex ]

    In this paper we discuss the results of a plan merging algorithm. This algorithm coordinates the plans of multiple, autonomous agents, each able to independently find a plan. This algorithm is evaluated using realistic data from a taxi company. We show that when we allow passengers to be a few minutes later at their destination and share rides, we can obtain more than 5% reduction of the taxi driving distance. When we allow for a delay of 15 inutes (a common amount of time in subsidized transport) we can gain up to 30%.

    @inproceedings{ weerdt03bnaic,
      author    = {Mathijs de Weerdt and Roman van der Krogt and Jonne Zutt},
      title     = {Plan Merging: Experimental Results},
      year      = 2003,
      booktitle = {Proceedings of the Fifteenth Belgium-Netherlands Conference
                   on Artificial Intelligence ({BNAIC}-03)},
      editor    = {Tom Heskes and Peter Lucas and Louis Vuurpijl and Wim
                   Wiegerinck},
      pages     = {315 -- 322},
      location  = {Nijmegen, The Netherlands}
    }
  4. R.P.J. van der Krogt, M.M. de Weerdt, and C. Witteveen. A resource based framework for planning and replanning. In Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology (IAT-03), 2003. (IEEE link) (Nominated for best paper award.)
    [ view abstract | bibtex ]

    We discuss a rigorous unifying framework for both planning and replanning, extending an existing logic-based approach to resource-based planning. The primitive concepts in this Action Resource Framework (ARF) are actions and resources. Actions consume and produce resources. Plans are structures composed of actions, resource facts and an explicit dependency function specifying their interrelationships. In this framework, both planning and replanning are conceived as plan transformation processes accomplished by applying sequences of operations on plans. For this, we introduce operators for plan transformation and define the concept of a plan library. Using a refinement planning template, we show how some existing (re)planning methods and heuristics can be described as special cases of this framework. The advantage of the framework is that it offers a unifying view on planning and replanning.

    @inproceedings{ krogt03iat,
      author    = {Roman van der Krogt and Mathijs de Weerdt and Cees Witteveen},
      title     = {A resource based framework for planning and replanning},
      year      = 2003,
      booktitle = {Proceedings of the {IEEE}/{WIC} International Conference on
                   Intelligent Agent Technology ({IAT}-03)},
      editor    = {Jiming Liu and Boi Faltings and Ning Zhong and Ruqian Lu and
                   Toyoaki Nishida},
      pages     = {247 -- 253},
      location  = {Halifax, Canada},
      publisher = {{IEEE} Computer Society},
      address   = {Los Alamitos, CA}
    }

2002

  1. M.M. de Weerdt, R.P.J. van der Krogt. A Method to Integrate Planning and Coordination. An invited talk for the AAAI Workshop on Planning with and for Multi-agent Systems, pp. 83-88, 2002.
    [ view abstract | bibtex ]

    Multi-agent planning involves finding a plan for each agent in a gorup where the goals, the actions and the initial resources are distributed over these autonomous agents. An algorithm is given for multi-agent planning that constructs coordinated agent plans distributedly. Instead of designing a planning algorithm and a coordination method separately, this algorithm integrates planning and coordination.
    The presented multi-agent planning algorithm is based on the idea of several forward heuristic planners that run in parallel. These planners are coordinated by communicating side-products and services via a blackboard.

    Bibtex not available yet

  2. R.P.J. van der Krogt, A.Bos, and C. Witteveen. Replanning in a Resource-based Framework. In Multi-Agent-Systems and Applications II: 9th ECCAI-ACAI/EASSS 2001, AEMAS 2001, HoloMAS 2001. Selected Revised Papers, pp. 148-158, 2002. (Springer link)
    [ view abstract | bibtex ]

    An important aspect of agents is how they construct a plan to reach their goals. Since most agents live in a dynamic environment, they also will often be confronted with situations in which the plans they constructed to reach their goals are no longer feasible. In such situations, agents have to change their plan to deal with the new environment. In this paper we describe such a replanning process using a computational framework, consisting of resources and actions to represent the planned activities of an agent.

    Bibtex not available yet

  3. L.D. Aronson, R.P.J. van der Krogt, C. Witteveen, and J.Zutt. Automated Transport Planning Using Agents. In Proceedings of the International Congress on Freight Transport Automation and Multimodality, pp. 1-19, 2002.
    [ view abstract | bibtex ]

    Modern transportation problems are highly dynamic and time critical. A planning system for transportation problems therefore must include efficient and flexible incident management and replanning strategies.
    In this paper we present a general agent-based framework for highly dynamic order-based transportation planning problems. The basis of our framework is a distribution of responsibilities between a strategic planner and several tactical planners (one for each vehicle). The strategic planner is responsible for task allocation of orders and tries to maximise the amount of time that can be used for time-shifting parts of the plan, thus trying to obtain a flexible schedule in which new orders can easily be fit in. The tactical planners are responsible for individual route planning, execution of the orders and handling of small incidents. If incidents have consequences for other tactical planners or result in a failure to deliver an order, a tactical planner reports this failure back to the strategic planner.
    In computing routes the tactical planners make use of a smart infrastructure. Roads and crossings will provide information about the traffic of other vehicles and these infrastructure agents compute time windows for passing sections on the route. This information is used by a route-planning heuristic (D**) to determine a feasible route. Finally, this route then is announced to the infrastructure in order to make reservations for route sections and prevent collisions.

    Bibtex not available yet

  4. R.P.J. van der Krogt, L.D. Aronson, and J. Zutt. Incident Management in Transport Planning. In Proceedings of the 7th TRAIL Congress, pp. 281-303, 2002.
    [ view abstract | bibtex ]

    In this paper we introduce an agent-based framework which can be used in a dynamic transport planning environent. Incidents are managed at two levels: a tactical level and an operational level. Agents generating multi-vehicle plans belong to the tactical level, whereas agents operating vehicles belong to the operational level. Agents at both levels are equipped with incident management techniques to deal with incidents occuring at their level. The purpose is to create a transport planning system which is both robust and efficient.

    Bibtex not available yet

  5. R.P.J. van der Krogt, L.D. Aronson, N. Roos, C. Witteveen, and J. Zutt. Tactical Planning using Heuristics. In Proceedings of the BNAIC, 2002, pp. 187-194.
    [ view abstract | bibtex ]

    Modern transportation problems are highly dynamic and time critical. A planning system for transportation problems must therefore include efficient and flexible planning and replanning strategies. In this paper we introduce a general agent-based framework for highly dynamic order-based transportation planning problems where a tactical planner and several operational planners (one for each transport agent) are distinguished. In particular we discuss the role of the tactical planner responsible for dynamic task allocation of orders and we present some preliminary results of task allocation heuristics in such dynamic environments.

    Bibtex not available yet

  6. J. Zutt, L.D. Aronson, R.P.J. van der Krogt, N. Roos, and C. Witteveen. Multi-Agent Transport Planning. In Proceedings of the BNAIC, 2002, pp. 387-394.
    [ view abstract | bibtex ]

    This paper describes the operational planning of complex multi-agent transportation problems. Based on a simple hierarchical agent-based model, agents execute transportation orders specified by clients. Hatzack and Nebel pointed out a correspondence with job shop scheduling. Using this correspondence they are able to use scheduling heuristics to compute safe traffic flows, using a fixed route for each transportation agent. We adopt their approach and show a significant improvement in case alternative routes are considered by the agents.

    Bibtex not available yet

2001

  1. R.P.J. van der Krogt, A. Bos, and C. Witteveen. Replanning in a Resource-based Framework. In Proceedings of Multi-Agent Systems and Applications - ACAI 2001 & EASSS 2001 Student Sessions, pp. 48-55, 2001.
    [ view abstract | bibtex ]

    An important aspect of agents is how they construct a plan to reach their goals. However, since most agents live in a dynamic environment, they will often be confronted with situations in which their plans are no longer feasible or optimal. In such situations, agents have to change their plan to deal with the new environment. In this paper we descrive such a replanning process using a computational framework, consisting of so-called resources and actions to represent the planned activities of an agent. A (complete) algorithm is introduced which can be used to replan the activities, taking the new environment into account.

    Bibtex not available yet

  2. R.P.J. van der Krogt, A. Bos, and C. Witteveen. Plan Fragment Libraries. In Proceedings of the BNAIC, 2001, pp. 399-406.
    [ view abstract | bibtex ]

    One of the important aspects of agents is their ability to contruct plans to reach their goals. This ability allows them to operate autonomously, without the intervention of a (human) operator. Unfortunately, the planning process is a very complex task. One way to reduce this complexity is to use case-based planning, which stores past plans and adapts these past plans to new situations. We do not want to store complete plans, but smaller, frequently occurring combinations of actions that solve only a few number of goals. We will call such a combination a plan fragment. These plan fragments can then be combined to form a plan.
    These plan fragments are stored in and retrieved from a library which is accessible to the agent. This paper focuses on such plan fragment libraries. We will show a simple algorithm that uses such a library to create plans. We also investigate a way to order the plan fragments according to some preference relation. The initial algorithm is extended to one that can use such an ordered library in an efficient way, making use of tabus.

    Bibtex not available yet

2000

  1. R.P.J. van der Krogt, A. Bos, M.M. de Weerdt, and C. Witteveen. An Algorithm for Replanning. In Proceedings of the BNAIC, 2000, pp. 21-28.
    [ view abstract | bibtex ]

    An important aspect of agents is how they construct a plan to reach their goals. However, since most real-world agents live in a dynamic environment, often they will be confronted with situations where their plans are no longer feasible or optimal. In such situations, agents have to change their plan to deal with the new environment. In this paper we describe such a replanning process using a computational framework, consisting of so-called resources and skills, to represent the planned activities of an agent. An algorithm is introduced which can be used to replan the activities, taking the new environment into account.

    @inproceedings{ krogt00bnaic,
      author    = {Roman van der Krogt and Andre Bos and Mathijs de Weerdt and Cees Witteveen},
      title     = {An Algorithm for Replanning},
      year      = 2000,
      booktitle = {Proceedings of the Twelfth Belgium-Netherlands Conference
                   on Artificial Intelligence ({BNAIC}-00)},
      pages     = {21 -- 28},
      location  = {Kaatsheuvel, The Netherlands}
    }