bluuebunny/crossref_metadata_2025 huggingface dataset:
Personalized Recommendation of Twitter Lists using Content and Network Information
Authors: Rakesh Vineeth , Singh Dilpreet , Vinzamuri Bhanukiran , Reddy Chandan K
Published: November 2022

Lists in social networks have become popular tools to orga-nize content. This paper proposes a novel framework for rec-ommending lists to users by combining several features thatjointly capture their personal interests. Our contribution is oftwo-fold. First, we develop a ListRec model that leveragesthe dynamically varying tweet content, the network of twitterers and the popularity of lists to collectively model the users’preference towards social lists. Second, we use the topicalinterests of users, and the list network structure to developa novel network-based model called the LIST-PAGERANK.We use this model to recommend auxiliary lists that are morepopular than the lists that are currently subscribed by theusers. We evaluate our ListRec model using the Twitterdataset consisting of 2988 direct list subscriptions. Using au-tomatic evaluation technique, we compare the performanceof the ListRec model with different baseline methods andother competing approaches and show that our model deliversbetter precision in terms of the prediction of the subscribedlists of the twitterers. Furthermore, we also demonstrate the importance of combining different weighting schemes andtheir effect on capturing users’ interest towards Twitter lists.To evaluate the LIST-PAGERANK model, we employ a user-study based evaluation to show that the model is effective inrecommending auxiliary lists that are more authoritative thanthe lists subscribed by the users.
Newsworthiness and Network Gatekeeping on Twitter: The Role of Social Deviance
Authors: Diakopoulos Nicholas , Zubiaga Arkaitz
Published: November 2022

Publishers of news information are keen to amplify the reach of their content by making it as re-sharable as possible on social media. In this work we study the relationship between the concept of social deviance and the re-sharing of news headlines by network gatekeepers on Twitter. Do network gatekeepers have the same predilection for selecting socially deviant news items as professionals? Through a study of 8,000 news items across 8 major news outlets in the U.S. we predominately find that network gatekeepers re-share news items more often when they reference socially deviant events. At the same time we find and discuss exceptions for two outlets, suggesting a more complex picture where newsworthiness for networked gatekeepers may be moderated by other effects such as topicality or varying motivations and relationships with their audience.
Are People Really Social in Porn 2.0?
Authors: Tyson Gareth , Elkhatib Yehia , Sastry Nishanth , Uhlig Steve
Published: November 2022

Social Web 2.0 features have become a vital component in a variety of multimedia systems, e.g., YouTube, Last.fm. Interestingly, adult video websites are also starting to adopt these Web 2.0 principles, giving rise to the term "Porn 2.0". This paper examines a large Porn 2.0 social network, through data covering 563k users. We explore a number of unusual behavioural aspects that set this apart from more traditional multimedia social networks. We particularly focus on the role of gender and sexuality, to understand how these different groups behave. A number of key differences are discovered relating to social demographics, modalities of interaction and content consumption habits, shedding light on this understudied area of online activity.
Self-Characterized Illness Phase and Information Needs of Participants in an Online Cancer Forum
Authors: Eschler Jordan , Dehlawi Zakariya , Pratt Wanda
Published: November 2022

A diagnosis of cancer is the first step on a long journey of treatment, follow-up, and maintenance or survivorship. As 5-year survivorship rates among cancer patients increase, more cancer survivors will participate in online discussion forums and support groups to assist current cancer patients through their illness. Online venues are both optimal for the exchange of patient expertise and a safe space for patients to “meet” others undergoing similar experiences. This paper presents the findings of content analysis in a general cancer forum hosted on reddit.com (r/cancer). We delineate the types of conversations found on the forum and their conceptual “shapes” (e.g., call and response of question and answer, sharing of stories), and describe connections between self-characterized cancer illness phase and stated information needs. We find that online participants posting immediately after diagnosis or during treatment tend to ask for advice; survivors are more likely to share information in the form of personal narratives; and terminal patients seek acknowledgement from the community and validation in their choices. These findings demonstrate that information systems design tailored to illness phase can expedite information finding and increase information relevance for cancer patients and survivors.
DUKE: A Solution for Discovering Neighborhood Patterns in Ego Networks
Authors: Muhammad Syed Agha , Van Laerhoven Kristof
Published: November 2022

