bluuebunny/crossref_metadata_2025 huggingface dataset:
Smelly Maps: The Digital Life of Urban Smellscapes
Authors: Quercia Daniele , Schifanella Rossano , Aiello Luca Maria , McLean Kate
Published: November 2022

Smell has a huge influence over how we perceive places. Despite its importance, smell has been crucially overlooked by urban planners and scientists alike, not least because it is difficult to record and analyze at scale. One of the authors of this paper has ventured out in the urban world and conducted ``smellwalks'' in a variety of cities: participants were exposed to a range of different smellscapes and asked to record their experiences. As a result, smell-related words have been collected and classified, creating the first dictionary for urban smell. Here we explore the possibility of using social media data to reliably map the smells of entire cities. To this end, for both Barcelona and London, we collect geo-referenced picture tags from Flickr and Instagram, and geo-referenced tweets from Twitter. We match those tags and tweets with the words in the smell dictionary. We find that smell-related words are best classified in ten categories. We also find that specific categories (e.g., industry, transport, cleaning) correlate with governmental air quality indicators, adding validity to our study.
Algorithmically Bypassing Censorship on Sina Weibo with Nondeterministic Homophone Substitutions
Authors: Hiruncharoenvate Chaya , Lin Zhiyuan , Gilbert Eric
Published: November 2022

Like traditional media, social media in China is subject to censorship. However, in limited cases, activists have employed homophones of censored keywords to avoid detection by keyword matching algorithms. In this paper, we show that it is possible to scale this idea up in ways that make it difficult to defend against. Specifically, we present a non-deterministic algorithm for generating homophones that create large numbers of false positives for censors, making it difficult to locate banned conversations. In two experiments, we show that 1) homophone-transformed weibos posted to Sina Weibo remain on-site three times longer than their previously censored counterparts, and 2) native Chinese speakers can recover the original intent behind the homophone-transformed messages, with 99% of our posts understood by the majority of our participants. Finally, we find that coping with homophone transformations is likely to cost the Sina Weibo censorship apparatus an additional 15 hours of human labor per day, per censored keyword. To conclude, we reflect briefly on the opportunities presented by this algorithm to build interactive, client-side tools that promote free speech.
Predicting User Engagement on Twitter with Real-World Events
Authors: Hu Yuheng , Farnham Shelly , Talamadupula Kartik
Published: November 2022

People invest time, attention, and emotion while engaging in various activities in the real-world, for either purposes of awareness or participation. Social media platforms such as Twitter offer tremendous opportunities for people to become engaged in such real-world events through information sharing and communicating about these events. However, little is understood about the factors that affect people's Twitter engagement in such real-world events. In this paper, we address this question by first operationalizing a person's Twitter engagement in real-world events such as posting, retweeting, or replying to tweets about such events. Next, we construct statistical models that examine multiple predictive factors associated with four different perspectives of users' Twitter engagement, and quantify their potential influence on predicting the (i) presence; and (ii) degree — of the user's engagement with 643 real-world events. We also consider the effect of these factors with respect to a finer granularization of the different categories of events. We find that the measures of people's prior Twitter activities, topical interests, geolocation, and social network structures are all variously correlated to their engagement with real-world events.
Covering the Egonet: A Crowdsourcing Approach to Social Circle Discovery on Twitter
Authors: Dykstra Karmen , Lijffijt Jefrey , Gionis Aristides
Published: November 2022

Twitter and other social media provide the functionality of manually grouping users into lists. The goal is to enable selective viewing of content and easier information acquisition. However, creating lists manually requires significant time and effort. To mitigate this effort, a number of recent methods attempt to create lists automatically using content and/or network structure, but results are far from perfect. In this work, we study the power of the millions of lists that are already created by other twitter users in order to “crowdsource” the task of list creation. We find that in a large dataset, collected specifically for this study, an optimal matching of existing lists from other twitter users to the ground-truth lists in egonets gives an F1 score of 0.43, while the best existing method achieves only 0.21. We explore the informativeness of features derived from network structure, existing lists, and posted content. We observe that different types of features are informative for different lists, and introduce a simple algorithm for ranking candidate lists. The proposed algorithm outperforms existing methods, but still falls short of the optimal selection of existing lists.
Signals of Expertise in Public and Enterprise Social Q&A
Authors: Pan Shimei , Mayfield Elijah , Lu Jie , Lai Jennifer
Published: November 2022

