Arrow Research search

Author name cluster

Patrick Doherty 0001

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

25 papers
1 author row

Possible papers

25

UAI Conference 2019 Conference Paper

Real-Time Robotic Search using Structural Spatial Point Processes

  • Olov Andersson
  • Per Sidén
  • Johan Dahlin
  • Patrick Doherty 0001
  • Mattias Villani

Aerial robots hold great potential for aiding Search and Rescue (SAR) efforts over large areas, such as during natural disasters. Traditional approaches typically search an area exhaustively, thereby ignoring that the density of victims varies based on predictable factors, such as the terrain, population density and the type of disaster. We present a probabilistic model to automate SAR planning, with explicit minimization of the expected time to discovery. The proposed model is a spatial point process with three interacting spatial fields for i) the point patterns of persons in the area, ii) the probability of detecting persons and iii) the probability of injury. This structure allows inclusion of informative priors from e. g. geographic or cell phone traffic data, while falling back to latent Gaussian processes when priors are missing or inaccurate. To solve this problem in real-time, we propose a combination of fast approximate inference using Integrated Nested Laplace Approximation (INLA), and a novel Monte Carlo tree search tailored to the problem. Experiments using data simulated from real world Geographic Information System (GIS) maps show that the framework outperforms competing approaches, finding many more injured in the crucial first hours.

Details

ICAPS Conference 2018 Conference Paper

Planning with Temporal Uncertainty, Resources and Non-Linear Control Parameters

  • Mikael Nilsson
  • Jonas Kvarnström
  • Patrick Doherty 0001

We consider a general and industrially motivated class of planning problems involving a combination of requirements that can be essential to autonomous robotic systems planning to act in the real world: Support for temporal uncertainty where nature determines the eventual duration of an action, resource consumption with a non-linear relationship to durations, and the need to select appropriate values for control parameters that affect time requirements and resource usage. To this end, an existing planner is extended with support for Simple Temporal Networks with Uncertainty, Timed Initial Literals, and temporal coverage goals. Control parameters are lifted from the main combinatorial planning problem into a constraint satisfaction problem that connects them to resource usage. Constraint processing is then integrated and interleaved with verification of temporal feasibility, using projections for partial temporal awareness in the constraint solver.

Details

JELIA Conference 2016 Conference Paper

Iteratively-Supported Formulas and Strongly Supported Models for Kleene Answer Set Programs - (Extended Abstract)

  • Patrick Doherty 0001
  • Jonas Kvarnström
  • Andrzej Szalas

Abstract In this extended abstract, we discuss the use of iteratively-supported formulas (ISFs) as a basis for computing strongly-supported models for Kleene Answer Set Programs (ASP \(^{K}\) ). ASP \(^{K}\) programs have a syntax identical to classical ASP programs. The semantics of ASP \(^{K}\) programs is based on the use of Kleene three-valued logic and strongly-supported models. For normal ASP \(^{K}\) programs, their strongly supported models are identical to classical answer sets using stable model semantics. For disjunctive ASP \(^{K}\) programs, the semantics weakens the minimality assumption resulting in a classical interpretation for disjunction. We use ISFs to characterize strongly-supported models and show that they are polynomially bounded.

Details

ICRA Conference 2016 Conference Paper

Model-predictive control with stochastic collision avoidance using Bayesian policy optimization

  • Olov Andersson
  • Mariusz Wzorek
  • Piotr Rudol
  • Patrick Doherty 0001

Robots are increasingly expected to move out of the controlled environment of research labs and into populated streets and workplaces. Collision avoidance in such cluttered and dynamic environments is of increasing importance as robots gain more autonomy. However, efficient avoidance is fundamentally difficult since computing safe trajectories may require considering both dynamics and uncertainty. While heuristics are often used in practice, we take a holistic stochastic trajectory optimization perspective that merges both collision avoidance and control. We examine dynamic obstacles moving without prior coordination, like pedestrians or vehicles. We find that common stochastic simplifications lead to poor approximations when obstacle behavior is difficult to predict. We instead compute efficient approximations by drawing upon techniques from machine learning. We propose to combine policy search with model-predictive control. This allows us to use recent fast constrained model-predictive control solvers, while gaining the stochastic properties of policy-based methods. We exploit recent advances in Bayesian optimization to efficiently solve the resulting probabilistically-constrained policy optimization problems. Finally, we present a real-time implementation of an obstacle avoiding controller for a quadcopter. We demonstrate the results in simulation as well as with real flight experiments.

