nils-herrmann/clean_scirepeval huggingface dataset:
Incremental A*

Incremental search techniques find optimal solutions to series of similar search tasks much faster than is possible by solving each search task from scratch. While researchers have developed incremental versions of uninformed search methods, we develop an incremental version of A*. The first search of Lifelong Planning A* is the same as that of A* but all subsequent searches are much faster because it reuses those parts of the previous search tree that are identical to the new search tree. We then present experimental results that demonstrate the advantages of Lifelong Planning A* for simple route planning tasks.
How to Make Reactive Planners Risk-Sensitive*

Probabilistic planners can have various planning objectives: usually they either maximize the probability of goal achievement or minimize the expected execution cost of the plan. Researchers have largely ignored the problem how to incorporate risk-sensitive attitudes into their planning mechanisms. We discuss a risk-sensitive planning approach that is based on utility theory. Our key result is that this approach can, at least for risk-seeking attitudes, be implemented with any reactive planner that maximizes (or satisfices) the probability of goal achievement. First, the risk-sensitive planning problem is transformed into a different planning problem, that is then solved by the planner. The larger the probability of goal achievement of the resulting plan, the better its expected utility is for the original (risk-sensitive) planning problem. This approach extends the functionality of reactive planners that maximize the probability of goal achievement, since it allows one to use them (unchanged) for risk-sensitive planning.
Terrain coverage with ant robots: a simulation study

In this paper, we study a simple means for coordinating teams of simple agents. In particular, we study ant robots and how they can cover terrain once or repeatedly by leaving markings in the terrain, similar to what ants do. These markings can be sensed by all robots and allow them to cover terrain even if they do not communicate with each other except via the markings, do not have any kind of memory, do not know the terrain, cannot maintain maps of the terrain, nor plan complete paths. The robots do not even need to be localized, which completely eliminates solving difficult and time-consuming localization problems. In this paper, we use real-time heuristic search methods to implement ant robots and present a simulation study with several real-time heuristic search methods to study their properties for terrain coverage. Our experiments show that all of the real-time heuristic search methods robustly cover terrain even if the robots are moved without realizing this, some robots fail, and some markings get destroyed. These results demonstrate that terrain coverage with real-time heuristic search methods is an interesting alternative to more conventional terrain coverage methods.
Probabilistic Planning for Behavior-Based Robots

Partially Observable Markov Decision Process models (POMDPs) have been applied to low-level robot control. We show how to use POMDPs differently, namely for sensor planning in the context of behavior-based robot systems. This is possible because solutions of POMDPs can be expressed as policy graphs, which are similar to the finite state automata that behavior-based systems use to sequence their behaviors. An advantage of our system over previous POMDP navigation systems is that it is able to find close-to-optimal plans since it plans at a higher level and thus with smaller state spaces. An advantage of our system over behavior-based systems that need to get programmed by their users is that it can optimize plans during missions and thus deal robustly with probabilistic models that are initially inaccurate.
Speeding up the Convergence of Real-Time Search

Learning Real-Time A* (LRTA*) is a real-time search method that makes decisions fast and still converges to a shortest path when it solves the same planning task repeatedly. In this paper, we propose new methods to speed up its convergence. We show that LRTA* often converges significantly faster when it breaks ties towards successors with smallest f-values ( a la A*) and even faster when it moves to successors with smallest f-values instead of only breaking ties in favor of them. FALCONS, our novel real-time search method, uses a sophisticated implementation of this successor-selection rule and thus selects successors very differently from LRTA*, which always minimizes the estimated cost to go. We first prove that FALCONS terminates and converges to a shortest path, and then present experiments in which FALCONS finds a shortest path up to sixty percent faster than LRTA* in terms of action executions and up to seventy percent faster in terms of trials. This paper opens up new avenues of research for the design of novel successorselection rules that speed up the convergence of both realtime search methods and reinforcement-learning methods.
Representations of Decision-Theoretic Planning Tasks

Goal-directed Markov Decision Process models (GDMDPs) are good models for many decision-theoretic planning tasks. They have been used in conjunction with two different reward structures, namely the goal-reward representation and the action-penalty representation. We apply GDMDPs to planning tasks in the presence of traps such as steep slopes for outdoor robots or staircases for indoor robots, and study the differences between the two reward structures. In these situations, achieving the goal is often the primary objective while minimizing the travel time is only of secondary importance. We show that the action-penalty representation without discounting guarantees that the optimal plan achieves the goal for sure (if this is possible) but neither the action-penalty representation with discounting nor the goal-reward representation with discounting have this property. We then show exactly when this trapping phenomenon occurs, using a novel interpretation for discounting, namely that it models agents that use convex exponential utility functions and thus are optimistic in the face of uncertainty. Finally, we show how the trapping phenomenon can be eliminated with our Selective State-Deletion Method.
Reports on the AAAI Spring Symposia (March 1999)