The success of internet social question-answering (Q&A) sites has led businesses to attempt to duplicate this model in- ternally. In such systems, demand for expertise is high, mean- ing that finding high-quality answers quickly is a top priority. Prior work on expertise discovery, though, has focused on high-traffic public websites like StackExchange. Here, we show that the most predictive metadata features from public websites do not transfer well to the enterprise.
Exemplar-Based Topic Detection in Twitter Streams
Authors: Elbagoury Ahmed , Ibrahim Rania , Farahat Ahmed , Kamel Mohamed , Karray Fakhri
Published: November 2022

Detecting topics in Twitter streams has been gaining an increasing amount of attention. It can be of great support for communities struck by natural disasters, and could assist companies and political parties understand users' opinions and needs. Traditional approaches for topic detection focus on representing topics using terms, are negatively affected by length limitation and the lack of context associated with tweets.In this work, we propose an Exemplar-based approach for topic detection, in which detected topics are represented using a few selected tweets. Using exemplar tweets instead of a set of key words allows for an easy interpretation of the meaning of the detected topics. Experimental evaluation on benchmark Twitter datasets shows that the proposed topic detection approach achieves the best term precision. It does this while maintaining good topic recall and running time compared to other approaches.
Contextualized Sarcasm Detection on Twitter
Authors: Bamman David , Smith Noah
Published: November 2022

Sarcasm requires some shared knowledge between speaker and audience; it is a profoundly contextual phenomenon.  Most computational approaches to sarcasm detection, however, treat it as a purely linguistic matter, using information such as lexical cues and their corresponding sentiment as predictive features.  We show that by including extra-linguistic information from the context of an utterance on Twitter — such as properties of the author, the audience and the immediate communicative environment — we are able to achieve gains in accuracy compared to purely linguistic features in the detection of this complex phenomenon, while also shedding light on features of interpersonal interaction that enable sarcasm in conversation.
Event-Based Clustering for Reducing Labeling Costs of Event-related Microposts
Authors: Schulz Axel , Janssen Frederik , Ristoski Petar , Fürnkranz Johannes
Published: November 2022

Automatically identifying the event type of event-related information in the sheer amount of social media data makes machine learning inevitable. However, this is highly dependent on (1) the number of correctly labeled instances and (2) labeling costs. Active learning has been proposed to reduce the number of instances to label. Albeit the thematic dimension is already used, other metadata such as spatial and temporal information that is helpful for achieving a more fine-grained clustering is currently not taken into account. In this paper, we present a novel event-based clustering strategy that makes use of temporal, spatial, and thematic metadata to determine instances to label. An evaluation on incident-related tweets shows that our selection strategy for active learning outperforms current state-of-the-art approaches even with few labeled instances.
Conversing in Reflective Glory: A Systematic Study Using National Football League Games
Authors: Margolin Drew , Liao Wang , Lin Yu-Ru
Published: November 2022

Conversations about a group can alter its structure and development. The antecedents of group-oriented conversation are difficult to pinpoint, however, because of the complex interdependence between individual and group behavior. In this study we utilize a unique set of exogenous, group-level treatments — the outcomes of National Football League games — to observe how group members — fans of these teams — participate in group-oriented conversation on Twitter. We show first that positive group outcomes (team victories) encourage group members to talk publicly about their group. Our results also indicate that group members participate more actively in the group-oriented discussion when the the outcome is a surprise. Future directions for this line of research are discussed.
“I Don’t Have a Photograph, But You Can Have My Footprints." – Revealing the Demographics of Location Data
Authors: Riederer Christopher , Zimmeck Sebastian , Phanord Coralie , Chaintreau Augustin , Bellovin Steven
Published: November 2022

High accuracy location data are routinely available to a plethora of mobile apps and web services. The availability of such data lead to a better general understanding of human mobility. However, as location data are usually not associated with demographic information, little work has been done to understand the differences in human mobility across demographics. In this study we begin to fill the void. In particular, we explore how the growing number of geotagged footprints that social network users create can reveal demographic attributes and how these footprints enable the understanding of mobility at a demographic level. Our methodology gives rise to novel opportunities in the study of mobility. We leverage publicly available geotagged photographs from a popular photosharing network to build a dataset on demographic mobility patterns. Our analysis of this dataset not only reproduces previous results on mobility behavior at various geographical levels but further extends the existing picture: it allows for the refinement of mobility modeling from entire populations to specific demographic groups. Our analysis suggests the existence of regional variations in mobility and reveals statistically significant differences in mobility between genders and ethnicities.
Answering Complex Queries in an Online Community Network
Authors: Nazi Azade , Thirumuruganathan Saravanan , Hristidis Vagelis , Zhang Nan , Das Gautam
Published: November 2022