Details

ICAPS Conference 2014 Conference Paper

EfficientIDC: A Faster Incremental Dynamic Controllability Algorithm

  • Mikael Nilsson
  • Jonas Kvarnström
  • Patrick Doherty 0001

The exact duration of an action generally cannot be predicted in advance. Temporal planning therefore tends to use upper bounds on durations, with the explicit or implicit assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is at home and can eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must then verify that the networks it generates are executable, captured by the property of dynamic controllability. The FastIDC algorithm can do this incrementally during planning. In this paper we show that the FastIDC method can result in traversing part of a temporal network multiple times, with constraints slowly tightening towards their final values. We then present a new algorithm that uses additional analysis together with a different traversal strategy to avoid this behavior. The new algorithm has a guaranteed time complexity lower than that of FastIDC and is proven sound and complete.

Details

TIME Conference 2014 Conference Paper

Incremental Dynamic Controllability in Cubic Worst-Case Time

  • Mikael Nilsson
  • Jonas Kvarnström
  • Patrick Doherty 0001

It is generally hard to predict the exact duration of an action. Uncertainty in durations is often modeled in temporal planning by the use of upper bounds on durations, with the assumption that if an action happens to be executed more quickly, the plan will still succeed. However, this assumption is often false: If we finish cooking too early, the dinner will be cold before everyone is ready to eat. Simple Temporal Problems with Uncertainty (STPUs) allow us to model such situations. An STPU-based planner must verify that the plans it generates are executable, captured by the property of dynamic controllability. The Efficient IDC (EIDC) algorithm can do this incrementally during planning, with an amortized complexity per step of O(n3) but a worst-case complexity per step of O(n4). In this paper we show that the worst-case run-time of EIDC does occur, leading to repeated reprocessing of nodes in the STPU while verifying the dynamic controllability property. We present a new version of the algorithm, EIDC2, which through optimal ordering of nodes avoids the need for reprocessing. This gives EIDC2 a strictly lower worst-case run-time, making it the fastest known algorithm for incrementally verifying dynamic controllability of STPUs.

Details

ICAPS Conference 2013 Conference Paper

Exploiting Fully Observable and Deterministic Structures in Goal POMDPs

  • Håkan Warnquist
  • Jonas Kvarnström
  • Patrick Doherty 0001

When parts of the states in a goal POMDP are fully observable and some actions are deterministic it is possible to take advantage of these properties to efficiently generate approximate solutions. Actions that deterministically affect the fully observable component of the world state can be abstracted away and combined into macro actions, permitting a planner to converge more quickly. This processing can be separated from the main search procedure, allowing us to leverage existing POMDP solvers. Theoretical results show how a POMDP can be analyzed to identify the exploitable properties and formal guarantees are provided showing that the use of macro actions preserves solvability. The efficiency of the method is demonstrated with examples when used in combination with existing POMDP solvers.

Details

ICAPS Conference 2013 Conference Paper

Incremental Dynamic Controllability Revisited

  • Mikael Nilsson
  • Jonas Kvarnström
  • Patrick Doherty 0001

Simple Temporal Networks with Uncertainty (STNUs) allow the representation of temporal problems where some durations are determined by nature, as is often the case for actions in planning. As such networks are generated it is essential to verify that they are dynamically controllable -- executable regardless of the outcomes of uncontrollable durations -- and to convert them to a dispatchable form. The previously published FastIDC algorithm achieves this incrementally and can therefore be used efficiently during plan construction. In this paper we show that FastIDC is not sound when new constraints are added, sometimes labeling networks as dynamically controllable when they are not. We analyze the algorithm, pinpoint the cause, and show how the algorithm can be modified to correctly detect uncontrollable networks.

Details

ICAPS Conference 2010 Conference Paper

Choosing Path Replanning Strategies for Unmanned Aircraft Systems

  • Mariusz Wzorek
  • Jonas Kvarnström
  • Patrick Doherty 0001

