1,503 research outputs found
Optimal and heuristic approaches for constrained flight planning under weather uncertainty
No full textAircraft flight planning is impacted by weather uncertainties. Existing approaches to flight planning are either deterministic and load additional fuel to account for uncertainty, or probabilistic but have to plan in 4D space. If constraints are imposed on the flight plan these methods provide no formal guarantees that the constraints are actually satisfied. We investigate constrained flight planning under weather uncertainty on discrete airways graphs and model this problem as a Constrained Stochastic Shortest Path (C-SSP) problem. Transitions are generated on-the-fly by the underlying aircraft performance model. As this prevents us from using off-the-shelf C-SSP solvers, we generalise column-generation methods stemming from constrained deterministic path planning to the probabilistic case. This results in a novel method which is complete but computationally expensive. We therefore also discuss deterministic and heuristic approaches which average over weather uncertainty and handle constraints by scalarising a multi-objective cost function. We evaluate and compare these approaches on real flight routes subject to real weather forecast data and a realistic aircraft performance model.This work was supported by the Airbus R&T project Dynamic Operations Optimization Under Uncertainty for Air-craft and Satellite Applications Florian Geißer, Sylvie Thiebaux and Felipe Trevizan werealso partially supported by ARC project DP180103446,On-line planning for constrained autonomous agents in an uncertain worl
Talking Trucks: Decentralized Collaborative Multi-Agent Order Scheduling for Self-Organizing Logistics
No full textLogistics planning is a complex optimization problem involving multiple decision makers. Automated scheduling systems offer support to human planners; however state-of-the-art approaches often employ a centralized control paradigm. While these approaches have shown great value, their application is hindered in dynamic settings with no central authority. Motivated by real-world scenarios, we present a decentralized approach to collaborative multi-agent scheduling by casting the problem as a Distributed Constraint Optimization Problem (DCOP). Our model-based heuristic approach uses message passing with a novel pruning technique to allow agents to cooperate on mutual agreement, leading to a near-optimal solution while offering low computational costs and flexibility in case of disruptions. Performance is evaluated in three real-world field trials with a logistics carrier and compared against a centralized model-free Deep Q-Network (DQN)-based Reinforcement Learning (RL) approach, a Mixed-Integer Linear Programming (MILP)-based solver, and both human and heuristic baselines. The results demonstrate that it is feasible to have virtual agents make autonomous decisions using our DCOP method, leading to an efficient distributed solution. To facilitate further research in Self-Organizing Logistics (SOL), we provide a novel real-life dataset.Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Algorithmic
Recherche de leptoquarks, de leptogluons et de squarks dans l'experience H1 aupres du collisionneur ep HERA
No full textIn defense of PDDL axioms
No full textThere is controversy as to whether explicit support for PDDL-like axioms and derived predicates is needed for planners to handle real-world domains effectively. Many researchers have deplored the lack of precise semantics for such axioms, while others have argued that it might be best to compile them away. We propose an adequate semantics for PDDL axioms and show that they are an essential feature by proving that it is impossible to compile them away if we restrict the growth of plans and domain descriptions to be polynomial. These results suggest that adding a reasonable implementation to handle axioms inside the planner is beneficial for the performance. Our experiments confirm this suggestion.The second and third author would like to acknowledge DFG for its support. The second author had been supported by funds from DFG as part of the project HEU-PLAN II (Ne 623/4-2). The third author would also like to acknowledge the European Union for its support of the FP6 project Cosy (FP6-004250-IP). The first author would like to acknowledge National ICT Australia (NICTA) and the Australian Research Council (ARC) for their support. NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the ARC.Peer-reviewe
I-dual: Solving Constrained SSPs via heuristic search in the dual space
No full textWe consider the problem of generating optimal
stochastic policies for Constrained Stochastic
Shortest Path problems, which are a natural
model for planning under uncertainty for resourcebounded
agents with multiple competing objectives.
While unconstrained SSPs enjoy a multitude
of efficient heuristic search solution methods with
the ability to focus on promising areas reachable
from the initial state, the state of the art for constrained
SSPs revolves around linear and dynamic
programming algorithms which explore the entire
state space. In this paper, we present i-dual, the first
heuristic search algorithm for constrained SSPs. To
concisely represent constraints and efficiently decide
their violation, i-dual operates in the space
of dual variables describing the policy occupation
measures. It does so while retaining the ability to
use standard value function heuristics computed by
well-known methods. Our experiments show that
these features enable i-dual to achieve up to two
orders of magnitude improvement in run-time and
memory over linear programming algorithms.This research was funded by AFOSR grant FA2386-15-14015
Tableaux for Policy Synthesis for MDPs with PCTL* Constraints
No full textMarkov decision processes (MDPs) are the standard formalism for modelling sequential decision making in stochastic environments. Policy synthesis addresses the problem of how to control or limit the decisions an agent makes so that a given specification is met. In this paper we consider PCTL*, the probabilistic counterpart of CTL*, as the specification language. Because in general the policy synthesis problem for PCTL* is undecidable, we restrict to policies whose execution history memory is finitely bounded a priori. Surprisingly, no algorithm for policy synthesis for this natural and expressive framework has been developed so far. We close this gap and describe a tableau-based algorithm that, given an MDP and a PCTL* specification, derives in a non-deterministic way a system of (possibly nonlinear) equalities and inequalities. The solutions of this system, if any, describe the desired (stochastic) policies. Our main result in this paper is the correctness of our method, i.e., soundness, completeness and termination.This research was funded by AFOSR grant FA2386-15-1-4015
An Incremental Multimodal Realizer for Behavior Co-Articulation and Coordination
No full textvan Welbergen H, Reidsma D, Kopp S. An Incremental Multimodal Realizer for Behavior Co-Articulation and Coordination. In: Nakano Y, Neff M, Paiva A, Walker M, eds. Intelligent virtual agents : 12th international conference, proceedings. Lecture Notes in Computer Science. Vol 7502. Berlin ; Heidelberg: Springer; 2012: 175-188
Study of B-meson decays to eta K-c(*), eta(c)(2S)K(*), and eta(c)gamma K(*)
No full textWe study two-body B-meson decays to a charmonium state (eta(c), eta(c)(2S) or h(c)) and a K+ or K-*0(892) meson using a sample of 349 fb(-1) of data collected with the BABAR detector at the PEP-II asymmetric-energy B Factory at the Stanford Linear Accelerator Center. We measure B(B-0 -> eta K-c*(0)) = (5.7 +/- 0.6(stat) +/- 0.9(syst)) x 10(-4), B(B-0 -> eta(c)(2S)K*(0)) h(c)K(+)) x B(h(c) -> eta(c)gamma) h(c)K*(0)) x B(h(c) -> eta(c)gamma) K (K) over bar pi) = (1.9 +/- 0.4(stat) +/- 1.1(syst))%. We also measure the mass and width of the eta(c) meson to be m(eta(c)) = (2985.8 +/- 1.5(stat) +/- 3.1(syst)) MeV/c(2) and Gamma(eta(c)) = (36.3(-3.6)(+3.7)(stat) +/- 4.4(syst)) MeV
RAO*: An algorithm for chance-constrained POMDP's
No full textAutonomous agents operating in partially observable stochastic environments often face the problem of optimizing expected performance while bounding the risk of violating safety constraints. Such problems can be modeled as chance-constrained POMDP’s (CCPOMDP’s). Our first contribution is a systematic derivation of execution risk in POMDP domains, which improves upon how chance constraints are handled in the constrained POMDP literature. Second, we present RAO∗, a heuristic forward search algorithm producing optimal, deterministic, finite-horizon policies for CCPOMDP’s. In addition to the utility heuristic, RAO∗ leverages an admissible execution risk heuristic to quickly detect and prune overly-risky policy branches. Third, we demonstrate the usefulness of RAO∗ in two challenging domains of practical interest: power supply restoration and autonomous science agents.This research was partially funded by AFOSR grants FA95501210348 and FA2386-15-1-4015, the SUTD-MIT Graduate Fellows Program, and NICTA. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program
Study of (B)over-bar ->Xi(c)(Lambda)over-bar(c)(-) and (B)over-bar ->Lambda(+)(c)(Lambda)over-bar(c)(-)(K)over-bar decays at BABAR
No full textWe report measurements of B-meson decays into two- and three-body final states containing two charmed baryons using a sample of 230x10(6) Upsilon(4S)-> B (B) over bar decays. We find significant signals in two modes, measuring branching fractions B(B-->Lambda(+)(c)(Lambda) over bar K--(c)-)=(1.14 +/- 0.15 +/- 0.17 +/- 0.60)x10(-3) and B(B-->Xi(0)(c)(Lambda) over bar (-)(c))xB(Xi(0)(c)->Xi(-)pi(+))=(2.08 +/- 0.65 +/- 0.29 +/- 0.54)x10(-5), where the uncertainties are statistical, systematic, and from the branching fraction B(Lambda(+)(c)-> pK(-)pi(+)), respectively. We also set upper limits at the 90% confidence level on two other modes: B((B) over bar (0)->Xi(+)(c)(Lambda) over bar (-)(c))xB(Xi(+)(c)->Xi(-)pi(+)pi(+))Lambda(+)(c)(Lambda) over bar (-)(c)(K) over bar (0))Lambda(+)(c)(Lambda) over bar K--(c)-
- …