An online community network such as Twitter or amazon.com links entities (e.g., users, products) with various relationships (e.g., friendship, co-purchase) and make such information available for access through a web interface. The web interfaces of these networks often support features such as keyword search and "get-neighbors" — so a visitor can quickly find entities (e.g., users/products) of interest. Nonetheless, the interface is usually too restrictive to answer complex queries such as (1) find 100 Twitter users from California with at least 100 followers who talked about ICWSM last year or (2) find 100 books with at least 200 5-star reviews at amazon.com. In this paper, we introduce the novel problem of answering complex queries that involve non-searchable attributes through the web interface of an online community network. We model such a network as a heterogeneous graph with two access channels, Content Search and Local Search. We propose a unified approach that transforms the complex query into a small number of supported ones based on a strategic query-selection process. We conduct comprehensive experiments on Twitter and amazon.com which demonstrate the efficacy of our proposed algorithms.
Population Bias in Geotagged Tweets
Authors: Malik Momin , Lamba Hemank , Nakos Constantine , Pfeffer Jürgen
Published: November 2022

Geotagged tweets are an exciting and increasingly popular data source, but like all social media data, they potentially have biases in who are represented. Motivated by this, we investigate the question, 'are users of geotagged tweets randomly distributed over the US population'? We link approximately 144 million geotagged tweets within the US, representing 2.6m unique users, to high-resolution Census population data and carry out a statistical test by which we answer this question strongly in the negative. We utilize spatial models and integrate further Census data to investigate the factors associated with this nonrandom distribution. We find that, controlling for other factors, population has no effect on the number of geotag users, and instead it is predicted by a number of factors including higher median income, being in an urban area, being further east or on a coast, having more young people, and having high Asian, Black or Hispanic/Latino populations.
What Women Like: A Gendered Analysis of Twitter Users' Interests based on a Twixonomy
Authors: Faralli Stefano , Stilo Giovanni , Velardi Paola
Published: November 2022

In this paper we analyze the distribution of interests in a large population of Twitter users (the full set of 40 million users in 2009 and a sample of about 100 thousand New York users in 2014), as a function of gender. To model interests, we associate "topical" friends in users' friendship lists (friends representing an interest rather than a social relation between peers) with Wikipedia categories. A word-sense disambiguation algorithm is used for selecting the appropriate wikipage for each topical friend. Starting from the set of wikipages representing the population's interests, we extract the sub-graph of Wikipedia categories connected to these pages, and we then prune cycles to induce a direct acyclic graph, that we call Twixonomy. We use a novel method for reducing the computational requirements of cycle detection on very large graphs. For any category at any generalization level in the Twixonomy, it is then possible to estimate the gender distribution of Twitter users interested in that category. We analyze both the population of "celebrities", i.e. male and female Twitter users with an associated wikipage, and the population of "peers", i.e. male and female users who follow celebrities.
Exploratory Access to Wikipedia through Faceted Dynamic Taxonomies
Authors: Sacco Giovanni
Published: November 2022

Users currently access Wikipedia through two traditional paradigms, text search and hypertext navigation. We believe that user access can be significantly improved by supporting a systematic conceptual exploration of the knowledge base through dynamic taxonomies with a faceted taxonomy organization. This approach allows the easy manipulation of sets of documents and the systematic and intuitive exploration of complex knowledge bases.
Inconsistency between Salience and the Dynamics of Changes: The Information War on Wikipedia (Research Proposal)
Authors: Labzina Elena
Published: November 2022

Informational wars are not new phenomena. However, nowadays, with the increasing role of the Internet and the growth of networked sources that rely on collective intelligence, manipulation of the information online, especially in supposedly trustworthy sources, becomes of a special interest. Indeed, biased information that is uncritically believed may shift the individual incentives and let those who are responsible for the manipulation virtually affect the flow of the history. This proposal is for a paper that intends to investigate the conflicts and changes in the Wikipedia articles before their topic became salient as a result of a certain political event. The paper proposes that such changes may be suspected to be a part of the preparation of the public for the event
Branch-and-Bound for the Precedence Constrained Generalized Traveling Salesman Problem
Authors: Salman Raad , Ekstedt Fredrik , Damaschke Peter
Published: November 2022

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 hours.
Solving the Watchman Route Problem on a Grid with Heuristic Search
Authors: Seiref Shawn , Jaffey Tamir , Lopatin Margarita , Felner Ariel
Published: November 2022