The Association for the Advancement of Artificial Intelligence, in cooperation, with Stanford University's Department of Com-puter Science, presented the 1999 Spring Symposium Series on 22 to 24 March 1999 at Stanford University. The titles of the seven symposia were (1) Agents with Adjustable Autonomy, (2) Artificial Intelligence and Computer Games, (3) Artificial Intelligence in Equipment Maintenance Service and Support, (4) Hybrid Systems and AI: Modeling, Analysis, and Control of Discrete + Continuous Systems, (5) Intelligent Agents in Cyberspace, (6) Predictive Toxicology of Chemicals: Experiences and Impact of AI Tools, and (7) Search Techniques for Problem Solving under Uncertainty and Incomplete Information.
Planning-Task Transformations for Soft Deadlines

Agents often have preference models that are more complicated than minimizing the expected execution cost. In this paper, we study how they should act in the presence of uncertainty and immediate soft deadlines. Delivery robots, for example, are agents that are often confronted with immediate soft deadlines. We introduce the additive and multiplicative planning-task transformations, that are fast representation changes that transform planning tasks with convex exponential utility functions to planning tasks that can be solved with variants of standard deterministic or probabilistic artificial intelligence planners. Advantages of our representation changes include that they are context-insensitive, fast, scale well, allow for optimal and near-optimal planning, and are grounded in utility theory. Thus, while representation changes are often used to make planning more efficient, we use them to extend the functionality of existing planners, resulting in agents with more realistic preference models.
Gridworlds as Testbeds for Planning with Incomplete Information

Gridworlds are popular testbeds for planning with incomplete information but not much is known about their properties. We study a fundamental planning problem, localization, to investigate whether gridworlds make good testbeds for planning with incomplete information. We find empirically that greedy planning methods that interleave planning and plan execution can localize robots very quickly on random gridworlds or mazes. Thus, they may not provide adequately challenging testbeds. On the other hand, we show that finding localization plans that are within a log factor of optimal is NP-hard. Thus there are instances of gridworlds on which all greedy planning methods perform very poorly, and we show how to construct them. These theoretical results help empirical researchers to select appropriate planning methods for planning with incomplete information as well as testbeds to demonstrate them.
'From Animals to Animats 5': Proceedings of the Fifth International Conference on Simulation of Adaptive Behavior

The Fifth International Conference on Adaptive Behavior (SAB98) was held at the University of Zurich (Switzerland) in 1998. The conference is an interdisciplinary conference that brings together researchers from various backgrounds such as ethology, theoretical biology, psychology, artificial life, machine learning, and robotics. These researchers study adaptive behavior for different reasons, most notably “explaining” and “building.” Some papers attempt to model biological behavior. Some of them then validate the models by running them on animats, often mobile robots, and compare the resulting behavior against that of animals. Other papers use the models to implement capabilities of animats that make them more robust or efficient. Some papers base their methods very faithfully on biological systems. Other papers are content if their methods have the same input/output behavior as biological systems. Still other papers use biological systems only as an inspiration for their methods. Finally, there are papers that do not pay attention to biological systems at all but whose results still provide insight into which capabilities are necessary to implement certain kinds of behaviors and which internal structures facilitate their implementation, possibly resulting in hypotheses about how biological systems work. The papers are grouped into categories such as Theoretical Issues, Perception and Visually Guided Behavior, Action Selection and Behavioral Sequences, Navigation, Emergent Structures and Behaviors, Learning, Motor Learning, Collective Behavior, and Evolution. The papers are diverse. Some papers study single behaviors, others study the interaction of behaviors. Some papers study single animats, others study groups of animats. Some papers perform experiments in simulation, others use physical systems. The papers use methods such as neural networks, evolutionary algorithms, differential equations, reinforcement learning, and non-linear control methods to study behaviors such as:
Value-Update Rules for Real-Time Search