Given the rapid growth of social media websites and the ease of aggregating ever-richer social data, an inevitable research question that can be expected to emerge is whether different interaction patterns of individuals and their meaningful interpretation can be captured for social network analysis. In this work, we present a novel solution that discovers occurrences of prototypical 'ego network' patterns from social media and mobile-phone networks, to provide a data-driven instrument to be used in behavioral sciences for graph interpretations. We analyze nine datasets gathered from social media websites and mobile phones, together with 13 network measures, and three unsupervised clustering algorithms. Further, we use an unsupervised feature similarity technique to reduce redundancy and extract compact features from the data. The reduced feature subsets are then used to discover ego patterns using various clustering techniques. By cluster analysis, we discover that eight distinct ego neighborhood patterns or ego graphs have emerged. This categorization allows concise analysis of users' data as they change over time. We provide fine-grained analysis for the validity and quality of clustering results. We perform clustering verification based on the following three intuitions: i) analyzing the clustering patterns for the same set of users crawled from three social media networks, ii) associating metadata information with the clusters and evaluating their performance on real networks, iii) studying selected participants over an extended period to analyze their behavior.
Geolocation Prediction in Twitter Using Social Networks: A Critical Analysis and Review of Current Practice
Authors: Jurgens David , Finethy Tyler , McCorriston James , Xu Yi , Ruths Derek
Published: November 2022

Geolocated social media data provides a powerful source of information about place and regional human behavior.  Because little social media data is geolocation-annotated, inference techniques serve an essential role for increasing the volume of annotated data. One major class of inference approaches has relied on the social network of Twitter, where the locations of a user's friends serve as evidence for that user's location. While many such inference techniques have been recently proposed, we actually know little about their relative performance, with the amount of ground truth data varying between 5% and 100% of the network, the size of the social network varying by four orders of magnitude, and little standardization in evaluation metrics. We conduct a systematic comparative analysis of nine state-of-the-art network-based methods for performing geolocation inference at the global scale, controlling for the source of ground truth data, dataset size, and temporal recency in test data. Furthermore, we identify a comprehensive set of evaluation metrics that clarify performance differences. Our analysis identifies a large performance disparity between that reported in the literature and that seen in real-world conditions. To aid reproducibility and future comparison, all implementations have been released in an open source geoinference package.
It's a Man's Wikipedia? Assessing Gender Inequality in an Online Encyclopedia
Authors: Wagner Claudia , Garcia David , Jadidi Mohsen , Strohmaier Markus
Published: November 2022

Wikipedia is a community-created encyclopedia that contains information about notable people from different countries, epochs and disciplines and aims to document the world's knowledge from a neutral point of view. However, the narrow diversity of the Wikipedia editor community has the potential to introduce systemic biases such as gender biases into the content of Wikipedia. In this paper we aim to tackle a sub problem of this larger challenge by presenting and applying a computational method for assessing gender bias on Wikipedia along multiple dimensions. We find that while women on Wikipedia are covered and featured well in many Wikipedia language editions, the way women are portrayed starkly differs from the way men are portrayed. We hope our work contributes to increasing awareness about gender biases online, and in particular to raising attention to the different levels in which gender biases can manifest themselves on the web.
Characterizing Information Diets of Social Media Users
Authors: Kulshrestha Juhi , Zafar Muhammad , Noboa Lisette , Gummadi Krishna , Ghosh Saptarshi
Published: November 2022

With the widespread adoption of social media sites like Twitter and Facebook, there has been a shift in the way information is produced and consumed. Earlier, the only producers of information were traditional news organizations, which broadcast the same carefully-edited information to all consumers over mass media channels. Whereas, now, in online social media, any user can be a producer of information, and every user selects which other users she connects to, thereby choosing the information she consumes. Moreover, the personalized recommendations that most social media sites provide also contribute towards the information consumed by individual users. In this work, we define a concept of information diet — which is the topical distribution of a given set of information items (e.g., tweets) — to characterize the information produced and consumed by various types of users in the popular Twitter social media. At a high level, we find that (i) popular users mostly produce very specialized diets focusing on only a few topics; in fact, news organizations (e.g., NYTimes) produce much more focused diets on social media as compared to their mass media diets, (ii) most users' consumption diets are primarily focused towards one or two topics of their interest, and (iii) the personalized recommendations provided by Twitter help to mitigate some of the topical imbalances in the users' consumption diets, by adding information on diverse topics apart from the users' primary topics of interest.
A Stratified Learning Approach for Predicting the Popularity of Twitter Idioms
Authors: Maity Suman , Gupta Abhishek , Goyal Pawan , Mukherjee Animesh
Published: November 2022

