Arrow Research search

Author name cluster

Bence Cserna

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.

9 papers
2 author rows

Possible papers

9

AAAI Conference 2020 Conference Paper

Envelope-Based Approaches to Real-Time Heuristic Search

  • Kevin Gall
  • Bence Cserna
  • Wheeler Ruml

In real-time heuristic search, the planner must return the next action for the agent within a pre-specified time bound. Many algorithms for this setting are ‘agent-centered’ in that, at every iteration, they only expand states near the agent’s current state, discarding the search frontier afterwards. In this paper, we investigate the alternative paradigm in which the search expands a single ever-growing envelope of states. Previous work on envelope-based methods restricts the agent to move along the generated search tree. We propose a more flexible approach in which an auxiliary search is performed within the envelope to guide the agent toward a promising frontier node. Experimental results indicate that intra-envelope search is beneficial in state spaces that are highly interconnected, such as those for grid pathfinding.

PDF Details

AAAI Conference 2019 Conference Paper

Allocating Planning Effort When Actions Expire

  • Shahaf S. Shperberg
  • Andrew Coles
  • Bence Cserna
  • Erez Karpas
  • Wheeler Ruml
  • Solomon E. Shimony

Making plans that depend on external events can be tricky. For example, an agent considering a partial plan that involves taking a bus must recognize that this partial plan is only viable if completed and selected for execution in time for the agent to arrive at the bus stop. This setting raises the thorny problem of allocating the agent’s planning effort across multiple open search nodes, each of which has an expiration time and an expected completion effort in addition to the usual estimated plan cost. This paper formalizes this metareasoning problem, studies its theoretical properties, and presents several algorithms for solving it. Our theoretical results include a surprising connection to job scheduling, as well as to deliberation scheduling in time-dependent planning. Our empirical results indicate that our algorithms are effective in practice. This work advances our understanding of how heuristic search planners might address realistic problem settings.

PDF Details

SoCS Conference 2019 Conference Paper

Improved Safe Real-Time Heuristic Search

  • Bence Cserna
  • Kevin C. Gall
  • Wheeler Ruml

A fundamental concern in real-time planning is the presence of dead ends in the state space, from which no goal is reachable. Recently, the SafeRTS algorithm was proposed for searching in such spaces. SafeRTS exploits a user-provided predicate to identify safe states, from which a goal is likely reachable, and attempts to maintain a backup plan for reaching such a state at all times. In this paper, we study the SafeRTS approach, identify certain properties of its behavior, and design an improved framework for safe real-time search. We prove that the new approach performs at least as well as SafeRTS and present experimental results showing that its promise is fulfilled in practice.

Details

ICAPS Conference 2019 Conference Paper

Replanning for Situated Robots

  • Michael Cashmore
  • Andrew Coles
  • Bence Cserna
  • Erez Karpas
  • Daniele Magazzeni
  • Wheeler Ruml

Planning enables intelligent agents, such as robots, to act so as to achieve their long term goals. To make the planning process tractable, a relatively low fidelity model of the world is often used, which sometimes leads to the need to replan. The typical view of replanning is that the robot is given the current state, the goal, and possibly some data from the previous planning process. However, for robots (or teams of robots) that exist in continuous physical space, act concurrently, have deadlines, or must otherwise consider durative actions, things are not so simple. In this paper, we address the problem of replanning for situated robots. Relying on previous work on situated temporal planning, we frame the replanning problem as a situated temporal planning problem, where currently executing actions are handled via Timed Initial Literals (TILs), under the assumption that actions cannot be interrupted. We then relax this assumption, and address situated replanning with interruptible actions. We bridge the gap between the low-level model of the robot and the high-level model used for planning by the novel notion of a bail out action generator, which relies on the low-level model to generate highlevel actions that describe possible ways to interrupt currently executing actions. Because actions can be interrupted at different times during their execution, we also propose a novel algorithm to handle temporal planning with time-dependent durations.

Details

AAAI Conference 2018 Conference Paper