In this paper we optimally solve the Watchman Route Problem (WRP) on a grid. We are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one c ll on the path. WRP is a reminiscent but is different from graph covering and mapping problems which are done online on an unknown graph. We formalize WRP as a heuristic search problem and solve it with an A*-based algorithm. We develop a series of admissible heuristics with increasing difficulty and accuracy. In particular, our heuristics abstract the problem into line-of-sight clusters graph. Then, solutions for the minimum spanning tree (MST) and the traveling salesman problem (TSP) on this graph are used as admissible heuristics for WRP. We theoretically and experimentally study these heuristics and show that we can optimally and suboptimally solve problems of increasing difficulties.
New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding
Authors: Li Jiaoyang , Gange Graeme , Harabor Daniel , Stuckey Peter , Ma Hang , Koenig Sven
Published: November 2022

We consider two new types of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage but in opposite directions. The second, target symmetry, arises when the shortest path of one agent requires the target location of a second agent after the second agent has already arrived. These symmetries can produce an exponential blowup in the space of possible collision resolutions, leading to timeout failure even for state-of-the-art algorithms such as Conflict-Based Search. We propose to break symmetries using new reasoning techniques that: (1) detect each type of situation and, (2) resolve them by introducing specialized constraints. We implement our ideas in the context of Conflict-Based Search where, in a range of experiments, we report up to an order-of-magnitude improvement in runtime performance and, in some cases, more than a doubling in success rate.
Multi-Resolution A*
Authors: Du Wei , Islam Fahad , Likhachev Maxim
Published: November 2022

Heuristic search-based planning techniques are commonly used for motion planning on discretized spaces. The performance of these algorithms is heavily affected by the resolution at which the search space is discretized. Typically a fixed resolution is chosen for a given domain. While a finer resolution allows better maneuverability, it exponentially increases the size of the state space, and hence demands more search efforts. On the contrary, a coarser resolution gives a fast exploratory behavior but compromises on maneuverability and the completeness of the search. To effectively leverage the advantages of both high and low resolution discretizations, we propose Multi-Resolution A* (MRA*) algorithm, that runs multiple weighted-A*(WA*) searches with different resolution levels simultaneously and combines the strengths of all of them. In addition to these searches, MRA* uses one anchor search to control expansions of other searches. We show that MRA* is bounded suboptimal with respect to the anchor resolution search space and resolution complete. We performed experiments on several motion planning domains including 2D, 3D grid planning and 7 DOF manipulation planning and compared our approach with several search-based and sampling-based baselines.
A New Boolean Encoding for MAPF and its Performance with ASP and MaxSAT Solvers
Authors: Asín Achá Roberto , López Rodrigo , Hagedorn Sebastián , Baier Jorge A.
Published: November 2022

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have proven to be most effective. In this paper, we propose a new encoding for MAPF, which we implement and solve using both ASP and MaxSAT solvers. Our encoding builds on a recent ASP encoding for MAPF but changes the way agent moves are encoded. This allows to represent swap and follow conflicts with binary clauses, which are known to work well along with conflict-based clause learning. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. Our results, over grid and warehouse maps, show that the ASP solver scales better when the number of agents is increased on grids with few obstacles, while the MaxSAT solver performs better in scenarios with more obstacles and fewer agents.
Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds
Authors: Gordon Ofir , Filmus Yuval , Salzman Oren
Published: November 2022

The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity.
Our analysis is based on two complementary approaches:
In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)--a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length.
In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence.
Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least 2 to the power of 10,000,000.
The Closed List Is an Obstacle Too
Authors: Felner Ariel , Shperberg Shahaf S. , Buzhish Hadar
Published: November 2022

The baseline approach for optimal path finding in 4-connected grids is A* with Manhattan Distance. Nevertheless, a large number of enhancements were suggested over the years, usually requiring a preprocessing phase and/or additional memory to store smart lookup tables. In this paper we introduce an enhancement to A* (called BOXA*) on grids which does not need any preprocessing and only needs negligible additional memory. The main idea is to treat the closed-list as a dynamic obstacle. We maintain a list of rectangles which surround CLOSED nodes and calculate an admissible heuristic using the fact that an optimal path from a given node must go around these rectangles. We experimentally show the benefits of this approach on a variety of grid domains.
Pattern Databases for Stochastic Shortest Path Problems
Authors: Klößner Thorsten , Hoffmann Jörg
Published: November 2022

Stochastic shortest-path problems (SSP) are an important subclass of
MDPs for which heuristic search algorithms exist since over a
decade. Yet most known heuristic functions rely on determinization so
do not actually take the transition probabilities into account. The
only exceptions are Trevizan et al.'s heuristics hpom and hroc,
which are geared at solving more complex (constrained) MDPs.
Here we contribute pattern database (PDB) heuristics for SSPs,
including an additivity criterion. These new heuristics turn out to be
very competitive, even when using a simple systematic generation of
pattern collections up to a fixed size. In our experiments, they beat
determinization-based heuristics, and tend to yield better runtimes
than hpom and hroc.
A Planning-Based Approach for In-Station Train Dispatching
Authors: Cardellini Matteo , Maratea Marco , Vallati Mauro , Boleto Gianluca , Oneto Luca
Published: November 2022