Twitter Idioms are one of the important types of hashtags that spread in Twitter. In this paper, we propose a classifier that can stratify the Idioms from the other kind of hashtags with 86.93% accuracy and high precision and recall rate. We then learn regression models on the stratified samples (Idioms and non-Idioms) separately to predict the popularity of the Idioms. This stratification not only itself allows us to make more accurate predictions but also makes it possible to include Idiom-specific features to separately improve the accuracy for the Idioms. Experimental results show that such stratification during the training phase followed by inclusion of Idiom-specific features leads to an overall improvement of 11.13% and 19.56% in correlation coefficient over the baseline method after the 7th and the 11th month respectively.
Determining the Presence of Political Parties in Social Circles
Authors: Van Gysel Christophe , Goethals Bart , De Rijke Maarten
Published: November 2022

We derive the political climate of the social circles of Twitter users using a weakly-supervised approach. By applying random walks over a sub-sample of Twitter's social graph we infer a distribution indicating the presence of eight Flemish political parties in users' social circles in the months before the 2014 elections. The graph structure is induced through a combination of connection and retweet features and combines information of over a million tweets and 14 million follower connections. We solely exploit the social graph structure and do not rely on tweet content. For validation we compare the affiliation of politically active Twitter users with the most-influential party in their network. On a validation set of around 700 politically active individuals we achieve F_1 scores of 0.85 and greater. We asked the Twitter community to evaluate our classification performance. More than half of the 2258 users who responded reported a score higher than 60 out of 100.
What Do Retweets Indicate? Results from User Survey and Meta-Review of Research
Authors: Metaxas Panagiotis , Mustafaraj Eni , Wong Kily , Zeng Laura , O'Keefe Megan , Finn Samantha
Published: November 2022

Arguably one of the most important features of Twitter is the support for “retweets” or messages re-posted verbatim by a user that were originated by someone else. Despite the fact that retweets are routinely studied and reported, many important questions remain about user motivation for their use and their significance. In this paper we answer the question of what users indicate when they retweet. We do so in a comprehensive fashion, by employing a user survey, a study of user profiles, and a meta-review of over 100 research publications from three related major conferences. Our findings indicate that retweeting indicates not only interest in a message, but also trust in the message and the originator, and agreement with the message contents. However, the findings are significantly weaker for journalists, some of whom beg to differ declaring so in their own user profiles. On the other hand, the inclusion of hashtags strengthens the signal of agreement, especially when the hashtags are related to politics. While in the past there have been additional claims in the literature about possible reasons for retweeting, many of them are not supported, especially given the technical changes introduced recently by Twitter.
Goodreads Versus Amazon: The Effect of Decoupling Book Reviewing And Book Selling
Authors: Dimitrov Stefan , Zamal Faiyaz , Piper Andrew , Ruths Derek
Published: November 2022

Book reviewing is a commonplace activity on many ecommerce sites. However, it is nested within the broader context of book buying and selling. Goodreads, an online platform for social curation of book collections, provides an opportunity to observe on-line book reviewing in an environment that is not (at least overtly) focused on commercialization. In this study, we perform a careful comparative study of reviewer behavior and engagement in Goodreads and Amazon.com, constrained to a single genre (biography), including 21,394 books and 2.5 million reviews. We discover marked differences between the platforms that suggest disparate population composition and objectives of review-writing across the two platforms. Our findings suggest an important and generalizable principle: that two platforms engaging users on the same task (e.g., book review writing) may elicit quite different behavior depending on the implicit or explicit context and motivation present.
T-Gram: A Time-Aware Language Model to Predict Human Mobility
Authors: Hsieh Hsun-Ping , Li Cheng-Te , Gao Xiaoqing
Published: November 2022

This paper presents a novel time-aware language model, T-gram, to predict the human mobility using location check-in data. While the conventional n-gram language model, which use the contextual co-occurrence to estimate the probability of a sequence of items, are often employed to predict human mobility, the time information of items is merely considered. T-gram exploits the time information associated at each location, and aims to estimate the probability of visiting satisfaction for a given sequence of locations. For a location sequence, if locations are visited at right times and the transitions between locations are proper as well, the T-gram probability gets higher. We also devise a T-gram Search algorithm to predict future locations. Experiments of human mobility prediction conducted on Gowalla check-in data significantly outperform a series of n-gram-based methods and encourage the future usage of T-gram.
Psychological Effects of Urban Crime Gleaned from Social Media
Authors: Delgado Valdes Jose , Eisenstein Jacob , De Choudhury Munmun
Published: November 2022