Avoiding Dead Ends in Real-Time Heuristic Search

  • Bence Cserna
  • William Doyle
  • Jordan Ramsdell
  • Wheeler Ruml

Many systems, such as mobile robots, need to be controlled in real time. Real-time heuristic search is a popular on-line planning paradigm that supports concurrent planning and execution. However, existing methods do not incorporate a notion of safety and we show that they can perform poorly in domains that contain dead-end states from which a goal cannot be reached. We introduce new real-time heuristic search methods that can guarantee safety if the domain obeys certain properties. We test these new methods on two different simulated domains that contain dead ends, one that obeys the properties and one that does not. We find that empirically the new methods provide good performance. We hope this work encourages further efforts to widen the applicability of realtime planning.

PDF Details

ICAPS Conference 2018 Conference Paper

Temporal Planning while the Clock Ticks

  • Michael Cashmore
  • Andrew Coles
  • Bence Cserna
  • Erez Karpas
  • Daniele Magazzeni
  • Wheeler Ruml

One of the original motivations for domain-independent planning was to generate plans that would then be executed in the environment. However, most existing planners ignore the passage of time during planning. While this can work well when absolute time does not play a role, this approach can lead to plans failing when there are external timing constraints, such as deadlines. In this paper, we describe a new approach for time-sensitive temporal planning. Our planner is aware of the fact that plan execution will start only once planning finishes, and incorporates this information into its decision making, in order to focus the search on branches that are more likely to lead to plans that will be feasible when the planner finishes.

Details

ICAPS Conference 2017 Conference Paper

Planning Time to Think: Metareasoning for On-Line Planning with Durative Actions

  • Bence Cserna
  • Wheeler Ruml
  • Jeremy Frank

When minimizing makespan during off-line planning, the fastest action sequence to reach a particular state is, by definition, preferred. When trying to reach a goal quickly in on-line planning, previous work has inherited that assumption: the faster of two paths that both reach the same state is usually considered to dominate the slower one. In this short paper, we point out that, when planning happens concurrently with execution, selecting a slower action can allow additional time for planning, leading to better plans. We present Slo'RTS, a metareasoning planning algorithm that estimates whether the expected improvement in future decision-making from this increased planning time is enough to make up for the increased duration of the selected action. Using simple benchmarks, we show that Slo'RTS can yield shorter time-to-goal than a conventional planner. This generalizes previous work on metareasoning in on-line planning and highlights the inherent uncertainty present in an on-line setting.

Details

UAI Conference 2017 Conference Paper

Value Directed Exploration in Multi-Armed Bandits with Structured Priors

  • Bence Cserna
  • Marek Petrik
  • Reazul Hasan Russel
  • Wheeler Ruml

Multi-armed bandits are a quintessential machine learning problem requiring balancing exploration with exploitation. While there has been progress in developing algorithms with strong theoretical guarantees, there has been less focus on practical near-optimal finite-time performance. In this paper, we propose an algorithm for Bayesian multi-armed bandits that utilizes approximate value functions. Building on previous work on UCB and Gittins index, we introduce linearly-separable value functions that capture the benefit of exploration when choosing the next arm to pull. Our algorithm enjoys a sub-linear performance guarantee and our simulation results confirm its strength in problems with structured priors. The simplicity and generality of our approach makes it a strong candidate for use in more complex multi-armed bandit problems.

Details

SoCS Conference 2016 Conference Paper

Anytime versus Real-Time Heuristic Search for On-Line Planning

  • Bence Cserna
  • Mike Bogochow
  • Stephen Chambers
  • Michaela Tremblay
  • Sammie Katt
  • Wheeler Ruml

Many AI systems, such as robots, must plan under time constraints. The most popular search approach applied in robotics so far is anytime search, in which the algorithm quickly finds a suboptimal plan, and then continues to find better and better plans as time passes, until eventually converging on an optimal plan. However, the time until the first plan is returned is not controllable, so such methods inherently involve idling the system

Details