In-station train dispatching is the problem of optimising the effective utilisation of available railway infrastructures for mitigating incidents and delays. In this paper, we describe an approach for dealing with the in-station dispatching problem by means of automated planning techniques.
Learning Pseudo-Backdoors for Mixed Integer Programs
Authors: Ferber Aaron , Song Jialin , Dilkina Bistra , Yue Yisong
Published: November 2022

We propose a machine learning approach for quickly solving Mixed Integer Programs (MIP) by learning to prioritize a set of decision variables, which we call pseudo-backdoors, for branching that results in faster solution times. Learning-based approaches have seen success in the area of solving combinatorial optimization problems by being able to flexibly leverage common structures in a given distribution of problems. Our approach takes inspiration from the concept of strong backdoors, which corresponds to a small set of variables such that only branching on these variables yields an optimal integral solution and a proof of optimality. Our notion of pseudo-backdoors corresponds to a small set of variables such that only branching on them leads to faster solve time (which can be solver dependent). A key advantage of pseudo-backdoors over strong backdoors is that they are much amenable to data-driven identification or prediction. Our proposed method learns to estimate the solver performance of a proposed pseudo-backdoor, using a labeled dataset collected on a set of training MIP instances. This model can then be used to identify high-quality pseudo-backdoors on new MIP instances from the same distribution. We evaluate our method on the generalized independent set problems and find that our approach can efficiently identify high-quality pseudo-backdoors. In addition, we compare our learned approach against Gurobi, a state-of-the-art MIP solver, demonstrating that our method can be used to improve solver performance.
Sum of Costs Optimal Multi-Agent Path Finding with Continuous Time via Satisfiability Modulo Theories
Authors: Surynek Pavel
Published: November 2022

Multi-agent path finding with continuous movements and time (denoted MAPF-R) is addressed. The task is to navigate agents that move smoothly between predefined positions to their individual goals so that they do not collide. Recently a novel solving approach for obtaining makespan optimal solutions called SMT-CCBS based on satisfiability modulo theories (SMT) has been introduced. We extend the approach further towards the sum-of-costs objective which is a more challenging case in the yes/no SMT environment due to more complex calculation of the objective.
Speeding Up Heuristic Function Synthesis via Extending the Formula Grammar
Authors: Poo Hernandez Sergio , Bulitko Vadim
Published: November 2022

Heuristic search algorithms have long been used in video-game AI for unit navigation and planning. The quality of the solution they produce depends substantially on the quality of the heuristic function they use. Recent work automatically synthesized human-readable heuristic functions for a given pathfinding map. This enables tailoring a heuristic to the map but is expensive since each map requires an independent synthesis run. In this paper we propose and evaluate re-using elements of heuristics synthesized for one map in synthesizing heuristics for another map. We do so by adding parts of a synthesized heuristic back to the grammar that defines the space of heuristic functions for the synthesis.
On Merging Agents in Multi-Agent Pathfinding Algorithms
Authors: Boyarski Eli , Chan Shao-Hung , Atzmon Dor , Felner Ariel , Koenig Sven
Published: November 2022

In Multi-Agent Pathfinding (MAPF), the task is to find non-colliding paths for a set of agents. This paper focuses on search-based MAPF algorithms from the Conflict-Based Framework, which is introduced here.
A common technique in such algorithms is to merge a group of dependent agents into a meta-agent and plan non-colliding paths for the meta-agent using a low-level MAPF sub-solver.
We analyze the patterns that emerge when agents are merged in an arbitrary order.
We then introduce policies for choosing which agents or meta-agents to merge to achieve improved efficiency in three algorithms: Independence Detection (ID) and Improved Conflict-Based Search (ICBS), which are optimal, and Priority-Based Search (PBS), which is a fast suboptimal algorithm. Experimental results show a significant improvement in efficiency
Effective Planning in Resource-Competition Problems by Task Decomposition
Authors: Chrpa Lukáš , Rytíř Pavel , Nyporko Andrii , Horčík Rostislav , Edelkamp Stefan
Published: November 2022

Effective planning while competing for limited resources is crucial in many real-world applications such as on-demand transport companies competing for passengers. Planning techniques therefore have to take into account possible actions of an adversarial agent. Such a challenge that can be tackled by leveraging game-theoretical methods such as Double Oracle.