Exposure to frequent crime incidents has been found to have a negative bearing on the well-being of city residents, even if they are not themselves a direct victim. We pursue the research question of whether naturalistic data shared on Twitter may provide a “lens” to understand changes in psychological attributes of urban communities (1) immediately following crime incidents, as well as (2) due to long-term exposure to crime. We analyze half a million Twitter posts from the City of Atlanta in 2014, where the rate of violent crime is three times of the national average. In a first study, we develop a statistical method to detect changes in social media psychological attributes in the immediate aftermath of a crime event. Second, we develop a regression model that uses historical (yearlong) crime to predict Twitter negative emotion, anxiety, anger, and sadness. We do not find significant changes in social media affect immediately following crime in Atlanta. However we do observe significant ability of historical crime to account for heightened negative emotion and anger in the future. Our findings have implications in gauging the utility of social media to infer longitudinal and population-scale patterns of urban well-being.
Reliability of Data Collection Methods in Social Media Research
Authors: Cheliotis Giorgos , Lu Xuesong , Yi Song
Published: November 2022

In this paper we argue for the systematic assessment and reporting of the reliability of data collection methods that rely on the automated collection of data from third party social media sites, where the researcher does not have direct access to meaning or control over data quality. Building on a long tradition of reliability assessment in the sciences and specifically in social science, we propose methods for the assessment of reliability, also for textual data that is increasingly mined from social media for the purposes of studying online populations.
Organizations Are Users Too: Characterizing and Detecting the Presence of Organizations on Twitter
Authors: McCorriston James , Jurgens David , Ruths Derek
Published: November 2022

Much work on the demographics of social media platforms such as Twitter has focused on the properties of individuals, such as gender or age. However, because credible detectors for organization accounts do not exist, these and future large-scale studies of human behavior on social media can be contaminated by the presence of accounts belonging to organizations. We analyze organizations on Twitter to assess their distinct behavioral characteristics and determine what types of organizations are active. We first create a dataset of manually classified accounts from a representative sample of Twitter and then introduce a classifier to distinguish between organizational and personal accounts. In addition, we find that although organizations make up less than 10% of the accounts, they are significantly more connected, with an order of magnitude more friends and followers.
An Analysis of Exercising Behavior in Online Populations
Authors: Jurgens David , McCorriston James , Ruths Derek
Published: November 2022

Exercise plays a central role in many peoples' fitness goals.  While prior work has examined how individuals pursue these health and fitness goals on general purpose platforms such as Twitter, the lack of precise activity recording has limited detailed analyses of individual and group behaviors.  In this study, we explore a recent social media platform dedicated to exercise and use nearly four years of longitudinal exercising history of over 188,000 users to discover large-scale exercising patterns corresponding to different motivations such as sports or general fitness.
Tweeting Behaviour during Train Disruptions within a City
Authors: Limsopatham Nut , Albakour M-Dyaa , Macdonald Craig , Ounis Iadh
Published: November 2022

In a smart city environment, citizens use social media for communicating and reporting events. Existing work has shown that social media tools, such as Twitter and Facebook, can be used as social sensors to monitor events in real-time as they happen (e.g.\ riots, natural disasters and sport events). In this paper, we study the reactions of citizens in social media towards train disruptions within a city. Our study using 30 days of tweets in a large city shows that citizens react differently to train disruptions by, for instance, displaying unique behaviours in tweeting depending on the time of the disruption. Specifically, for working days, tweets related to train disruptions are typically generated during rush hour periods. In contrast, during weekends, urban citizens tended to tweet about train disruptions during late evenings. Using these insights, we develop a supervised approach to predict whether a train disruption tweet will be retweeted and propagated on the social network, by using features, such as time, user, and the content of tweets. Our experimental results show that we can effectively predict when a train disruption tweet is retweeted by using such features.
Making Social Media Research Reproducible
Authors: Hutton Luke , Henderson Tristan
Published: November 2022

The huge numbers of people using social media makes online socialnetworks an attractive source of data for researchers. But in order for the resultant huge numbers of research publications that involve social media to be credible and trusted, their methodologies,considerations of data handling and sensitivity, analysis, and so forth must be appropriately documented. We believe that one way to improve standards and practices in social media research is to encourage such research to be made reproducible, that is, to have sufficient documentation and sharing of research to allow others to either replicate or build on research results. Enabling this fundamental part of the scientific method will benefit the entire social media ecosystem, from the researchers who use data, to the people that benefit from the outcomes of research.
User Engagement on Wikipedia, A Review of Studies of Readers and Editors
Authors: Miquel-Ribé Marc
Published: November 2022

Is it an encyclopedia or a social network? Without considering both aspects it would not be possible to understand how a worldwide army of editors created the largest online knowledge repository. Wikipedia has a consistent set of rules and it responds to many of the User Engagement Framework attributes, and this is why it works. In this paper, we identify these confirmed attributes as well as those presenting problems. We explain that although having a strong editor base Wikipedia is finding it challenging to maintain this base or increase its size. In order to understand this, scholars have analyzed Wikipedia using current metrics like user session and activity. We conclude there exist opportunities to analyze engagement in new aspects in order to understand its success, as well as to redesign mechanisms to improve the system and help the transition between reader and editor.
On the Evolution of Wikipedia: Dynamics of Categories and Articles
Authors: Bairi Ramakrishna , Carman Mark , Ramakrishnan Ganesh
Published: November 2022