Unmanned aircraft systems use a variety of techniques to plan collision-free flight paths given a map of obstacles and no-fly zones. However, maps are not perfect and obstacles may change over time or be detected during flight, which may invalidate paths that the aircraft is already following. Thus, dynamic in-flight replanning is required. Numerous strategies can be used for replanning, where the time requirements and the plan quality associated with each strategy depend on the environment around the original flight path. In this paper, we investigate the use of machine learning techniques, in particular support vector machines, to choose the best possible replanning strategy depending on the amount of time available. The system has been implemented, integrated and tested in hardware-in-the-loop simulation with a Yamaha RMAX helicopter platform.

Details

ECAI Conference 2010 Conference Paper

Iterative Bounding LAO

  • Håkan Warnquist
  • Jonas Kvarnström
  • Patrick Doherty 0001

Iterative Bounding LAO* is a new algorithm for ε-optimal probabilistic planning problems where an absorbing goal state should be reached at a minimum expected cost from a given ini tial state. The algorithm is based on the LAO* algorithm for finding optimal solutions in cyclic AND/OR graphs. The new algorithm uses two heuristics, one upper bound and one lower bound of the optimal cost. The search is guided by the lower bound as in LAO*, while the upper bound is used to prune search branches. The algorithm has a new mechanism for expanding search nodes, and while maintaining the error bounds, it may use weighted heuristics to reduce the size of the explored search space. In empirical tests on benchmark problems, Iterative Bounding LAO* expands fewer search nodes compared to state of the art RTDP variants that also use two-sided bounds.

Details

ECAI Conference 2010 Conference Paper

Stream-Based Reasoning Support for Autonomous Systems

  • Fredrik Heintz
  • Jonas Kvarnström
  • Patrick Doherty 0001

For autonomous systems such as unmanned aerial vehicles to successfully perform complex missions, a great deal of embedded reasoning is required at varying levels of abstraction. To support the integration and use of diverse reasoning modules we have developed DyKnow, a stream-based knowledge processing middleware framework. By using streams, DyKnow captures the incremental nature of sensor data and supports the continuous reasoning necessary to react to rapid changes in the environment. DyKnow has a formal basis and pragmatically deals with many of the architectural issues which arise in autonomous systems. This includes a systematic stream-based method for handling the sense-reasoning gap, caused by the wide difference in abstraction levels between the noisy data generally available from sensors and the symbolic, semantically meaningful information required by many high-level reasoning modules. As concrete examples, stream-based support for anchoring and planning are presented.

Details

ICRA Conference 2010 Conference Paper

Vision-based pose estimation for autonomous indoor navigation of micro-scale Unmanned Aircraft Systems

  • Piotr Rudol
  • Mariusz Wzorek
  • Patrick Doherty 0001

We present a navigation system for autonomous indoor flight of micro-scale Unmanned Aircraft Systems (UAS) which is based on a method for accurate monocular vision pose estimation. The method makes use of low cost artificial landmarks placed in the environment and allows for fully autonomous flight with all computation done on-board a UAS on COTS hardware. We provide a detailed description of all system components along with an accuracy evaluation and a time profiling result for the pose estimation method. Additionally, we show how the system is integrated with an existing micro-scale UAS and provide results of experimental autonomous flight tests. To our knowledge, this system is one of the first to allow for complete closed-loop control and goal-driven navigation of a micro-scale UAS in an indoor setting without requiring connection to any external entities.

Details

IROS Conference 2009 Conference Paper

A stream-based hierarchical anchoring framework

  • Fredrik Heintz
  • Jonas Kvarnström
  • Patrick Doherty 0001

Autonomous systems situated in the real world often need to recognize, track, and reason about various types of physical objects. In order to allow reasoning at a symbolic level, one must create and continuously maintain a correlation between symbols labeling physical objects and the sensor data being collected about them, a process called anchoring. In this paper we present a stream-based hierarchical anchoring framework extending the DyKnow knowledge processing middleware. A classification hierarchy is associated with expressive conditions for hypothesizing the type and identity of an object given streams of temporally tagged sensor data. The anchoring process constructs and maintains a set of object linkage structures representing the best possible hypotheses at any time. Each hypothesis can be incrementally generalized or narrowed down as new sensor data arrives. Symbols can be associated with an object at any level of classification, permitting symbolic reasoning on different levels of abstraction. The approach has been applied to a traffic monitoring application where an unmanned aerial vehicle collects information about a small urban area in order to detect traffic violations.

Details

ICAPS Conference 2008 Conference Paper

A Temporal Logic-Based Planning and Execution Monitoring System

  • Jonas Kvarnström
  • Fredrik Heintz
  • Patrick Doherty 0001