This paper aims at the scalability issues arising from combining planning techniques with Double Oracle. In particular, we propose an abstraction-based heuristic for deciding how resources will be collected (e.g. which car goes for which passenger and in which order) and we propose a method for decomposing planning tasks into smaller ones (e.g. generate plans for each car separately). Our empirical evaluation shows that our proposed approach considerably improves scalability compared to the state-of-the-art techniques.
When to Commit to an Action in Online Planning and Search
Authors: Gu Tianyi , Ruml Wheeler , Shperberg Shahaf S. , Shimony Eyal Solomon , Karpas Erez
Published: November 2022

In online planning, search is concurrent with execution. Under the formulation of planning as heuristic search, when a planner commits to an action, it re-roots its search tree at the node representing the outcome of that action. For the system to remain controlled, the planner must commit to a new action (perhaps a no-op) before the previously chosen action completes. This time pressure results in a real-time search. In this time-bounded setting, it can be beneficial to commit early, in order to perform more lookahead search focused below an upcoming state. In this paper, we propose a principled method for making this commitment decision. Our experimental evaluation shows that our scheme can outperform previously-proposed fixed strategies.
On Producing Shortest Cost-Optimal Plans
Authors: Katz Michael , Röger Gabriele , Helmert Malte
Published: November 2022

Cost-optimal planning is at the heart of planning research, with many existing planners that produce provably optimal solutions. While some applications pose additional restrictions, such as producing shortest (in the number of actions) among the cost-optimal plans, standard cost-optimal planning does not provide such a guarantee. We discuss two possible approaches to produce provably the shortest among the cost-optimal plans, one corresponding to an instantiation of cost-algebraic A∗, the other based on a cost transformation. We formally prove that the new cost-transformation method indeed produces the shortest among the cost-optimal plans and empirically compare the performance of the approaches in different configurations.
Additive Pattern Databases for Decoupled Search
Authors: Sievers Silvan , Gnad Daniel , Torralba Álvaro
Published: November 2022

Abstraction heuristics are the state of the art in optimal classical planning as
heuristic search. Despite their success for explicit-state search, though,
abstraction heuristics are not available for decoupled state-space search, an
orthogonal reduction technique that can lead to exponential savings by decomposing
planning tasks. In this paper, we show how to compute pattern database (PDB)
heuristics for decoupled states. The main challenge lies in how to additively employ
multiple patterns, which is crucial for strong search guidance of the heuristics. We
show that in the general case, for arbitrary collections of PDBs, computing the
heuristic for a decoupled state is exponential in the number of leaf components of
decoupled search. We derive several variants of decoupled PDB heuristics that allow
to additively combine PDBs avoiding this blow-up and evaluate them empirically.
Learning a Priority Ordering for Prioritized Planning in Multi-Agent Path Finding
Authors: Zhang Shuyang , Li Jiaoyang , Huang Taoan , Koenig Sven , Dilkina Bistra
Published: November 2022

Prioritized Planning (PP) is a fast and popular framework for solving Multi-Agent Path Finding, but its solution quality depends heavily on the predetermined priority ordering of the agents. Current PP algorithms use either greedy policies or random assignments to determine a total priority ordering, but none of them dominates the others in terms of the success rate and solution quality (measured by the sum-of-costs). We propose a machine-learning (ML) framework to learn a good priority ordering for PP. We develop two models, namely ML-T, which is trained on a total priority ordering, and ML-P, which is trained on a partial priority ordering. We propose to boost the effectiveness of PP by further applying stochastic ranking and random restarts. The results show that our ML-guided PP algorithms outperform the existing PP algorithms in success rate, runtime, and solution quality on small maps in most cases and are competitive with them on large maps despite the difficulty of collecting training data on these maps.
Optimally Solving the Multiple Watchman Route Problem with Heuristic Search (Extended Abstract)
Authors: Livne Yaakov , Atzmon Dor , Skyler Shawn , Boyarski Eli , Shapiro Amir , Felner Ariel
Published: November 2022

In the Watchman Route Problem (WRP), the task is to find a path for a watchman agent such that all locations in the given map will be visually seen by the watchman at least once during the path traversal. Recently, the problem has been optimally solved on a grid map using heuristic search. In this paper, we extend this work to the case of multiple agents. We call this problem the Multiple Watchman Route Problem (MWRP). In MWRP, the task is to find a path for each watchman such that each location on the map will be seen by at least one watchman. We optimally solve MWRP with heuristic search for two different objective functions with a number of A*-based variants, including an enhanced branching mechanism. We then provide an experimental study on these methods and on other attributes of this problem.
Search Space Reduction Using Swamp Hierarchies
Authors: Pochter Nir , Zohar Aviv , Rosenschein Jeffrey , Felner Ariel
Published: November 2022