We present several statistics related to English Wikipedia category and article evolution between Wikipedia 2012 (Oct) and 2014 (Jun) instances. This includes analysis of categories, articles and links creation and deletion. We also present the distribution of Wikipedia articles over 14 broad topics and compare them across 2012 and 2014 Wikipedia. We provide several statistics of Wikipedia category graph. We demonstrate that Wikipedia category hierarchy can be treated as an is-a graph locally, but over longer paths it is no more an is-a graph.
MultilingualWikipedia: Editors of Primary Language Contribute to More Complex Articles
Authors: Park Sungjoon , Kim Suin , Hale Scott , Kim Sooyoung , Byun Jeongmin , Oh Alice
Published: November 2022

For many people who speak more than one language,their language proficiency for each of the languagesvaries. We can conjecture that people who use onelanguage (primary language) more than another wouldshow higher language proficiency in that primary language.It is, however, difficult to observe and quantifythat problem because natural language use is difficultto collect in large amounts. We identify Wikipedia asa great resource for studying multilingualism, and weconduct a quantitative analysis of the language complexityof primary and non-primary users of English,German, and Spanish. Our preliminary results indicatethat there are indeed consistent differences of languagecomplexity in the Wikipedia articles chosen by primaryand non-primary users, as well as differences in the editsby the two groups of users.
Too Good to Throw Away: A Powerful Reuse Strategy for Reiter's Hitting Set Tree
Authors: Rodler Patrick
Published: November 2022

Reiter's HS-Tree is one of the most popular diagnostic search algorithms due to its desirable properties and general applicability. In sequential diagnosis, where the addressed diagnosis problem is subject to successive change through the acquisition of additional knowledge about the diagnosed system, HS-Tree is used in a stateless fashion. That is, the existing search tree is discarded when new knowledge is obtained, albeit often large parts of the tree are still relevant and have to be rebuilt in the next iteration, involving redundant operations and costly reasoner calls. As a remedy, we propose DynamicHS, a variant of HS-Tree that avoids these redundancy issues by maintaining state throughout sequential diagnosis while preserving all desirable properties of HS-Tree. Evaluations in a problem domain where HS-Tree is the state-of-the-art diagnostic method reveal stable and significant time savings achieved by DynamicHS.
Planning Against Adversary in Zero-Sum Games: Heuristics for Selecting and Ordering Critical Actions
Authors: Chrpa Lukas , Rytir Pavel , Horcik Rostislav
Published: November 2022

Effective and efficient reasoning in adversarial environments is important for many real-world applications ranging from cybersecurity to military operations. Deliberative reasoning techniques, such as Automated Planning, often restrict to static environments where only an agent can make changes by its actions. On the other hand, such techniques are effective and can generate non-trivial solutions. To explicitly reason in environments with an active adversary such as zero-sum games, the game-theoretic framework such as the Double Oracle algorithm can be leveraged. In this paper, we leverage the notions of critical and adversary actions, where critical actions should be applied before the adversary ones. We propose heuristics that provide a guidance for planners about what (critical) actions and in which order have to be applied in a good plan. We empirically evaluate our approach in terms of quality of generated strategies (by leveraging Double Oracle) and CPU time required to generated such strategies.
On the Differences and Similarities of fMM and GBFHS
Authors: Shperberg Shahaf , Felner Ariel
Published: November 2022

fMM and GBFSH are two prominent bidirectional heuristic search algorithms. Over the past few years, there has been a great deal of theoretical and empirical work on both of these algorithms. As part of the research conducted on these algorithms, some interesting theoretical properties were proven for fMM and not for GBFSH and vice versa. In addition, both of them are used as benchmarks for evaluation bidirectional heuristic search algorithms. In this paper we show that fMM infused by a lower-bound propagation and GBFSH are equivalent. In essence, every instance of fMM can be mapped to an instance of GBFSH that expands the exact sequence of nodes and vice versa. This equivalence indicates that all theoretical properties proven for one algorithm hold for both algorithm, and that future analyses and benchmarks can consider only one of these algorithms.
Fast Bounded Suboptimal Probabilistic Planning with Clear Preferences on Missing Information
Authors: Chatterjee Ishani , Kusnur Tushar , Likhachev Maxim
Published: November 2022

