nils-herrmann/clean_scirepeval huggingface dataset:
Preprocessing techniques for accelerating the DCOP algorithm ADOPT

Methods for solving Distributed Constraint Optimization Problems (DCOP) have emerged as key techniques for distributed reasoning. Yet, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have successfully been used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of different preprocessing techniques that are based on dynamic programming and speed up ADOPT, an asynchronous complete and optimal DCOP algorithm. We investigate when preprocessing is useful and which factors influence the resulting speedups in two DCOP domains, namely graph coloring and distributed sensor networks. Our experimental results demonstrate that our preprocessing techniques are fast and can speed up ADOPT by an order of magnitude.
Multi-robot forest coverage

One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. Terrain coverage is crucial for lawn mowing, cleaning, harvesting, search-and-rescue, intrusion detection and mine clearing. Naturally, coverage can be sped up with multiple robots. In this paper, we describe multi-robot forest coverage, a new multi-robot coverage algorithm based on an algorithm by Even et al. (2004) for finding a tree cover with trees of balanced weights. The cover time of multi-robot forest coverage is at most eight times larger than optimal, and our experiments show it to perform significantly better than existing multi-robot coverage algorithms.
Decision-theoretic planning under risk-sensitive planning objectives

Risk attitudes are important for human decision making, especially in scenarios where huge wins or losses are possible, as exemplified by planetary rover navigation, oilspill response, and business applications. Decision-theoretic planners therefore need to take risk aspects into account to serve their users better. However, most existing decision-theoretic planners use simplistic planning objectives that are risk-neutral. The thesis research is the first comprehensive study of how to incorporate risk attitudes into decision-theoretic planners and solve large-scale planning problems represented as Markov decision process models. The thesis consists of three parts. 
The first part of the thesis work studies risk-sensitive planning in case where exponential utility functions are used to model risk attitudes. I show that existing decision-theoretic planners can be transformed to take risk attitudes into account. Moreover, different versions of the transformation are needed if the transition probabilities are implicitly given, namely, temporally extended probabilities and probabilities given in a factored form. 
The second part of the thesis work studies risk-sensitive planning in case where general nonlinear utility functions are used to model risk attitudes. I show that a state-augmentation approach can be used to reduce a risk-sensitive planning problem to a risk-neutral planning problem with an augmented state space. I further use a functional interpretation of value functions and approximation methods to solve the planning problems efficiently with value iteration. I also show an exact method for solving risk-sensitive planning problems where one-switch utility functions are used to model risk attitudes. 
The third part of the thesis work studies risk sensitive planning in case where arbitrary rewards are used. I propose a spectrum of conditions that can be used to constrain the utility function and the planning problem so that the optimal expected utilities exist and are finite. I prove that the existence and finiteness properties hold for stationary plans, where the action to perform in each state does not change over time, under different sets of conditions.
The Generation of Bidding Rules for Auction-Based Robot Coordination

Robotics researchers have used auction-based coordination systems for robot teams because of their robustness and efficiency. However, there is no research into systematic methods for deriving appropriate bidding rules for given team objectives. In this paper, we propose the first such method and demonstrate it by deriving bidding rules for three possible team objectives of a multi-robot exploration task. We demonstrate experimentally that the resulting bidding rules indeed exhibit good performance for their respective team objectives and compare favorably to the optimal performance. Our research thus allows the designers of auction-based coordination systems to focus on developing appropriate team objectives, for which good bidding rules can then be derived automatically.
Existence and Finiteness Conditions for Risk-Sensitive Planning: Results and Conjectures

Decision-theoretic planning with risk-sensitive planning objectives is important for building autonomous agents or decision-support systems for real-world applications. However, this line of research has been largely ignored in the artificial intelligence and operations research communities since planning with risk-sensitive planning objectives is more complicated than planning with risk-neutral planning objectives. To remedy this situation, we derive conditions that guarantee that the optimal expected utilities of the total plan-execution reward exist and are finite for fully observable Markov decision process models with non-linear utility functions. In case of Markov decision process models with both positive and negative rewards, most of our results hold for stationary policies only, but we conjecture that they can be generalized to non stationary policies.
Risk-Sensitive Planning with One-Switch Utility Functions: Value Iteration