In various domains, such as computer games, robotics, and transportation networks, shortest paths may need to be found quickly. Search time can be significantly reduced if it is known which parts of the graph include "swamps" - areas that cannot lie on the only available shortest path, and can thus safely be pruned during search. We introduce an algorithm for detecting hierarchies of swamps, and exploiting them. Experiments support our claims of improved efficiency, showing significant reduction in search time.
Cost Based Search Considered Harmful
Authors: Cushing William , Benton J. , Kambhampati Subbarao
Published: November 2022

Planning research has returned to the issue of optimizing costs (rather than sizes) of plans. A prevalent perception, at least among non-experts in search, is that graph search for optimizing the size of paths generalizes more or less trivially to optimizing the cost of paths. While this kind of generalization is usually straightforward for graph theorems, graph algorithms are a different story. In particular, implementing a search evaluation function by substituting cost for size is a Bad Idea. Though experts have stated as much, cutting-edge practitioners are still learning of the consequences the hard way; here we mount a forceful indictment on the inherent dangers of cost-based search.
State-Set Search
Authors: Pang Bo , Holte Robert
Published: November 2022

State-set search is state space search when the states being manipulated by the search algorithm are sets of states from some underlying state space. State-set search arises commonly in planning and abstraction systems, but this paper provides the first formal, general analysis of state-set search. We show that the state-set distance computed by planning systems is different than that computed by abstraction systems and introduce a distance in between the two, dww, the maximum admissible distance. We introduce the concept of a multi-abstraction, which maps a state to more than one abstract state in the same abstract space, describe the first implementation of a multi-abstraction system that computes dww, and give initial experimental evidence that it can be superior to domain abstraction.
Predicting Solution Cost with Conditional Probabilities
Authors: Lelis Levi , Stern Roni , Jabbari Arfaee Shahab
Published: November 2022

Classical heuristic search algorithms find the solution cost of a problem while finding the path from the start state to a goal state. However, there are applications in which finding the path is not needed. In this paper we propose an algorithm that accurately and efficiently predicts the solution cost of a problem without finding the actual solution. We show empirically that our predictor makes more accurate predictions when compared to the bootstrapped heuristic, which is known to be a very accurate inadmissible heuristic. In addition, we show how our prediction algorithm can be used to enhance heuristic search algorithms. Namely, we use our predictor to calculate a bound for a bounded best-first search algorithm and to tune the w-value of Weighted IDA*. In both cases major search speedups were observed.
Repeated-Task Canadian Traveler Problem
Authors: Bnaya Zahy , Felner Ariel , Fried Dror , Maksin Olga , Shimony Solomon
Published: November 2022

In the Canadian Traveler Problem (CTP) a traveling agent is given a weighted graph, where some of the edges may be blocked, with a known probability. The agent needs to travel to a given goal. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is intractable. Previous work has focused on the case of a single agent. We generalize CTP to a repeated task version where a number of agents need to travel to the same goal, minimizing their combined travel cost. We provide optimal algorithms for the special case of disjoint path graphs. Based on a previous UCT-based approach for the single agent case, a framework is developed for the multi-agent case and four variants are given - two of which are based on the results for disjoint-path graphs. Empirical results show the benefits of the suggested framework and the resulting heuristics. For small graphs where we could compare to optimal policies, our approach achieves near optimal results at only a fraction of the computation cost.
Path Planning with Adaptive Dimensionality
Authors: Gochev Kalin , Cohen Benjamin , Butzke Jonathan , Safonova Alla , Likhachev Maxim
Published: November 2022

Path planning quickly becomes computationally hard as the dimensionality of the state-space increases. In this paper, we present a planning algorithm intended to speed up path planning for high-dimensional state-spaces such as robotic arms. The idea behind this work is that while planning in a high-dimensional state-space is often necessary to ensure the feasibilityof the resulting path, large portions of the path have a lower-dimensional structure. Based on this observation, our algorithm iteratively constructs a state-space of an adaptive dimensionality--a state-space that is high-dimensional only where the higher dimensionality is absolutely necessary for finding a feasible path. This often reduces drastically the size of the state-space, and as a result, the planning time and memory requirements. Analytically, we show that our method is complete and is guaranteed to find a solution if one exists, within a specified suboptimality bound. Experimentally, we apply the approach to 3D vehicle navigation (x, y, heading), and to a 7 DOF robotic arm on the Willow Garage’s PR2 robot. The results from our experiments suggest that ourmethod can be substantially faster than some of the state-of-the-art planning algorithms optimized for those tasks.
Probably Approximately Correct Heuristic Search
Authors: Stern Roni , Felner Ariel , Holte Robert
Published: November 2022