In the real-world, robots must often plan despite the environment being partially known. This frequently necessitates planning under uncertainty over missing information about the environment. Unfortunately, the computational expense of such planning often precludes its scalability to real-world problems. The Probabilistic Planning with Clear Preferences (PPCP) framework focuses on a specific subset of such planning problems wherein there exist clear preferences over the actual values of missing information (Likhachev and Stenz 2009). PPCP exploits the existence and knowledge of these preferences to perform provably optimal planning via a series of deterministic A*-like searches over particular instantiations of the environment. Such decomposition leads to much better scalability with respect to both the size of a problem and the amount of missing information in it. The run-time of PPCP however is a function of the number of searches it has to run until convergence. In this paper, we make a key observation that the number of searches PPCP has to run can be dramatically decreased if each search computes a plan that minimizes the amount of missing information it relies upon. To that end, we introduce Fast-PPCP, a novel planning algorithm that computes a provably bounded suboptimal policy using significantly lesser number of searches than that required to find an optimal policy. We present Fast-PPCP with its theoretical analysis, compare with common alternative approaches to planning under uncertainty over missing information, and experimentally show that Fast-PPCP provides substantial gain in runtime over other approaches while incurring little loss in solution quality.
Experimental Evaluation of Classical Multi Agent Path Finding Algorithms
Authors: Kaduri Omri , Boyarski Eli , Stern Roni
Published: November 2022

Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.
Contingent Planning for Robust Multi-Agent Path Finding
Authors: Nekvinda Michal , Barták Roman , Kalech Meir
Published: November 2022

A classical approach to Multi-agent Path Finding assumes an offline construction of collision-free paths that the agents blindly follow during execution. k-robust plans can be executed without collisions even if an agent is delayed for at most k steps. In the paper, we propose a novel concept of robustness that uses alternative paths to which the agents are diverted in case of delay. Such plans can be found with much higher chances than k-robust plans.
Further Improved Heuristics For Conflict-Based Search
Authors: Boyarski Eli , Felner Ariel , Le Bodic Pierre , Harabor Daniel D. , Stuckey Peter J. , Koenig Sven
Published: November 2022

Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF).
At its high level, CBS expands nodes by resolving conflicts.
In recent years, admissible heuristics were added to the high level of CBS.
We enhance all known heuristic functions for CBS by using information about the cost of resolving certain conflicts, with only a small computational overhead. We experimentally demonstrate that the improved heuristics contribute to making CBS even more efficient.
Distributional Metareasoning for Heuristic Search
Authors: Gu Tianyi
Published: November 2022

Heuristic search methods are widely used in many real-world autonomous systems. Yet, people always want to solve search problems that are larger than time allows. To address these challenging problems, even suboptimally, a planning agent should be smart enough to intelligently allocate its computational resources, to think carefully about where in the state space it should spend time searching. For finding optimal solutions, we must examine every node that is not provably too expensive. In contrast, to find suboptimal solutions when under time pressure, we need to be very selective about which nodes to examine. In this work, we will demonstrate that estimates of uncertainty, represented as belief distributions, can be used to drive search effectively. This type of algorithmic approach is known as metareasoning, which refers to reasoning about which reasoning to do. We will provide examples of improved algorithms for real-time search, bounded-cost search, and situated planning.
Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation
Authors: Vainshtain David , Salzman Oren
Published: November 2022

Planning collision-free paths for multiple agents operating in close proximity has a myriad of applications ranging from smart warehouses to route planning for airport taxiways. This problem, known as the Multi-Agent Path-Finding (MAPF) problem, is highly relevant to real-world applications in automation and robotics, and has attracted significant research in recent years. While in many applications, the robots are tasked with transporting objects and thus have the means to move obstacles, common formulations of the problem prohibit agents from moving obstacles en-route to a task. This often causes agents to take long detours to avoid obstacles instead of simply moving them to clear a path. In this work we present multi-agent terraforming, a novel extension of the MAPF problem that can exploit the fact that the system contains movable obstacles. We build upon leading MAPF solvers and propose an efficient method to solve the multi-agent terraforming problem in a manner that is both complete and optimal. We evaluate our method on scenarios inspired by smart warehouses (such as those of Amazon) and demonstrate that, compared to the classical MAPF formulation, the extra flexibility provided by terraforming facilitates a notable improvement of solution quality.
Trajectory Constraint Heuristics for Optimal Probabilistic Planning
Authors: Peterson John R. , Kulkarni Anagha , Keyder Emil , Kim Joseph , Zilberstein Shlomo
Published: November 2022

