nils-herrmann/clean_scirepeval huggingface dataset:
The Innuence of Domain Properties on the Performance of Real-time Search Algorithms

The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the oocial policies, either expressed or implied, of the sponsoring organizations.  In this report, we investigate the innuence of domain properties on the performance of real-time search algorithms. We study uninformed, revolving real-time search algorithms with minimal lookahead that solve suboptimal search problems, for example variants of Korf's LRTA* algorithm and edge counting (these algorithms have been used successfully in the literature). We demonstrate, both theoretically and experimentally , that they can search Eulerian domains (a superset of undirected domains) very easily: even the real-time search algorithms that can be intractable are always ef-cient in Eulerian domains. Because traditional real-time search testbeds (such as the eight puzzle and gridworlds) are Eulerian, they cannot be used to distinguish between eecient and ineecient real-time search algorithms. It follows that one has to use non-Eulerian domains to demonstrate the superiority of a real-time search algorithm across a wide range of domains { the studied real-time search algorithms diier in this respect from traditional search algorithms. To this end, we describe two classes of domains (\reset state spaces" and \quicksand state spaces") that do not suuer as much from the problems of the standard test domains and demonstrate the performance of various real-time search algorithms in them.
Easy and Hard Testbeds for Real-Time Search Algorithms

Although researchers have studied which factors influence the behavior of traditional search algorithms, currently not much is known about how domain properties influence the performance of real-time search algorithms. In this paper we demonstrate, both theoretically and experimentally, that Eulerian state spaces (a superset of undirected state spaces) are very easy for some existing real-time search algorithms to solve: even real-time search algorithms that can be intractable, in general, are efficient for Eulerian state spaces. Because traditional real-time search testbeds (such as the eight puzzle and gridworlds) are Eulerian, they cannot be used to distinguish between efficient and inefficient real-time search algorithms. It follows that one has to use non-Eulerian domains to demonstrate the general superiority of a given algorithm. To this end, we present two classes of hard-to-search state spaces and demonstrate the performance of various real-time search algorithms on them.
Efficient Goal-Directed 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.
Safeguarded Teleoperation for Lunar Rovers

In this paper we present recent advances in developing and validating the safeguarded teleoperation approach to timedelayed remote driving. This approach shares control of the rover using a command fusion strategy: In benign situations, usus 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 a p proach in a 10 km traverse, demonstrating the effectiveness of safeguarding, even with malicious drivers.
Passive Distance Learning for Robot Navigation

Autonomous mobile robots need good models of their environment, sensors and actuators to navigate reliably and efficiently. While this information can be supplied by humans, or learned from scratch through active exploration, such approaches are tedious and time-consuming. Our approach is to provide the robot with the topological and geometrical constraints that are easily obtainable by humans, and have the robot learn the rest while in the course of performing its tasks. We present GROW-BW, an unsupervised and passive distance learning algorithm that overcomes the problem that the robot can never be sure about its location if it is not allowed to reduce its uncertainty by asking a teacher or executing localization actions. Advantages of GROW-BW include that the robot can be used immediately to perform navigation tasks and improves its performance over time, focusing its attention to routes that are more relevant for its tasks. We demonstrate that GROW-BW can learn good distance, sensor, and actuator models with only a small amount of experience.
Unsupervised learning of probabilistic models for robot navigation

Navigation methods for office delivery robots need to take various sources of uncertainty into account in order to get robust performance. In previous work, we developed a reliable navigation technique that uses partially observable Markov models to represent metric, actuator and sensor uncertainties. This paper describes an algorithm that adjusts the probabilities of the initial Markov model by passively observing the robot's interactions with its environment. The learned probabilities more accurately reflect the actual uncertainties in the environment, which ultimately leads to improved navigation performance. The algorithm, an extension of the Baum-Welch algorithm, learns without a teacher and addresses the issues of limited memory and the cost of collecting training data. Empirical results show that the algorithm learns good Markov models with a small amount of training data.
Graph learning with a nearest neighbor approach