A* is a best-first search algorithm that returns an optimal solution. w-admissible algorithms guarantee that the returned solution is no larger than w times the optimal solution. In this paper we introduce a generalization of the w-admissibility concept that we call PAC search, which is inspired by the PAC learning framework in Machine Learning. The task of a PAC search algorithm is to find a solution that is w-admissible with high probability. In this paper we formally define PAC search, and present a framework for PAC search algorithms that can work on top of any search algorithm that produces a sequence of solutions. Experimental results on the 15-puzzle demonstrate that our framework activated on top of Anytime Weighted A* (AWA*) expands significantly less nodes than regular AWA* while returning solutions that have almost the same quality.
Abstract: Block A* and Any-Angle Path-Planning
Authors: Yap Peter , Burch Neil , Holte Robert , Schaeffer Jonathan
Published: November 2022

We present three new ideas for grid-based path-planning algorithms that improve the search speed and quality of the paths found. First, we introduce a new type of database, the Local Distance Database (LDDB), that contains distances between boundary points of a local neighborhood. Second, an LDDB-based algorithm is introduced, called Block A*, that calculates the optimal path between start and goal locations given the local distances stored in the LDDB. Third, our experimental results for any-angle path planning in a wide varietyof test domains, including real game maps, show that Block A* is faster than both A* and the previously best grid-based any-angle search algorithm, Theta*.
Paper Summary: Time-Bounded Adaptive A*
Authors: Hernandez Carlos , Baier Jorge , Uras Tansel , Koenig Sven
Published: November 2022

This paper summarizes our AAMAS 2012 paper on "Time-Bounded Adaptive A*," which introduces the game time model to evaluate search algorithms in real-time settings, such as video games. It then extends the existing real-time search algorithm TBA* to path planning with the freespace assumption in initially partially or completely unknown terrain, resulting in Time-Bounded Adaptive A* (TBAA*). TBAA* needs fewer time intervals in the game time model than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.
SoCS 2012 Organization
Authors: Likhachev Maxim
Published: November 2022

List of organizers and program committee for the Fifth Annual Symposium on Combinatorial Search held in 2012.
Adaptive Parallelization for Constraint Satisfaction Search
Authors: Yun Xi , Epstein Susan
Published: November 2022

This paper introduces two adaptive paradigms that parallelize search for solutions to constraint satisfaction problems. Both are intended for any sequential solver that uses contention-oriented variable-ordering heuristics and restart strategies. Empirical results demonstrate that both paradigms improve the search performance of an underlying sequential solver, and also solve challenging problems left open after recent solver competitions.
Multimapping Abstractions and Hierarchical Heuristic Search
Authors: Pang Bo , Holte Robert
Published: November 2022

In this paper we introduce a broadly applicable method, called multimapping abstraction, that allows multiple heuristic values for a state to be extracted from one abstract state space. The key idea is to define an abstraction to be a multimapping, i.e., a function that maps a state in the original state space to a set of states in the abstract space. We performed a large-scale experiment on several benchmark state spaces to compare the memory requirements and runtime of Hierarchical IDA* (HIDA*) using multimapping domain abstractions to HIDA* with individual domain abstractions and to HIDA* with multiple, independent domain abstractions. Our results show that multimapping domain abstractions are superior to both alternatives in terms of both memory usage and runtime.
Bidirectional A* Search with Additive Approximation Bounds
Authors: Rice Michael , Tsotras Vassilis
Published: November 2022

In this paper, we present new theoretical and experimental results for bidirectional A* search. Unlike most previous research on this topic, our results do not require assumptions of either consistent or balanced heuristic functions for the search. Our theoretical work examines new results on the worst-case number of node expansions for inconsistent heuristic functions with bounded estimation errors. Additionally, we consider several alternative termination criteria in order to more quickly terminate the bidirectional search, and we provide worst-case approximation bounds for our suggested criteria. We prove that our approximation bounds are purely additive in nature (a general improvement over previous multiplicative approximations). Experimental evidence on large-scale road networks suggests that the errors introduced are truly quite negligible in practice, while the performance gains are significant.
Abstracting Abstraction in Search II: Complexity Analysis
Authors: Backstrom Christer , Jonsson Peter
Published: November 2022

Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible concept of transformations between labelled graphs. We also proposed a number of properties to describe and classify such transformations. This framework enabled the modelling of a number of different abstraction methods in a way that facilitated comparative analyses. It is of particular interest that these properties can be used to capture the concept of refinement without backtracking between levels; how to do this has been an open question for at least twenty years. In this paper, we continue our previous research by analysing the complexity of testing the various transformation properties for both explicit and implicit graph~representations.