Search algorithms such as LAO* and LRTDP coupled with admissible heuristics are widely used methods for optimal probabilistic planning. Their effectiveness depends on the degree to which heuristics are able to approximate the optimal cost of a state. Most common domain-independent heuristics, however, rely on determinization, and ignore the probabilities associated with different effects of actions. Here, we present a method for decomposing a probabilistic planning problem into subproblems by constraining possible action outcomes. Admissible heuristics evaluated for each subproblem can then be combined via a weighted sum to obtain an admissible heuristic for the original problem that takes into account a limited amount of probabilistic information. We use this approach to derive new admissible heuristics for probabilistic planning, and show that for some problems they are significantly more informative than existing heuristics, leading to up to an order of magnitude speedups in the time to converge to an optimal policy.
Online Multi-Agent Path Finding: New Results
Authors: Morag Jonathan , Felner Ariel , Stern Roni , Atzmon Dor , Boyarski Eli
Published: November 2022

Online MAPF extends the classical Multi-Agent Path Finding problem (MAPF) by considering a more realistic problem in which new agents may appear over time. As online solvers are not aware of which agents will join in the future, the notion of snapshot-optimal was defined, where only current knowledge is considered. In this paper, we perform an extensive comparison between oracle-optimal solutions (where the solver is preinformed of future agents), snapshot-optimal solutions, and suboptimal solutions obtained by prioritised planning.
Lazy Compilation in Classical Planning (Extended Abstract)
Authors: Fílová Zuzana , Surynek Pavel
Published: November 2022

Classical planning is a task of finding a sequence of actions that achieve a given goal. One of many approaches to classical planning is compilation into propositional satisfiability (SAT). In this work, we propose a new method that uses lazy compilation into SAT. Different from the standard compilation method, lazy compilation constructs the target propositional formula step by step while the SAT solver is consulted at each step and refinements of the formula are suggested according to SAT solver's answers. The performed experiments pointed out that lazy compilation has the potential to improve the performance of the planners.
Dual Euclidean Shortest Path Search (Extended Abstract)
Authors: Hechenberger Ryan , Stuckey Peter J. , Le Bodic Pierre , Harabor Daniel D.
Published: November 2022

The Euclidean Shortest Path Problem (ESPP) asks us to find a minimum length path between two points on a 2D plane while avoiding a set of polygonal obstacles. Existing approaches for ESPP, based on Dijkstra or A* search, are primal methods that gradually build up longer and longer valid paths until they reach the target. In this paper we define an alternative algorithm for ESPP which can avoid this problem. Our approach starts from a path that ignores all obstacles, and generates longer and longer paths, each avoiding more obstacles, until eventually the search finds an optimal valid path.
Beyond Markov Decision Process with Scalar Markovian Rewards
Authors: Miura Shuwa
Published: November 2022

Real-world decision problems often involve multiple competing objectives or a complex reward structure that violate Markov assumption. However, the existing research on sequential decision making under uncertainty primarily focused on Markov Decision Processes (MDPs) with scalar Markovian reward signals. My thesis considers settings where scalar Markovian rewards are not sufficient to produce desired behaviors. The first part of my thesis develops algorithms to optimize lexicographically ordered objectives. The second part considers autonomous agents which incorporate the perspective of their observer. As the perspective of the observer can depend on how the agents behaved so far, rewards in this setting can depend on histories (non-Markovian). In the final part of my thesis, I hope to characterize when rewards beyond scalar Markovian signals are needed from the decision theoretic perspective
Evolving Hyper Heuristic-Based Solvers for Rush Hour and FreeCell
Authors: Hauptman Ami , Elyasaf Achiya , Sipper Moshe
Published: November 2022

We use genetic programming to evolve highly successful solvers for two puzzles: Rush Hour and FreeCell.
On the Scaling Behavior of HDA*
Authors: Kishimoto Akihiro , Fukunaga Alex , Botea Adi
Published: November 2022

HDA* is a simple, parallelization of A* where work is asynchronously distributed among the nodes by a global hash function. Using up to 1024 cores on a large distributed memory cluster, we evaluate HDA* for a domain-independent planner as well an application-specific 24-puzzle solver. We show that HDA* scales fairly well on a large cluster using up to 1024 cores. Our analysis of the scaling behavior shows that on a cluster of multicore nodes, using only a subset of the available cores and leaving some cores idle can, surprisingly, lead to better results.
GPU Exploration of Two-Player Games with Perfect Hash Functions
Authors: Edelkamp Stefan , Sulewski Damian , Yücel Cengizhan
Published: November 2022