As no plan can cover all possible contingencies, the ability to detect failures during plan execution is crucial to the robustness of any autonomous system operating in a dynamic and uncertain environment. In this paper we present a general planning and execution monitoring system where formulas in an expressive temporal logic specify the desired behavior of a system and its environment. A unified domain description for planning and monitoring provides a solid shared declarative semantics permitting the monitoring of both global and operator-specific conditions. During plan execution, an execution monitor subsystem detects violations of monitor formulas in a timely manner using a progression algorithm on incrementally generated partial logical models. The system has been integrated on a fully deployed autonomous unmanned aircraft system. Extensive empirical testing has been performed using a combination of actual flight tests and hardware-in-the-loop simulations in a number of different mission scenarios.

Details

ICAPS Conference 2006 Conference Paper

Reconfigurable Path Planning for an Autonomous Unmanned Aerial Vehicle

  • Mariusz Wzorek
  • Patrick Doherty 0001

In this paper, we present a motion planning framework for a fully deployed autonomous unmanned aerial vehicle which integrates two sample-based motion planning techniques, Probabilistic Roadmaps and Rapidly Exploring Random Trees. Additionally, we incorporate dynamic reconfigurability into the framework by integrating the motion planners with the control kernel of the UAV in a novel manner with little modification to the original algorithms. The framework has been verified through simulation and in actual flight. Empirical results show that these techniques used with such a framework offer a surprisingly efficient method for dynamically reconfiguring a motion plan based on unforeseen contingencies which may arise during the execution of a plan. The framework is generic and can be used for additional platforms.

Details

JELIA Conference 2004 Conference Paper

Towards a Logical Analysis of Biochemical Pathways

  • Patrick Doherty 0001
  • Steve Kertes
  • Martin Magnusson 0001
  • Andrzej Szalas

Abstract Biochemical pathways or networks are generic representations used to model many different types of complex functional and physical interactions in biological systems. Models based on experimental results are often incomplete, e. g. , reactions may be missing and only some products are observed. In such cases, one would like to reason about incomplete network representations and propose candidate hypotheses, which when represented as additional reactions, substrates, products, would complete the network and provide causal explanations for the existing observations. In this paper, we provide a logical model of biochemical pathways and show how abductive hypothesis generation may be used to provide additional information about incomplete pathways. Hypothesis generation is achieved using weakest and strongest necessary conditions which represent these incomplete biochemical pathways and explain observations about the functional and physical interactions being modeled. The techniques are demonstrated using metabolism and molecular synthesis examples.

Details

TIME Conference 1999 Conference Paper

TALplanner: An Empirical Investigation of a Temporal Logic-Based Forward Chaining Planner

  • Patrick Doherty 0001
  • Jonas Kvarnström

We present a new forward chaining planner, TALplanner, based on ideas developed by Bacchus (1998) and Kabanza (1997), where domain-dependent search control knowledge represented as temporal formulas is used to effectively control forward chaining. Instead of using a linear modal tense logic as with Bacchus and Kabanza, we use TAL, a narrative-based linear temporal logic used for reasoning about action and change in incompletely specified dynamic environments. Two versions of TALplanner are considered, TALplan/modal which is based on the use of emulated modal formulas and a progression algorithm, and TALplan/non-modal which uses neither modal formulas nor a progression algorithm. For both versions of TALplanner and for all tested domains, TALplanner is shown to be considerably faster and requires less memory. The TAL versions also permit the representation of durative actions with internal state.

Details

TIME Conference 1998 Conference Paper

Tackling the Qualification Problem using Fluent Dependency Constraints: Preliminary Report

  • Patrick Doherty 0001
  • Jonas Kvarnström

The use of causal rules, or fluent dependency constraints, has proven to provide a versatile means of dealing with the ramification problem. In this paper, we show how fluent dependency constraints, together with the use of durational fluents, can be used to deal with problems associated with action qualification. We provide both a weak and a strong form of qualification and demonstrate the approach using an action scenario which combines solutions to the frame, ramification and qualification problems in the context of actions with duration, concurrent actions, nondeterministic actions and the use of both Boolean and non-Boolean fluents. The circumscription policy used for the combined problems is reducible to the first-order case. In addition, we demonstrate the use of a research tool, called VITAL (VIsualization of Temporal Action Logics), for querying and visualizing action scenarios.

Details
v2026.09.13