In this paper, we study how to traverse all edges of an unknown graph G = (V;E) that is bi-directed and strongly connected. This problem can be solved with a simple algorithm that traverses all edges at most twice, and no algorithm can do better in the worst case. Artificial Intelligence researchers, however, often use the following online nearest neighbor algorithm: “repeatedly take a shortest path to the closest unexplored edge and traverse it.” We prove bounds on the worst-case complexity of this algorithm. We show, for example, that its worst-case complexity is close to optimal for some classes of graphs, such as graphs with linear or star topology and dense graphs with edge lengths one. In general, however, its complexity can grow faster than linear in the sum of all edge lengths, although not faster than log(V ) times the sum of all edge lengths.
Probabilistic Navigation in Partially Observable Environments

Autonomous mobile robots need very reliable navigation capabilities in order to operate unattended for long periods of time. We have developed an approach that uses partially observable Markov models to robustly track a robot’s location and integrates it with a planning and execution monitoring approach that uses this information to control the robot’s actions. The approach explicitly maintains a probability distributionover the possible locations of the robot, taking into account various sources of uncertainty, including approximate knowledge of the environment, actuator uncertainty, and sensor noise. A novel feature of our approach is its integration of topological map information with approximate metric information. We demonstrate the reliability of this approach, especially its ability to smoothly recover from errors in sensing.
Robot Navigation with Markov Models: A Framework for Path Planning and Learning with Limited Computational Resources

Navigation methods for mobile robots need to take various sources of uncertainty into account in order to get robust performance. The ability to improve performance with experience and to adapt to new circumstances is equally important for long-term operation. Real-time constraints, limited computation and memory, as well as the cost of collecting training data also need to be accounted for. In this paper, we discuss our evolving architecture for mobile robot navigation that we use as a test-bed for evaluating methods for dealing with uncertainty in the face of real-time constraints and limited computational resources. The architecture is based on POMDP models that explicitly represent actuator uncertainty, sensor uncertainty, and approximate knowledge of the environment (such as uncertain metric information). Using this model, the robot is able to track its likely location as it navigates through a building. Here, we discuss additions to the architecture: a learning component that allows the robot to improve the POMDP model from experience, and a decision-theoretic path planner that takes into account the expected performance of the robot as well as probabilistic information about the state of the world. A key aspect of both additions is the efficient allocation of computational resources and their practical application to real-world robots.
Probabilistic Robot Navigation in Partially Observable Environments

Autonomous mobile robots need very reliable navigation capabilities in order to operate unattended for long periods of time. This paper reports on first results of a research program that uses par tially observable Markov models to robustly track a robots location in office environments and to direct its goal-oriented actions. The approach explicitly maintains a probability distribution over the possible locations of the robot taking into account various sources of uncertainly including approximate knowledge of the environment and actuator and sensor uncertainty. A novel feature of our approach is its integration of topological map information with approximate metric information. We demonstrate the robustness of this approach in controlling an actual indoor mobile robot navigating corridors.
Real-Time Search in Non-Deterministic Domains

Many search domains are non-deterministic. Although real-time search methods have traditionally been studied in deterministic domains, they are well suited for searching nondeterministic domains since they do not have to plan for every contingency they can react to the actual outcomes of actions. In this paper, we introduce the min-max LRTA* algorithm, a simple extension of Korf's Learning Real-Time A* algorithm (LRTA*) to nondeterministic domains. We describe which nondeterministic domains min-max LRTA* can solve, and analyze its performance for these domains. We also give tight bounds on its worst-case performance and show how this performance depends on properties of both the domains and the heuristic functions used to encode prior information about the domains.
No-Regret Algorithms for Structured Prediction Problems