Real-time search methods have successfully been used to solve a large variety of search problems but their properties are largely unknown. In this paper, we study how existing real-time search methods scale up. We compare two realtime search methods that have been used successfully in the literature and differ only in the update rules of their values: Node Counting, a real-time search method that always moves to the successor state that it has visited the least number of times so far, and Learning Real-Time A*, a similar real-time search method. Both real-time search methods seemed to perform equally well in many standard domains from artificial intelligence. Our formal analysis is therefore surprising. We show that the performance of Node Counting can be exponential in the number of states even in undirected domains. This solves an open problem and shows that the two real-time search methods do not always perform similarly in undirected domains since the performance of Learning RealTime A* is known to be polynomial in the number of states at worst.
Safeguarded Teleoperation for Lunar Rovers: From Human Factors to Field Trials

In this paper we present recent advances in developing and validating the safeguarded teleoperation approach to time-delayed remote driving. This approach shares control of the rover using a command fusion strategy: In benign situations, users remotely drive the rover; in hazardous situations, a safeguarding system running on-board the rover overwrites user commands to ensure vehicle safety. This strategy satisfies users, because it allows them to drive (except in hazardous situations), while maintaining the integrity of the rover and mission. We present results from experiments on untrained teleoperators with and without safeguarding, which reveal needs to be met by future user interfaces. We describe three technical advances in safeguarding: improving the accuracy of dead reckoning by a factor of 2, speeding up the controller by a factor of 18, and developing an area-based rather than a path-based obstacle avoidance planner in order to circumvent map merging problems. Finally, we discuss a field trial validating the approach in a 10 km traverse, demonstrating the effectiveness of safeguarding, even with malicious drivers.
Efficient Goal-Directe Exploration

If a state space is not completely known in advance, then search algorithms have to explore it sufficiently to locate a goal state and a path leading to it, performing therefore what we call goal-directed exploration. Two paradigms of this process are pure exploration and heuristic-driven exploitation: the former approaches explore the state space using only knowledge of the physically visited portion of the domain, whereas the latter approaches totally rely on heuristic knowledge to guide the search towards goal states. Both approaches have disadvantages: the first one does not utilize available knowledge to cut down the search effort, and the second one relies too much on the knowledge, even if it is misleading. We have therefore developed a framework for goal-directed exploration, called VECA, that combines the advantages of both approaches by automatically switching from exploitation to exploration on parts of the state space where exploitation does not perform well. VECA provides better performance guarantees than previously studied heuristic-driven exploitation algorithms, and experimental evidence suggests that this guarantee does not deteriorate its average-case performance.
Sensor Planning with Non-linear Utility Functions

Sensor planning is concerned with when to sense and what to sense. We study sensor planning in the context of planning objectives that trade-off between minimizing the worst-case, expected, and best-case plan- execution costs. Sensor planning with these planning objectives is interesting because they are realistic and the frequency of sensing changes with the planning objective: more pessimistic decision makers tend to sense more frequently. We perform sensor planning by combining one of our techniques for planning with non-linear utility functions with an existing sensor-planning method. The resulting sensor-planning method is not only as easy to implement as the sensor-planning method that it extends but also (almost) as efficient. We demonstrate empirically how sensor plans change as the planning objective changes, using a common testbed for sensor planning.
Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search

We study goal-directed navigation tasks in mazes, where the robots know the maze but do not know their initial pose (position and orientation). These search tasks can be modeled as planning tasks in large non-deterministic domains whose states are sets of poses. They can be solved efficiently by interleaving planning and plan execution, which can reduce the sum of planning and plan-execution time because it allows the robots to gather information early. We show how Min-Max LRTA*, a real-time heuristic search method, can solve these and other planning tasks in non-deterministic domains efficiently. It allows for fine-grained control over how much planning to do between plan executions, uses heuristic knowledge to guide planning, and improves its plan-execution time as it solves similar planning tasks, until its plan-execution time is at least worst-case optimal. We also show that Min-Max LRTA* solves the goal-directed navigation tasks fast, converges quickly, and requires only a small amount of memory.
Exploring Unknown Environments with Real-Time Search or Reinforcement Learning

Learning Real-Time A* (LRTA*) is a popular control method that interleaves planning and plan execution and has been shown to solve search problems in known environments efficiently. In this paper, we apply LRTA * to the problem of getting to a given goal location in an initially unknown environment. Uninformed LRTA * with maximal lookahead always moves on a shortest path to the closest unvisited state, that is, to the closest potential goal state. This was believed to be a good exploration heuristic, but we show that it does not minimize the worst-case plan-execution time compared to other uninformed exploration methods. This result is also of interest to reinforcement-learning researchers since many reinforcement learning methods use asynchronous dynamic programming, interleave planning and plan execution, and exhibit optimism in the face of uncertainty, just like LRTA *.
The Complexity of Node Counting on Undirected Graphs