In this paper we improve solving two-player games by computing the game-theoretical value of every reachable state. A graphics processing unit located on the graphics card is used as a co-processor to accelerate the solution process. We exploit perfect hash functions to store the game states efficiently in memory and to transfer their ordinal representation between the host and the graphics card. As an application we validate Gasser's results that Nine-Men-Morris is a draw on a personal computer. Moreover, our solution is strong, while for the opening phase Gasser only provided a weak solution.
Edge Partitioning in Parallel Structured Duplicate Detection
Authors: Zhou Rong , Schmidt Tim , Hansen Eric , Do Minh , Uckun Serdar
Published: November 2022

We show how edge partitioning, a technique originally developed for external-memory search, can be used to reduce the number of slow synchronization operations needed in parallel graph search. We show that edge partitioning improves on a previous technique called parallel structured duplicate detection by allowing a higher degree of concurrency, even for search problems with little or no inherent locality. For domain-independent graph search, we also show that edge partitioning significantly improves search speed by improving the efficiency of precondition checking. We demonstrate the effectiveness of this approach to parallel graph search for domain-independent STRIPS planning.
Improved Prediction of IDA*'s Performance via Epsilon-Truncation
Authors: Lelis Levi , Zilles Sandra , Holte Robert
Published: November 2022

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given cost bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the ``discretization effect''. Second, we disprove the intuitively appealing idea that a ``more informed'' prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in several of our experiments the more informed system makes poorer predictions. Our third contribution is a method, called ``$\epsilon$-truncation'', which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments $\epsilon$-truncation rarely degraded predictions; in the vast majority of cases it improved predictions, often substantially.
A Novel Technique for Avoiding Plateaus of Greedy Best-First Search in Satisficing Planning
Authors: Imai Tatsuya , Kishimoto Akihiro
Published: November 2022

Heuristic functions play an important role in drastically improving performance of satisficing planners based on greedy best-first search (GBFS). While automatic generation of heuristic functions (e.g., (Hoffmann and Nebel 2001; Helmert 2006)) enables state-of-the-art satisficing planners to solve very complicated planning problems including benchmarks in the International Planning Competitions, accurate evaluations of nodes still remain as a challenging task. Although GBFS is fundamental and powerful in planning, it has an essential drawback when heuristic functions return inaccurate estimates. Assume that a heuristic function underestimates the difficulties of unpromising nodes. Then, since GBFS must expand nodes with small heuristic values first, it spends most of time in searching only unpromising areas and delays moving to the promising part.Previous work tackles this issue by adding a diversity to search, which is an ability in simultaneously exploring different parts of the search space to bypass large errors in heuristic functions. Several algorithms combined with diversity (e.g., K-best-first search (KBFS) in (Felner, Kraus, and Korf 2003)) are empirically shown to be superior to naive best-first search algorithms. However, they still have limited diversity, since they do not immediately expand nodes mistakenly evaluated as very unpromising ones.This paper presents a new technique called diverse best-first search (DBFS), which incorporates a diversity into search in a different way than previous search-based approaches. We show empirical results clearly showing that DBFS is effective in satisficing planning.
Conflict-Based Search for Optimal Multi-Agent Path Finding
Authors: Sharon Guni , Stern Roni , Felner Ariel , Sturtevant Nathan
Published: November 2022

We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.
Predicting Optimal Solution Cost with Bidirectional Stratified Sampling (Abstract)
Authors: Lelis Levi , Stern Roni , Felner Ariel , Zilles Sandra , Holte Robert
Published: November 2022

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i.e., without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity.
Search-Aware Conditions for Probably Approximately Correct Heuristic Search
Authors: Stern Roni , Felner Ariel , Holte Robert
Published: November 2022

The notion of finding a solution that is approximately optimal with high probability was recently introduced to the field of heuristic search,formalized as Probably Approximately Correct Heuristic Search, or PAC search in short. A big challenge when constructing a PAC search algorithm is to identify when a given solution achieves the desired sub-optimality with the required confidence, allowing the search to halt and return the incumbent solution. In this paper we propose two novel methods for identifying when a PAC search can halt. Unlike previous work, the new methods provided in this paper become more knowledgeable as the search progresses. This can speedup the search, since the search can halt earlier with the proposed methods and still keeping the desired PAC solution quality guarantees.Experimental results indeed show a substantial speedup of the search in comparison to the previous approach for PAC search.
Efficient Implementation of Pattern Database Heuristics for Classical Planning
Authors: Sievers Silvan , Ortlieb Manuela , Helmert Malte
Published: November 2022

Despite their general success in the heuristic search community, pattern database (PDB) heuristics have, until very recently, not been used by the most successful classical planning systems. We describe a new efficient implementation of pattern database heuristics within the Fast Downward planner. A planning system using this implementation is competitive with the state of the art in optimal planning, significantly improving over results from the previous best PDB heuristic implementation in planning.