No-regret algorithms are a popular class of online learning rules. Unfortunately, most no-regret algorithms assume that the set Y of allowable hypotheses is small and discrete. Instead, the authors consider prediction problems where Y has internal structure: Y might be the set of strategies in a game like poker, the set of paths in a graph, or the set of configurations of a data structure like a rebalancing binary search tree; or Y might be a given convex set (the "online convex programming" problem), or, in general, an arbitrary bounded set. They derive a family of no-regret learning rules, called Lagrangian Hedging algorithms, to take advantage of this structure. Their algorithms are a direct generalization of known no-regret learning rules, like weighted majority and external-regret matching. In addition to proving regret bounds, they demonstrate one of their algorithms learning to play one-card poker.
Generalizing Dijkstra's Algorithm and Gaussian Elimination for Solving MDPs

The authors study the problem of computing the optimal value function for a Markov Decision Process (MDP) with positive costs. Computing this function quickly and accurately is a basic step in many schemes for deciding how to act in stochastic environments. There are efficient algorithms that compute value functions for special types of MDPs. For deterministic MDPs with S states and A actions, Dijkstra's algorithm runs in time O(AS log S). And, in single-action MDPs (Markov chains), standard linear-algebraic algorithms find the value function in time O(S sup 3), or faster by taking advantage of sparsity or good conditioning. Algorithms for solving general MDPs can take much longer: the authors are not aware of any speed guarantees better than those for comparably sized linear programs. They present a family of algorithms that reduce to Dijkstra's algorithm when applied to deterministic MDPs, and to standard techniques for solving linear equations when applied to Markov chains. More importantly, they demonstrate experimentally that these algorithms perform well when applied to MDPs that "almost" have the required special structure.
Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees

MDPs are an attractive formalization for planning, but realistic problems often have intractably large state spaces. When we only need a partial policy to get from a fixed start state to a goal, restricting computation to states relevant to this task can make much larger problems tractable. We introduce a new algorithm, Bounded RTDP, which can produce partial policies with strong performance guarantees while only touching a fraction of the state space, even on problems where other algorithms would have to visit the full state space. To do so, Bounded RTDP maintains both upper and lower bounds on the optimal value function. The performance of Bounded RTDP is greatly aided by the introduction of a new technique to efficiently find suitable upper bounds; this technique can also be used to provide informed initialization to a wide range of other planning algorithms.
POMDP Planning for Robust Robot Control

POMDPs provide a rich framework for planning and control in partially observable domains. Recent new algorithms have greatly improved the scalability of POMDPs, to the point where they can be used in robot applications. In this paper, we describe how approximate POMDP solving can be further improved by the use of a new theoretically-motivated algorithm for selecting salient information states. We present the algorithm, called PEMA, demonstrate competitive performance on a range of navigation tasks, and show how this approach is robust to mismatches between the robot’s physical environment and the model used for planning.
No-regret algorithms for structured prediction problems — DRAFT

No-regret algorithms are a popular class of learning rules which map a sequence of input vectors x1, x2 . . . to a sequence of predictions y1, y2, . . .. Unfortunately, most no-regret algorithms assume that the predictions yt are chosen from a small, discrete set. We consider instead prediction problems where yt has internal structure: yt might be a strategy in a game like poker, or a configuration of a data structure like a rebalancing binary search tree. We derive a family of no-regret learning rules, called Lagrangian Hedging algorithms, to take advantage of this structure. Our algorithms are a direct generalization of known no-regret learning rules like weighted majority and regret matching. In addition to proving regret bounds, we demonstrate one of our algorithms learning to play one-card poker.
Fast Exact Planning in Markov Decision Processes

We study the problem of computing the optimal value function for a Markov decision process with positive costs. Computing this function quickly and accurately is a basic step in many schemes for deciding how to act in stochastic environments. There are efficient algorithms which compute value functions for special types of MDPs: for deterministic MDPs with S states and A actions, Dijkstra's algorithm runs in time O(AS log S). And, in single-action MDPs (Markov chains), standard linear-algebraic algorithms find the value function in time O(S3), or faster by taking advantage of sparsity or good conditioning. Algorithms for solving general MDPs can take much longer: we are not aware of any speed guarantees better than those for comparably-sized linear programs. We present a family of algorithms which reduce to Dijkstra's algorithm when applied to deterministic MDPs, and to standard techniques for solving linear equations when applied to Markov chains. More importantly, we demonstrate experimentally that these algorithms perform well when applied to MDPs which "almost" have the required special structure.
Better Motion Prediction for People-tracking

An important building block for intelligent mobile robots is the ability to track people moving around in the environment. Algorithms for person-tracking often incorporate motion models, which can improve tracking accuracy by predicting how people will move. More accurate motion models produce better tracking because they allow us to average together multiple predictions of the person’s location rather than depending entirely on the most recent observation. Many implemented systems, however, use simple conservative motion models such as Brownian motion (in which the person’s direction of motion is independent on each time step). We present an improved motion model based on the intuition that people tend to follow efficient trajectories through their environments rather than random paths. Our motion model learns common destinations within the environment by clustering training examples of actual trajectories, then uses a path planner to predict how a person would move along routes from his or her present location to these destinations. We have integrated this motion model into a particle-filter-based person-tracker, and we demonstrate experimentally that our new motion model performs significantly better than simpler models, especially in situations in which there are extended periods of occlusion during tracking.
Multi-robot coordination and competition using mixed integer and linear programs

Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs) are preferred methods representing complex uncertain dynamic systems and determining an optimal control policy to manipulate the system in the desired manner. Until recently, controlling a system composed of multiple agents using the MDP methodology was impossible due to an exponential increase in the size of the MDP problem representation. In this thesis, a novel method for solving large multi-agent MDP systems is presented which avoids this exponential size increase while still providing optimal policies for a large class of useful problems. 
This thesis provides the following main contributions: 
A novel description language for multi-agent MDPs. We develop two different modeling techniques for representing multi-agent MDP (MAMDP) coordination problems. The first phrases the problem using a linear program which avoids the exponential state space size of multi-agent MDPs. The second, more expressive representation, expands upon the linear programming representation with the addition of integer constraints. For many problems, these representations exactly represent the original problem with exponentially fewer variables and constraints. This leads to an efficient and optimal solution of the multi-agent MDP. 
A novel multi-agent coordination method for multi-agent MDPs . We use the Dantzig-Wolfe decomposition technique and the branch and bound method to solve the above models efficiently. These solution methods overcome significant drawbacks in related work. We develop a multi-robot towing and foraging model, devise a novel multi-agent path planner and solve coordination problems with quadratic cost on a global resource. 
A method to determine the optimal strategies for competing teams . One team of players is allowed to determine the cost function of the MAMDP of the second team. This allows us to solve a zero-sum game played by both teams. One team chooses cost functions and the other coordinates to find the least cost plan given the other team's possible strategies. Each team is coordinated using the newly developed multi-agent coordination method above. 
A game of robot paintball. Using the above techniques we solve a game of multi-robot paintball. This game is played with real robots at high speeds.
ARA : formal analysis

In real world problems, time for deliberation is often limited. Anytime algorithms are beneficial in these conditions as they usually find a first, possibly highly suboptimal, solution very fast and then continually work on improving the solution until allocated time expires. While anytime algorithms are popular, existing anytime search methods are unable to provide a measure of goodness of their results. In this paper we propose the ARA* algorithm. ARA* is an anytime heuristic search which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. In addition to the theoretical analysis we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and dynamic path planning problem for an outdoor rover.
Planning in the Presence of Cost Functions Controlled by an Adversary

We investigate methods for planning in a Markov Decision Process where the cost function is chosen by an adversary after we fix our policy. As a running example, we consider a robot path planning problem where costs are influenced by sensors that an adversary places in the environment. We formulate the problem as a zero-sum matrix game where rows correspond to deterministic policies for the planning player and columns correspond to cost vectors the adversary can select. For a fixed cost vector, fast algorithms (such as value iteration) are available for solving MDPs. We develop efficient algorithms for matrix games where such best response oracles exist. We show that for our path planning problem these algorithms are at least an order of magnitude faster than direct solution of the linear programming formulation.