We analyze the complexity of Node Counting, a graph-traversal method. On many graphs arising in control problems in Artificial Intelligence, Node Counting performs as efficiently as other methods which are known to be of polynomial complexity in the number of states (e.g., Learning Real-Time A* method). We show that complexity of Node Counting on undirected graphs is , which is not polynomial in the number of states. This solves an open problem from the literature.
Sensor-based planning with the freespace assumption

A popular technique for getting to a goal location in unknown terrain is planning with the freespace assumption. The robot assumes that the terrain is clear unless it knows otherwise. It always plans a shortest path to the goal location and re-plans whenever it detects an obstacle that blocks its path or, more generally, when it detects that its current path is no longer optimal. It has been unknown whether this sensor-based planning approach is worst-case optimal, given the lack of initial knowledge about the terrain. We demonstrate that planning with the freespace assumption can make good performance guarantees on some restricted graph topologies (such as grids) but is not worst-case optimal in general. For situations in which its performance guarantee is insufficient, we also describe an algorithm, called Basic-VECA, that exhibits good average-case performance and provides performance guarantees that are optimal up to a constant (user-defined) factor.
A Layered Architecture for O ce Delivery Robots

O ce delivery robots have to perform many tasks. They have to determine the order in which to visit ofces, plan paths to those o ces, follow paths reliably, and avoid static and dynamic obstacles in the process. Reliability and e ciency are key issues in the design of such autonomous robot systems. They must deal reliably with noisy sensors and actuators and with incomplete knowledge of the environment. They must also act e ciently, in real time, to deal with dynamic situations. Our architecture is composed of four abstraction layers: obstacle avoidance, navigation, path planning, and task scheduling. The layers are independent, communicating processes that are always active, processing sensory data and status information to update their decisions and actions. A version of our robot architecture has been in nearly daily use in our building since December 1995. As of July 1996, the robot has traveled more than 75 kilometers in service of over 1800 navigation requests that were speci ed using our World Wide Web interface.
Xavier: A Robot Navigation Architecture Based on Partially Observable Markov Decision Process Models

Autonomous mobile robots need very reliable navigation capabilities in order to operate unattended for long periods of time. We present a technique for achieving this goal that uses partially observable Markov decision process models (POMDPs) to explicitly model navigation uncertainty, including actuator and sensor uncertainty and approximate knowledge of the environment. This allows the robot to maintain a probability distribution over its current pose. Thus, while the robot rarely knows exactly where it is, it always has some belief as to what its true pose is, and is never completely lost. We present a navigation architecture based on POMDPs that provides a uniform framework with an established theoretical foundation for pose estimation, path planning, robot control during navigation, and learning. Our experiments show that this architecture indeed leads to robust corridor navigation for an actual indoor mobile robot.
Goal-Directed Acting with Incomplete Information

In the not too distant future, delivery robots will distribute parcels in office buildings and exploratory robots will roam the surface of other planets. Such situated agents must exhibit goal-directed behavior in realtime, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception, or insufficient reasoning speed. In this thesis, we develop efficient generalpurpose decision-making methods for one-shot (that is, single-instance) planning tasks that enable situated agents to exhibit goal-directed behavior in the presence of incomplete information. The decision making methods combine search and planning methods from artificial intelligence with methods from operations research and utility theory. We demonstrate how to use Partially Observable Markov Decision Process (POMDP) models to act, plan, and learn despite the uncertainty that results from actuator and sensor noise and missing information about the environment. We show how to use exponential utility functions to act in the presence of deadlines or in high-risk situations and demonstrate how to perform representation changes that transform planning tasks with exponential utility functions to planning tasks that standard search and planning methods from artificial intelligence can solve. Finally, we show how to decrease the planning time by interleaving planning and plan execution and present a real-time search method that allows for fine-grained control over how much planning to do between plan executions, uses heuristic knowledge to guide planning, and improves its performance over time as it solves similar planning tasks. We use goal-directed robot-navigation tasks to illustrate the methods throughout the thesis, and present theoretical analyses, simulations, and experiments on a real robot.