Decision-theoretic planning with nonlinear utility functions is important since decision makers are often risk-sensitive in high-stake planning situations. One-switch utility functions are an important class of nonlinear utility functions that can model decision makers whose decisions change with their wealth level. We study how to maximize the expected utility of a Markov decision problem for a given one-switch utility function, which is difficult since the resulting planning problem is not decomposable. We first study an approach that augments the states of the Markov decision problem with the wealth level. The properties of the resulting infinite Markov decision problem then allow us to generalize the standard risk-neutral version of value iteration from manipulating values to manipulating functions that map wealth levels to values. We use a probabilistic blocks-world example to demonstrate that the resulting risk-sensitive version of value iteration is practical.
The Effect of Representation and Knowledge on Goal-Directed Exploration with Reinforcement-Learning Algorithms

We analyze the complexity of on-line reinforcement-learning algorithms applied to goal-directed exploration tasks. Previous work had concluded that, even in deterministic state spaces, initially uninformed reinforcement learning was at least exponential for such problems, or that it was of polynomial worst-case time-complexity only if the learning methods were augmented. We prove that, to the contrary, the algorithms are tractable with only a simple change in the reward structure ("penalizing the agent for action executions") or in the initialization of the values that they maintain. In particular, we provide tight complexity bounds for both Watkins‘ Q-learning and Heger‘s Q-hat-learning and show how their complexity depends on properties of the state spaces. We also demonstrate how one can decrease the complexity even further by either learning action models or utilizing prior knowledge of the topology of the state spaces. Our results provide guidance for empirical reinforcement-learning researchers on how to distinguish hard reinforcement-learning problems from easy ones and how to represent them in a way that allows them to be solved efficiently.
Auction-Based Multi-Robot Routing

Recently, auction methods have been investigated as effective, decentralized methods for multi-robot coordination. Experimental research has shown great potential, but has not been complemented yet by theoretical analysis. In this paper we contribute a theoretical analysis of the performance of auction methods for multi-robot routing. We suggest a generic framework for auction-based multi-robot routing and analyze a variety of bidding rules for different team objectives. This is the first time that auction methods are shown to offer theoretical guarantees for such a variety of bidding rules and team objectives.
A Generalized Framework for Lifelong Planning A* Search

Recently, it has been suggested that Lifelong Planning A* (LPA*), an incremental version of A*, might be a good heuristic search-based replanning method for HSP-type planners. LPA* uses consistent heuristics and breaks ties among states with the same f-values in favor of states with smaller g-values. However, HSP-type planners use inconsistent heuristics to trade off plan-execution cost and planning time. In this paper, we therefore develop a general framework that allows one to develop more capable versions of LPA* and its nondeter-ministic version Minimax LPA*, including versions of LPA* and Minimax LPA* that use inconsistent heuristics and break ties among states with the same f-values in favor of states with larger g-values. We then show experimentally that the new versions of LPA* indeed speed it up on grids and thus promise to provide a good foundation for building heuristic search-based replanners.
Scaling up WA* with Commitment and Diversity

Weighted A* (WA*) is a popular search technique that scales up A* while sacrificing solution quality. Recently, researchers have proposed two variants of WA*: KWA* adds diversity to WA*, and MSC-WA* adds commitment to WA*. In this paper, we demonstrate that there is benefit in combining them. The resulting MSC-KWA* scales up to larger domains than WA*, KWA* and MSC-WA*, which is rather surprising since diversity and commitment at first glance seem to be opposing concepts.
Fast replanning for 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/sup */ (D/sup */) 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 faster than planning from scratch since it modifies its previous search results locally. Consequently, it has been extensively used in mobile robotics. In this article, we introduce an alternative to D/sup */ that determines the same paths and thus moves the robot in the same way but is algorithmically different. D/sup */ Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D/sup */. We believe that our results will make D/sup */-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications.
Limited Discrepancy Beam Search

Beam search reduces the memory consumption of best-first search at the cost of finding longer paths but its memory consumption can still exceed the given memory capacity quickly. We therefore develop BULB (Beam search Using Limited discrepancy Backtracking), a complete memory-bounded search method that is able to solve more problem instances of large search problems than beam search and does so with a reasonable runtime. At the same time, BULB tends to find shorter paths than beam search because it is able to use larger beam widths without running out of memory. We demonstrate these properties of BULB experimentally for three standard benchmark domains.
Bounds on the Travel Cost of a Mars Rover Prototype Search Heuristic

D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars rover prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of $\Omega(n\log n/\log\log n)$ and O(n log n), respectively, on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs we prove an O(n log2 n) upper bound.
PDRRTs: integrating graph-based and cell-based planning

Motion-planning problems can be solved by discretizing the continuous configuration space, for example with graph-based or cell-based techniques. We study rapidly exploring random trees (RRTs) as an example of graph-based techniques and the parti-game method as an example of cell-based techniques. We then propose parti-game directed RRTs (PDRRTs) as a novel technique that combines them. PDRRTs are based on the parti-game method but use RRTs as local controllers rather than the simplistic controllers used by the parti-game method. Our experimental results show that PDRRTs plan faster and solve more motion-planning problems than RRTs and plan faster and with less memory than the parti-game method.
Incremental Heuristic Search in Artificial Intelligence

Incremental search reuses information from previous searches to find solutions to a series of similar search problems potentially faster than is possible by solving each search problem from scratch. This is important since many artificial intelligence systems have to adapt their plans continuously to changes in (their knowledge of) the world. In this article, we therefore give an overview of incremental search, focusing on Lifelong Planning A*, and outline some of its possible applications in artificial intelligence.
Efficient and inefficient ant coverage methods

Ant robots are simple creatures with limited sensing and computational capabilities. They have the advantage that they are easy to program and cheap to build. This makes it feasible to deploy groups of ant robots and take advantage of the resulting fault tolerance and parallelism. We study, both theoretically and in simulation, the behavior of ant robots for one-time or repeated coverage of terrain, as required for lawn mowing, mine sweeping, and surveillance. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. To overcome these limitations, we study navigation methods that are based on real-time (heuristic) search and leave markings in the terrain, similar to what real ants do. These markings can be sensed by all ant 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 ant robots do not even need to be localized, which completely eliminates solving difficult and time-consuming localization problems. We study two simple real-time search methods that differ only in how the markings are updated. We show experimentally that both real-time search methods robustly cover terrain even if the ant robots are moved without realizing this (say, by people running into them), some ant robots fail, and some markings get destroyed. Both real-time search methods are algorithmically similar, and our experimental results indicate that their cover time is similar in some terrains. Our analysis is therefore surprising. We show that the cover time of ant robots that use one of the real-time search methods is guaranteed to be polynomial in the number of locations, whereas the cover time of ant robots that use the other real-time search method can be exponential in (the square root of) the number of locations even in simple terrains that correspond to (planar) undirected trees.
Building Terrain-Covering Ant Robots: A Feasibility Study

Robotics researchers have studied robots that can follow trails laid by other robots. We, on the other hand, study robots that leave trails in the terrain to cover closed terrain repeatedly. How to design such ant robots has so far been studied only theoretically for gross robot simplifications. In this article, we describe for the first time how to build physical ant robots that cover terrain and test their design both in realistic simulation environments and on a Pebbles III robot. We show that the coverage behavior of our ant robots can be modeled with a modified version of node counting, a real-time search method. We then report on first experiments that we performed to understand their efficiency and robustness in situations where some ant robots fail, they are moved without realizing this, the trails are of uneven quality, and some trails are destroyed. Finally, we report the results of a large-scale simulation experiment where ten ant robots covered a factory floor of 25 by 25 meters repeatedly over 85 hours without getting stuck.
Analysis of Greedy Robot-Navigation Methods

Robots often have to navigate robustly despite incomplete information about the terrain or their location in the terrain. In this case, they often use greedy methods to make planning tractable. In this paper, we analyze two such robot-navigation methods. The first method is Greedy Localization, which determines the location of a robot in known terrain by always moving it to the closest location from which it will make an observation that reduces the number of its possible locations, until it has reduced that number as much as possible. We reduce the upper bound on the number of movements of Greedy Localization from O(n 3 2 ) to O(n log n) on grid graphs and thus close to the known lower bound of Ω(n log n/ log log n), where n is the number of (unblocked) vertices of the graph that discretizes the terrain. The second method is Dynamic A* (D*), which is used on several prototypes of both urban reconnaissance and planetary robots. It moves a robot in initially unknown terrain from given start coordinates to given goal coordinates by always moving the robot on a shortest presumed unblocked path from its current coordinates to the goal coordinates, pretending that unknown terrain is unblocked, until it has reached the goal coordinates or there are no more presumed unblocked paths. We reduce the upper bound on the number of movements of D* from O(n 3 2 ) to O(n log n) on arbitrary graphs and O(n log n) on planar graphs (including grid graphs) and thus close to the known lower bound of Ω(n log n/ log log n), where n is the number of (blocked and unblocked) vertices of the graph that discretizes the terrain.
The Fourteenth International Conference on Automated Planning and Scheduling (ICAPS-04)

The Fourteenth International Conference on Automated Planning and Scheduling (ICAPS-04) was held in Canada in June of 2004. It covered the latest theoretical and empirical advances in planning and scheduling. The conference program consisted of tutorials, workshops, a doctoral consortium, and three days of technical paper presentations in a single plenary track, one day of which was jointly organized with the Ninth International Conference on Principles of Knowledge Representation and Reasoning. ICAPS-04 also hosted the International Planning Competition, including a classical track and a newly formed probabilistic track. This report describes the conference in more detail.
Simple auctions with performance guarantees for multi-robot task allocation

We consider the problem of allocating a number of exploration tasks to a team of mobile robots. Each task consists of a target location that needs to be visited by a robot. The objective of the allocation is to minimize the total cost, that is, the sum of the travel costs of all robots for visiting all targets. We show that finding an optimal allocation is an NP-hard problem, even in known environments. The main contribution of this paper is PRIM ALLOCATION, a simple and fast approximate algorithm for allocating targets to robots which provably computes allocations whose total cost is at most twice as large as the optimal total cost. We then cast PRIM ALLOCATION in terms of a multi-round single-item auction where robots bid on targets, which allow for a decentralized implementation. To the best of our knowledge, PRIM ALLOCATION is the first auction-based allocation algorithm that provides a guarantee on the quality of its allocations. Our experimental results in a multi-robot simulator demonstrate that PRIM ALLOCATION is fast and results in close-to-optimal allocations despite its simplicity and decentralized nature. In particular, it needs an order of magnitude fewer bids than a computationally intensive allocation algorithm based on combinatorial auctions, yet its allocations are at least as good.
Preprocessing Techniques for Distributed Constraint Optimization

Although algorithms for Distributed Constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have been successfully used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of very different preprocessing techniques that speed up ADOPT, an asynchronous optimal DCOP algorithm that significantly outperforms competing DCOP algorithms by more than one order of magnitude.
A comparison of fast search methods for real-time situated agents

Real-time situated agents, including characters in real-time computer games, often do not know the terrain in advance but automatically observe it within a certain range around them. They have to interleave planning with movement to make planning tractable when moving autonomously to user-specified coordinates. Planning faces real-time requirements since it is important that the agents be responsive to the commands of the users and move smoothly. In this paper, we compare two fast search methods for this task that speed up planning in different ways, namely real-time heuristic search (LRTA*) and incremental heuristic search (D* Lite), resulting in the first comparison of real-time and incremental heuristic search in the literature. We characterize when to choose which search method, depending on the kind of terrain and the planning objective.
The effect of representation and knowledge on goal-directed exploration with reinforcement-learning algorithms

We analyze the complexity of on-line reinforcement-learning algorithms applied to goal-directed exploration tasks. Previous work had concluded that, even in deterministic state spaces, initially uninformed reinforcement learning was at least exponential for such problems, or that it was of polynomial worst-case time-complexity only if the learning methods were augmented. We prove that, to the contrary, the algorithms are tractable with only a simple change in the reward structure ("penalizing the agent for action executions") or in the initialization of the values that they maintain. In particular, we provide tight complexity bounds for both Watkins' Q-learning and Heger's Q-hat-learning and show how their complexity depends on properties of the state spaces. We also demonstrate how one can decrease the complexity even further by either learning action models or utilizing prior knowledge of the topology of the state spaces. Our results provide guidance for empirical reinforcement-learning researchers on how to distinguish hard reinforcement-learning problems from easy ones and how to represent them in a way that allows them to be solved efficiently.