6 Search Results for "Durfee, Edmund H."

Document
DOI: 10.4230/LITES-v005-i001-a001
Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions

Authors: Bader Naim Alahmad and Sathish Gopalakrishnan

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.
Cite as

Bader Naim Alahmad and Sathish Gopalakrishnan. Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 01:1-01:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{alahmad_et_al:LITES-v005-i001-a001,
  author =	{Alahmad, Bader Naim and Gopalakrishnan, Sathish},
  title =	{{Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a001},
  doi =		{10.4230/LITES-v005-i001-a001},
  annote =	{Keywords: Mixed criticalities, Probability distribution, Real time systems, Scheduling, Chance constrained Markov decision process, Linear programming, Randomized policy}
}
Document
DOI: 10.4230/DagSemProc.08461.5
Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions

Authors: Lonneke Mous, Valentin Robu, and Han La Poutre

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
The exposure problem appears whenever an agent with complementary valuations bids to acquire a bundle of items sold sequentially, in separate auctions. In this talk, we review a possible solution that can help solve this problem, which involves selling options for the items, instead of the items themselves. We provide a brief overview of the state of the art in this field and discuss, based on our recent results, under which conditions using option mechanisms would be desirable for both buyers and sellers, by comparison to direct auctioning of items. We conclude with a brief discussion of further research directions in this field, as well as the relation to other techniques proposed to address the problem, such as leveled commitment mechanisms.
Cite as

Lonneke Mous, Valentin Robu, and Han La Poutre. Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{mous_et_al:DagSemProc.08461.5,
  author =	{Mous, Lonneke and Robu, Valentin and La Poutre, Han},
  title =	{{Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--35},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.5},
  URN =		{urn:nbn:de:0030-drops-18724},
  doi =		{10.4230/DagSemProc.08461.5},
  annote =	{Keywords: Options, sequential auctions, multi-agent systems, exposure problem, bidding strategies, mechanism design, leveled commitment}
}
Document
DOI: 10.4230/DagSemProc.08461.1
08461 Abstracts Collection – Planning in Multiagent Systems

Authors: Jürgen Dix, Edmund H. Durfee, and Cees Witteveen

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
From the 9th of November to the 14th of November 2008 the Dagstuhl Seminar 08461 '`Planning in Multiagent Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Jürgen Dix, Edmund H. Durfee, and Cees Witteveen. 08461 Abstracts Collection – Planning in Multiagent Systems. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dix_et_al:DagSemProc.08461.1,
  author =	{Dix, J\"{u}rgen and Durfee, Edmund H. and Witteveen, Cees},
  title =	{{08461 Abstracts Collection – Planning in Multiagent Systems}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.1},
  URN =		{urn:nbn:de:0030-drops-18740},
  doi =		{10.4230/DagSemProc.08461.1},
  annote =	{Keywords: Multi-agent systems, AI-planning, coordination, robustness, temporal planning}
}
Document
DOI: 10.4230/DagSemProc.08461.2
08461 Executive Summary – Planning in Multi-Agent Systems

Authors: Jürgen Dix, Edmund H. Durfee, and Cees Witteveen

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
Planning in Multiagent Systems, or Multiagent Planning (MAP for short), considers the planning problem in the context of multiagent systems. It extends traditional AI planning to domains where multiple agents are involved in a plan and need to act together. Research in multiagent planning is promising for real-world problems: on one hand, AI planning techniques provide powerful tools for solving problems in single agent settings; on the other hand, multiagent systems, which have made significant progress over the past few years, are recognized as a key technology for tackling complex problems in realistic application domains. The motivation for this seminar is thus to bring together researchers working on these different fields in AI planning and multiagent systems to discuss the central topics mentioned above, to identify potential opportunities for coordination, and to develop benchmarks for future research in multiagent planning.
Cite as

Jürgen Dix, Edmund H. Durfee, and Cees Witteveen. 08461 Executive Summary – Planning in Multi-Agent Systems. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dix_et_al:DagSemProc.08461.2,
  author =	{Dix, J\"{u}rgen and Durfee, Edmund H. and Witteveen, Cees},
  title =	{{08461 Executive Summary – Planning in Multi-Agent Systems }},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.2},
  URN =		{urn:nbn:de:0030-drops-18739},
  doi =		{10.4230/DagSemProc.08461.2},
  annote =	{Keywords: Multi-agent systems, AI-planning, coordination, robustness, temporal planning}
}
Document
DOI: 10.4230/DagSemProc.08461.3
ASODPOP: Making Open DPOP Asynchronous

Authors: Brammert Ottens

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
In this paper we show how ODPOP can be adapted to an asynchronous environment where agents might have to decide their values before the algorithm has ended, giving us Asynchronous ODPOP (ASODPOP). We have compared the algorithm with both ADOPT and distributed local search (DSA). Compared to ADOPT we show that our approach sends fewer messages, converges to a reasonable solution faster, and uses an equal amount of NCCCs. We also show that this convergence is much faster than local search, whilst the solution that local search converges to is far from optimal.
Cite as

Brammert Ottens. ASODPOP: Making Open DPOP Asynchronous. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ottens:DagSemProc.08461.3,
  author =	{Ottens, Brammert},
  title =	{{ASODPOP: Making Open DPOP Asynchronous}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.3},
  URN =		{urn:nbn:de:0030-drops-18714},
  doi =		{10.4230/DagSemProc.08461.3},
  annote =	{Keywords: DCOP, Logistics, Planning, Coordination}
}
Document
DOI: 10.4230/DagSemProc.08461.4
Creating incentives to prevent execution failures: an extension of VCG mechanism

Authors: Yingqian Zhang and Mathijs de Weerdt

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
When information or control in a multiagent planning system is private to the agents, they may misreport this information or refuse to execute an agreed outcome, in order to change the resulting end state of such a system to their benefit. In some domains this may result in an execution failure. We show that in such settings VCG mechanisms lose truthfulness, and that the utility of truthful agents can become negative when using VCG payments (i.e., VCG is not strongly individually rational). To deal with this problem, we introduce an extended payment structure which takes into account the actual execution of the promised outcome. We show that this extended mechanism can guarantee a nonnegative utility and is (i) incentive compatible in a Nash equilibrium, and (ii) incentive compatible in dominant strategies if and only if all agents can be verified during execution.
Cite as

Yingqian Zhang and Mathijs de Weerdt. Creating incentives to prevent execution failures: an extension of VCG mechanism. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:DagSemProc.08461.4,
  author =	{Zhang, Yingqian and de Weerdt, Mathijs},
  title =	{{Creating incentives to prevent execution failures: an extension of VCG mechanism}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.4},
  URN =		{urn:nbn:de:0030-drops-18705},
  doi =		{10.4230/DagSemProc.08461.4},
  annote =	{Keywords: Mechanism design, multiagent planning}
}
  • Refine by Author
  • 2 Dix, Jürgen
  • 2 Durfee, Edmund H.
  • 2 Witteveen, Cees
  • 1 Alahmad, Bader Naim
  • 1 Gopalakrishnan, Sathish
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Markov processes
  • 1 Software and its engineering → Real-time schedulability
  • 1 Software and its engineering → Real-time systems software

  • Refine by Keyword
  • 2 AI-planning
  • 2 Multi-agent systems
  • 2 coordination
  • 2 robustness
  • 2 temporal planning
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 5 2009
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact