nils-herrmann/clean_scirepeval huggingface dataset:
An Approximation Algorithm for the Robot Localization Problem

Localization is a fundamental problem in robotics. The robot possesses line-of-sight sensors, a compass, and a map of its polygonal environment; it must determine its location at a minimum cost of travel distance. Localization is NP-hard , even to minimize within a c log n factor , where n is the number of polygon vertices. No approximation algorithm for the problem has been known. We give a strongly polynomial time O(log n log r)-factor approximation algorithm, where r is the number of reflex vertices. Technical features of the algorithm include a new edge-visibility based partition decomposition of the plane, and the idea of repeatedly planning travel on a “majority-rule” map, which permits a plan to be a route rather than a decision tree.
Improved analysis of D*

D* is a planning method that always routes a robot in initially unknown terrain from its current location to a given goal location along a shortest presumed unblocked path. The robot moves along the path until it discovers new obstacles and then repeats the procedure. D* has been used on a large number of robots. It is therefore important to analyze the resulting travel distance. Previously, there has been only one analysis of D*, and it has two shortcomings. First, to prove the lower bound, it uses a physically unrealistic example graph which has distances that do not correspond to distances on a real map. We show that the lower bound is not smaller for grids, the kind of map-based graph on which D* is usually used. Second, there is a large gap between the upper and lower bounds on the travel distance. We considerably reduce this gap by decreasing the upper bound on arbitrary graphs, including grids. To summarize, we provide new, substantially tighter bounds on the travel distance of D* on grids, thus providing a realistic analysis for the way D* is actually used.
Risk-averse auction agents

Auctions are an important means for purchasing material in the era of e-commerce. Research on auctions often studies them in isolation. In practice, however, auction agents are part of complete supply-chain management systems and have to make the same decisions as their human counterparts. To address this issue, we generalize results from auction theory in three ways. First, auction theory provides the optimal bidding function for the case where auction agents want to maximize the expected profit. Since companies are often risk-averse, we derive a closed form of the optimal bidding function for auction agents that maximize the expected utility of the profit for concave exponential utility functions. Second, auction theory often assumes that auction agents know the bidder's valuation of an auctioned item. However, the valuation depends on how the item can be used in the production process. We therefore develop theoretical results that enable us to integrate our auction agents into production-planning systems to derive the bidder's valuation automatically. Third, auction theory often assumes that the probability distribution over the competitors' valuations of the auctioned item is known. We use simulations of the combined auction- and production-planning system to obtain crude approximations of these probability distributions automatically. The resulting auction agents are part of a complete supply-chain management system and seamlessly combine ideas from auction theory, utility theory, and dynamic programming.
A reactive robot architecture with planning on demand

In this paper, we describe a reactive robot architecture that uses fast replanning methods to avoid the shortcomings of reactive navigation, such as getting stuck in box canyons or in front of small openings. Our robot architecture differs from other robot architectures in that it gives planning progressively greater control of the robot if reactive navigation continues to fail, until planning controls the robot directly. Our first experiments on a Nomad robot and in simulation demonstrate that our robot architecture promises to simplify the programming of reactive robot architectures and results in robust navigation, smooth trajectories, and reasonably good navigation performance.
Improved analysis of greedy mapping

We analyze greedy mapping, a simple mapping method that has successfully been used on mobile robots. Greedy mapping moves the robot from its current location on a shortest path towards a closest unvisited, unscanned or informative location, until the terrain is mapped. Previous work has resulted in upper and lower bounds on its worst-case travel distance but there was a large gap between the bounds. In this paper, we reduce the gap substantially by decreasing the upper bound from /spl Oscr/;(|V|/sup 3/2/) to /spl Oscr/;(|V|ln|V|) edge traversals, where |V| is the number of vertices of the graph. This upper bound demonstrates that the travel distance of greedy mapping is guaranteed to be small and thus suggests that greedy mapping is indeed a reasonable mapping method. The guaranteed good performance of greedy mapping is robust in that it holds for different versions of greedy mapping, regardless of sensor type and sensor range.
The Fifth Symposium on Abstraction, Reformulation, and Approximation (SARA-2002)

The Fifth International Symposium on Abstraction, Reformulation, and Approximation (SARA-2002) was held from 2 to 4 August 2002 in Kananaskis, Alberta, Canada. This interdisciplinary conference brought together researchers from around the world to present recent progress on, and exchange ideas about, how abstraction, reformulation, and approximation techniques can be used in areas such as automatic programming, constraint satisfaction, design, diagnosis, machine learning, search, planning, reasoning, game playing, scheduling, and theorem proving.
Robot exploration with combinatorial auctions

We study how to coordinate a team of mobile robots to visit a number of given targets in a partially unknown terrain. Robotics researchers have studied single-item auctions to perform this exploration task but these do not make synergies between the targets into account. We therefore design combinatorial auctions, propose different combinatorial bidding strategies and compare their performance with each other, as well as to single item auctions and an optimal centralized mechanism. Our computational results in teambots, a multi-robot simulator, indicate that combinatorial auctions generally lead to significantly superior team performance than single-item auctions, and generate very good results compared to an optimal centralized mechanism.
Trail-laying robots for robust terrain coverage

Robotics researchers have studied robots that can follow the trails laid by other robots. We, on the other hand, study robots that leave trails in the terrain to cover closed terrain once or repeatedly. How to design such ant robots has so far been studied only theoretically for gross robot simplifications. In this paper, we describe for the first time how to build physical ant robots that cover terrain. We show that a modified version of node counting can model the behavior of the ant robots and report on first experiments that we performed to understand their behavior better. These experiments confirm that our ant robots indeed cover terrain robustly even if the trails are of uneven quality, the ant robots are moved without realizing this, or some trails are destroyed. Finally, we report the results of a large-scale experiment where ten simulated ant robots covered a factory floor of 25 by 25 meters repeatedly over 85 hours without any ant robots getting stuck.
Robot Localization and Exploration with Agent-Centered Search

In this article, we describe agent-centered search and illu strate this planning paradigm with examples from robot localization and exploration. Agent-centered search method s interleave planning and plan execution and restrict planni ng to the part of the domain around the current state of the agent. They can execute actions in the presence of time constraints and often have a small sum of planning and plan-execution time, both because they trade-off planning and plan-execution time and because they allow agents to gather information early in nondeterministic domains, whi ch reduces the amount of planning they have to perform for unencountered situations. These advantages become importan t as more and more intelligent systems are interfaced with the world and have to operate autonomously in complex environments. Agent-centered search methods have been applied to a variety of domains, including traditional search, STRIPS type planning, moving-target search, planning with totall y and partially observable Markov decision processes models , reinforcement learning, and robot navigation. We discuss the design and properties of several agent-centered search methods, focusing on robot localization and exploration.
Incremental replanning for mapping

Incremental heuristic search methods can often replan paths much faster than incremental or heuristic search methods individually, yet are simple to use. So far, they have only been used in mobile robotics to move a robot to given goal coordinates in unknown terrain. As far as we know, incremental heuristic search methods have not yet been applied to the problem of mapping unknown terrain. In this paper we therefore describe how to apply our incremental heuristic search method D* Lite, that combines ideas from Lifelong Planning A* and Focussed D*, to mapping unknown terrain, which is rather nontrivial. We then compare its runtime against that of incremental search and heuristic search alone, demonstrating the computational benefits of their combination. By demonstrating the versatility and computational benefits of incremental heuristic search, we hope that this underexploited technique will be used more often in mobile robotics.
Abstraction, Reformulation, and Approximation: 5th International Symposium, SARA 2002, Kananaskis, Alberta, Canada, August 2-4, 2002, Proceedings

Invited Presentations.- Model Checking and Abstraction.- Reformulation in  Spatiotemporal Abstraction of Stochastic Sequential Processes.- State Space Relaxation and Search Strategies in Dynamic Programming.- Invited Presentations.- Admissible Moves in Two-Player Games.- Dynamic Bundling: Less Effort for More Solutions.- Symbolic Heuristic Search Using Decision Diagrams.- On the Construction of Human-Automation Interfaces by Formal Abstraction.- Pareto Optimization of Temporal Decisions.- An Information-Theoretic Characterization of Abstraction in Diagnosis and Hypothesis Selection.- A Tractable Query Cache by Approximation.- An Algebraic Framework for Abstract Model Checking.- Action Timing Discretization with Iterative-Refinement.- Formalizing Approximate Objects and Theories: Some Initial  Model Minimization in Hierarchical Reinforcement Learning.- Learning Options in Reinforcement Learning.- Approximation Techniques for Non-linear Problems with Continuum of Solutions.- Approximation of Relations by Propositional Formulas: Complexity and Semantics.- Abstracting Visual Percepts to Learn Concepts.- Short Presentations.- PAC Meditation on Boolean Formulas.- On the Reformulation of Vehicle Routing Problems and Scheduling Problems.- The Oracular Constraints  Performance of Lookahead Control Policies in the Face of Abstractions and Approximations.- TTree: Tree-Based State Generalization with Temporally Abstract Actions.- Ontology-Driven Induction of Decision Trees at Multiple Levels of Abstraction.- Research Summaries.- Abstracting Imperfect Information Game Trees.- Using Abstraction for Heuristic Search and Planning.- Approximation Techniques in Multiagent Learning.- Abstraction and Reformulation in GraphPlan.- Abstract Reasoning for Planning and Coordination.-  Abstraction Techniques, and Their Value.- Reformulation of Non-binary Constraints.- Reformulating Combinatorial Optimization as Constraint Satisfaction.- Autonomous Discovery of Abstractions through Interaction with an Environment.- Interface Verification: Discrete Abstractions of Hybrid Systems.- Learning Semi-lattice Codebooks for Image Compression.- Research Summary.- Principled Exploitation of Heuristic Information.- Reformulation of Temporal Constraint Networks.
Towards Building Terrain-Covering Ant Robots

We study robots that leave trails in the terrain to cover closed terrain efficiently and robustly. Such ant robots have so far been studied only theoretically for gross ant robot simplifications in unrealistic settings. In this article, we design ant robots for a realistic robot simulation environment. We discuss how large the markers should be that form the trail, how frequently they should be dropped, how large the sensed floor area below the ant robots should be, how the ant robots should move depending on where the markers are in the sensed area, and how the markers should be deleted to avoid saturating the floor with markers. We then report experiments that we have performed to understand the behavior of the resulting ant robots better, including their efficiency and robustness in situations where they are failing, they are moved without realizing this, and markers are deleted. Finally, we report the results of a large-scale experiment where ten ant robots covered an area of 25 by 25 meters repeatedly over 85 hours.
Speeding up the calculation of heuristics for heuristic search-based planning

Heuristic search-based planners, such as HSP 2.0, solve STRIPS-style planning problems efficiently but spend about eighty percent of their planning time on calculating the heuristic values. In this paper, we systematically evaluate alternative methods for calculating the heuristic values for HSP 2.0 and demonstrate that the resulting planning times differ substantially. HSP 2.0 calculates each heuristic value by solving a relaxed planning problem with a dynamic programming method similar to value iteration. We identify two different approaches for speeding up the calculation of heuristic values, namely to order the value updates and to reuse information from the calculation of previous heuristic values. We then show how these two approaches can be combined, resulting in our PINCH method. PINCH outperforms both of the other approaches individually as well as the methods used by HSP 1.0 and HSP 2.0 for most of the large planning problems tested. In fact, it speeds up the planning time of HSP 2.0 by up to eighty percent in several domains and, in general, the amount of savings grows with the size of the domains, allowing HSP 2.0 to solve larger planning problems than was possible before in the same amount of time and without changing its overall operation.
The interaction of representations and planning objectives for decision-theoretic planning tasks

This article studies decision-theoretic planning or reinforcement learning in the presence of traps such as steep slopes for outdoor robots or staircases for indoor robots. In this case, achieving the goal from the start is often the primary objective while minimizing the travel time is only of secondary importance. This article studies how this planning objective interacts with possible representations of the planning tasks, namely whether to use a discount factor that is one or smaller than one and whether to use the action-penalty or the goal-reward representation. It is shown that the action-penalty representation without discounting guarantees that the plan that maximizes the expected reward also achieves the goal from the start (provided that this is possible) but neither the action-penalty representation with discounting nor the goal-reward representation with discounting have this property. The article then shows exactly when this trapping phenomenon occurs, using a novel interpretation of discounting, namely that it models agents that use convex exponential utility functions and thus are optimistic in the face of uncertainty. Finally, it is shown how the selective state-deletion method can be used in conjunction with standard decision-theoretic planners to eliminate the trapping phenomenon.
Improved fast replanning for robot navigation in unknown terrain

Mobile robots often operate in domains that are only incompletely known, for example, when they have to move from given start coordinates to given goal coordinates in unknown terrain. In this case, they need to be able to replan quickly as their knowledge of the terrain changes. Stentz' Focussed Dynamic A* is a heuristic search method that repeatedly determines a shortest path from the current robot coordinates to the goal coordinates while the robot moves along the path. It is able to replan one to two orders of magnitudes faster than planning from scratch since it modifies previous search results locally. Consequently, it has been extensively used in mobile robotics. In this paper, we introduce an alternative to Focussed Dynamic A* that implements the same navigation strategy but is algorithmically different. Focussed Dynamic A* Lite is simpler, easier to understand, easier to analyze and easier to extend than Focussed Dynamic A*, yet is more efficient. We believe that our results will make D*-like replanning algorithms even more popular and enable robotics researchers to adapt them to additional applications.
Heuristic Search-Based Replanning

Many real-world planning problems require one to solve a series of similar planning tasks. In this case, replanning can be much faster than planning from scratch. In this paper, we introduce a novel replanning method for symbolic planning with heuristic search-based planners, currently the most popular planners. Our SHERPA replanner is not only the first heuristic search-based replanner but, different from previous replanners for other planning paradigms, it also guarantees that the quality of its plans is as good as that achieved by planning from scratch. We provide an experimental feasibility study that demonstrates the promise of SHERPA for heuristic search-based replanning.
Greedy mapping of terrain

We study a greedy mapping method that always moves the robot from its current location to the closest location that it has not visited (or observed) yet, until the terrain is mapped. Although one does not expect such a simple mapping method to minimize the travel distance of the robot, we present analytical results that show (perhaps surprisingly) that the travel distance of the robot is reasonably small. This is interesting because greedy mapping has a number of desirable properties. It is simple to implement and integrate into complete robot architectures. It does not need to have control of the rebut at all times, takes advantage of prior knowledge about parts of the terrain (if available), and can be used by several robots cooperatively.
Greedy localization

We show that finding localization plans with optimal worst-case execution time for localization tasks with short-range sensors in discretized domains is NP-hard, even within a logarithmic factor. This strongly suggests that finding and executing localization plans with optimal or even near-optimal worst-case execution time cannot be done in polynomial time. Greedy localization methods interleave planning and execution and keep the amount of planning performed between moves small. We analyze one such greedy localization method, the delayed planning architecture, and show that it can find and execute localization plans in polynomial time and thus substantially reduce the sum of planning and execution time compared to localization methods that find localization plans with optimal or near-optimal execution time. We also characterize how suboptimal the execution time of its localization plans can be. These results provide a first step towards analyzing other greedy localization methods.
Agent-Centered Search

In this article, I describe agent-centered search (also called real-time search or local search) and illustrate this planning paradigm with examples. Agent-centered search methods interleave planning and plan execution and restrict planning to the part of the domain around the current state of the agent, for example, the current location of a mobile robot or the current board position of a game. These methods can execute actions in the presence of time constraints and often have a small sum of planning and execution cost, both because they trade off planning and execution cost and because they allow agents to gather information early in nondeterministic domains, which reduces the amount of planning they have to perform for unencountered situations. These advantages become important as more intelligent systems are interfaced with the world and have to operate autonomously in complex environments. Agent-centered search methods have been applied to a variety of domains, including traditional search, strips-type planning, moving-target search, planning with totally and partially observable Markov decision process models, reinforcement learning, constraint satisfaction, and robot navigation. I discuss the design and properties of several agent-centered search methods, focusing on robot exploration and localization.
Risk-Averse Auction Planning and its Integration into Supply Chain Management Systems

Auctions are an important means for purchasing materials. Consequently, a supply chain management system has to be able to decide whether to participate in auctions and how much to bid. To address these issues, we generalize results from auction theory in several ways. First, auction theory often assumes that decision makers want to maximize their expected profits. However, decision makers are often risk-averse when faced with the possibility of losing the auction and then incurring huge penalties for not being able to satisfy some orders. We take their risk attitudes into account by changing the objective from maximizing the expected profit to maximizing the expected utility of the profit according to a risk-averse utility function. Second, auction theory often assumes that decision makers know their valuations for the auctioned item. However, their valuations depend on how they can use the item in the production process. We therefore integrate auction strategies into a production planning system to derive the valuation automatically. Third, auction theory often assumes that the probability distribution over the competitors’ valuations is known. We use simulations of the production planning system with integrated auction strategies to approximate these probability distributions automatically. The combination of these three research contributions results in a prototype of a supply chain management system with integrated auction strategies for the paper industry.
Lifelong Planning for Mobile Robots

Mobile robots often have to replan as their knowledge of the world changes. Lifelong planning is a paradigm that allows them to replan much faster than with complete searches from scratch, yet finds optimal solutions. To demonstrate this paradigm, we apply it to Greedy Mapping, a simple sensor-based planning method that always moves the robot from its current cell to a closest cell with unknown blockage status, until the terrain is mapped. Greedy Mapping has a small mapping time, makes only action recommendations and can thus coexist with other components of a robot architecture that also make action recommendations, and is able to take advantage of prior knowledge of parts of the terrain (if available). We demonstrate how a robot can use our lifelong-planning version of A* to repeatedly determine a shortest path from its current cell to a closest cell with unknown blockage status. Our experimental results demonstrate the advantage of lifelong planning for Greedy Mapping over other search methods. Similar results had so far been established only for goal-directed navigation in unknown terrain.