bluuebunny/crossref_metadata_2025 huggingface dataset:
More than Liking and Bookmarking? Towards Understanding Twitter Favouriting Behaviour
Authors: Meier Florian , Elsweiler David , Wilson Max
Published: November 2022

Microblogging services, such as Twitter, offer a variety of interactive features that allow users to engage with contacts in their social network and the content they produce. One such feature is the favourite button on Twitter, an icon in the form of a star that users can click on to assign a special status to a particular tweet. Despite evidence suggesting that users increasingly make use of favouriting, little is known about the reasons people have for favouriting or the utility the feature offers. This contrasts with other core features, such as “following” and “retweeting”, which have been studied extensively. In this paper we argue that by investigating the motivations for favouriting tweets we can enhance our understanding of what people want to achieve with Twitter and the types of content users find interesting or useful. With these goals in mind we conducted a large-scale survey (n=606), questioning Twitter users on various aspects of their favouriting behaviour. Of these users only 395 were aware of the function and 290 make use of the functionality. The survey responses from these users demonstrate that motives for favouriting tweets are extremely heterogeneous and not always consistent within and between users. Moreover, our findings reveal that user needs when favouriting such as the need for re-finding a tweet or the wish for a more private conversation are often poorly supported and sometimes even go unmet by the Twitter user interface.
Emoticons and Phrases: Status Symbols in Social Media
Authors: Tchokni Simo , Ó Séaghdha Diarmuid , Quercia Daniele
Published: November 2022

There is a sociolinguistic interest in studying the socialpower dynamics that arise on online social networksand how these are reflected in their users’ use of lan-guage. Online social power prediction can also be usedto build tools for marketing and political campaigns thathelp them build an audience. Existing work has focusedon finding correlations between status and linguistic fea-tures in email, Wikipedia discussions, and court hearings.While a few studies have tried predicting status on thebasis of language on Twitter, they have proved less fruit-ful. We derive a rich set of features from literature ina variety of disciplines and build classifiers that assignTwitter users to different levels of status based on theirlanguage use. Using various metrics such as number offollowers and Klout score, we achieve a classification ac-curacy of individual users as high as 82.4%. In a secondstep, we reached up to 71.6% accuracy on the task of pre-dicting the more powerful user in a dyadic conversation.We find that the manner in which powerful users writediffers from low status users in a number of differentways: not only in the extent to which they deviate fromtheir usual writing habits when conversing with othersbut also in pronoun use, language complexity, sentimentexpression, and emoticon use. By extending our analysisto Facebook, we also assess the generalisability of ourresults and discuss differences and similarities betweenthese two sites.
Critical Mass of What? Exploring Community Growth in WikiProjects
Authors: Solomon Jacob , Wash Rick
Published: November 2022

Fledgling online communities often hope to achieve critical mass so that the community becomes sustainable. This concept however is not well understood. At what point does a community achieve critical mass, and how does the community know this? Furthermore, online communities become sustainable when they achieve a mass of what? We explore this question by analyzing growth in a large number of online communities on Wikipedia. We find that individual communities often have different patterns of growth of membership from its pattern of growth of contribution or production. We also find that in the early stages of community development, building membership has a greater impact on community production and activity in later periods than accumulating many contributions early on, and this is especially true when there is more diversity in the early participants in a community. We also show that participation from a community's "power users" in its early stage is not as valuable to sustainability as the collective contributions of those who make only small contributions. We argue that critical mass is established by developing a diverse set of community members with heterogeneous interests and resources, and not purely by accumulating content.
Discussion Graphs: Putting Social Media Analysis in Context
Authors: Kıcıman Emre , Counts Scott , Gamon Michael , De Choudhury Munmun , Thiesson Bo
Published: November 2022

Much research has focused on studying complex phenomena through their reflection in social media, from drawing neighborhood boundaries to inferring relationships between medicines and diseases. While it is generally recognized in the social sciences that such studies should be conditioned on gender, time and other confounding factors, few of the studies that attempt to extract information from social media actually condition on such factors due to the difficulty in extracting these factors from naturalistic data and the added complexity of of including them in analyses. In this paper, we present a simple framework for specifying and implementing common social media analyses that makes it trivial to inspect and condition on contextual information. Our data model---discussion graphs---captures both the structural features of relationships inferred from social media as well as the context of the discussions from which they are derived, such as who is participating in the discussions, when and where the discussions are occurring, and what else is being discussed in conjunction. We implement our framework in a tool called DGT, and present case studies on its use. In particular, we show how analyses of neighborhoods and their boundaries based on geo-located social media data can have drastically varying results when conditioned on gender and time.
Quantifying Information Overload in Social Media and Its Impact on Social Contagions
Authors: Gomez Rodriguez Manuel , Gummadi Krishna , Schoelkopf Bernhard
Published: November 2022

Information overload has become an ubiquitous problem in modern society. Social media users and microbloggers receive an endless flow of information, often at a rate far higher than their cognitive abilities to process the information. In this paper, we conduct a large scale quantitative study of information overload and evaluate its impact on information dissemination in the Twitter social media site. We model social media users as information processing systems that queue incoming information according to some policies, process information from the queue at some unknown rates and decide to forward some of the incoming information to other users. We show how timestamped data about tweets received and forwarded by users can be used to uncover key properties of their queueing policies and estimate their information processing rates and limits. Such an understanding of users' information processing behaviors allows us to infer whether and to what extent users suffer from information overload. Our analysis provides empirical evidence of information processing limits for social media users and the prevalence of information overloading. The most active and popular social media users are often the ones that are overloaded. Moreover, we find that the rate at which users receive information impacts their processing behavior, including how they prioritize information from different sources, how much information they process, and how quickly they process information. Finally, the susceptibility of a social media user to social contagions depends crucially on the rate at which she receives information. An exposure to a piece of information, be it an idea, a convention or a product, is much less effective for users that receive information at higher rates, meaning they need more exposures to adopt a particular contagion.
On Understanding the Divergence of Online Social Group Discussion
Authors: Purohit Hemant , Ruan Yiye , Fuhry David , Parthasarathy Srinivasan , Sheth Amit
Published: November 2022

We study online social group dynamics based on how group members diverge in their online discussions. Previous studies mostly focused on the link structure to characterize social group dynamics, whereas the group behavior of content generation in discussions is not well understood. Particularly, we use Jensen-Shannon (JS) divergence to measure the divergence of topics in user-generated contents, and how it progresses over time. We study Twitter messages (tweets) in multiple real-world events (natural disasters and social activism) with different times and demographics. We also model structural and user features with guidance from two socio-psychological theories, social cohesion and social identity, to learn their implications on group discussion divergence. Those features show significant correlation with group discussion divergence. By leveraging them we are able to construct a classifier to predict the future increase or decrease in group discussion divergence, which achieves an area under the curve (AUC) of 0.84 and an F-1 score (harmonic mean of precision and recall) of 0.8. Our approach allows to systematically study collective diverging group behavior independent of group formation design. It can help to prioritize whom to engage with in communities for specific topics of needs during disaster response coordination, and for specific concerns and advocacy in the brand management.
Do Topic-Dependent Models Improve Microblog Sentiment Estimation?
Authors: Chen Francine , Mirisaee Seyed
Published: November 2022

A topic-independent sentiment model is commonly used to estimate sentiment in microblogs. But for movie and product reviews, domain adaptation has been shown to improve sentiment estimation performance. We examined whether topic-dependent models improve polarity estimation of microblogs. We considered both a model trained on Twitter tweets containing a target keyword and a model trained on an enlarged set of tweets containing terms related to a topic.  Comparing the performance of the topic-dependent models to a topic-independent model trained on a general sample of  tweets, we noted that for some topics, topic-dependent models performed better. We then propose a method for predicting which topics are likely to have better sentiment estimation performance when a topic-dependent sentiment model is used.
Facebook, Twitter and Google Plus for Breaking News: Is There a Winner?
Authors: Osborne Miles , Dredze Mark
Published: November 2022

Twitter is widely seen as being the go to place for breaking news.Recently however, competing Social Media have begun to carry news.Here we examine how Facebook, Google Plus and Twitter report on breaking news. We consider coverage (whether news events are reported) and latency (the time when they are reported). Using data drawn from three weeks in December 2013, we identify 29 major news events, ranging from celebrity deaths, plague outbreaks to sports events. We find that all media carry the same major events, but Twitter continues to be the preferred medium for breaking news, almost consistently leading Facebook or Google Plus. Facebook and Google Plus largely repost newswire stories and their main research value is that they conveniently package multitple sources of information together.
Anonymity in Social Media: Effects of Content Controversiality and Social Endorsement on Sharing Behavior
Authors: Zhang Kaiping , Kizilcec René
Published: November 2022

The amount of information shared via social media is rapidly increasing amid growing concerns over online privacy. This study investigates the effect of controversiality and social endorsement of media content on sharing behavior when choosing between sharing publicly or anonymously. Anonymous sharing is found to be a popular choice (59% of shares), especially for controversial content which is 3.2x more likely to be shard anonymously. Social endorsement was not found to affect sharing behavior, except for sports-related content. Implications for social media interface design are discussed.
Measuring Post Traumatic Stress Disorder in Twitter
Authors: Coppersmith Glen , Harman Craig , Dredze Mark
Published: November 2022

Traditional mental health studies rely on information primarily collected through personal contact with a health care professional. Recent work has shown the utility of social media data for studying depression, but there have been limited evaluations of other mental health conditions. We consider post traumatic stress disorder (PTSD), a serious condition that affects millions worldwide, with especially high rates in military veterans. We also present a novel method to obtain a PTSD classifier for social media using simple searches of available Twitter data, a significant reduction in training data cost compared to previous work. We demonstrate its utility by examining differences in language use between PTSD and random individuals, building classifiers to separate these two groups and by detecting elevated rates of PTSD at and around U.S. military bases using our classifiers.
Summarizing Newspaper Comments
Authors: Llewellyn Clare , Grover Claire , Oberlander Jon
Published: November 2022

This work investigates summarizing the conversations that occur in the comments section of the UK newspaper the Guardian. In the comment summarization task comments are clustered and ranked within the cluster. The top comments from each cluster are used to give an overview of that cluster. It was found that topic model clustering gave the most agreement when evaluated against a human gold standard. This approach is compared to cosine distance clustering and k-means clustering. PageRank was found to be the prefered ranking system when compared with TF-IDF, Mutual Information gain and Maximal Marginal Relevance and evaluated against sets of comments summarized by a journalist for the Guardian letters page.
"I Didn't Sign Up for This!": Informed Consent in Social Network Research
Authors: Hutton Luke , Henderson Tristan
Published: November 2022

The issue of whether, and how, to obtain informed consent for researchstudies that use social network data has recently come to the fore insome controversial cases.Determining how to acquire valid consent that meets the expectations of participants, while minimising the burden placed on them, remains an open problem.We apply Nissenbaum's model of contextual integrity to the consent process, to study whether social norms of willingness to share social network data can be leveraged to avoid burdening participants with too many interventions, while still accurately capturing their own sharing intent. We find that for the 27.7% of our participants (N = 109) who conform to social norms, contextual integrity can be used to significantly reduce the time taken to capture their consent, while still maintaining accuracy. Our findings have implications for researchers conducting such studies who are looking to acquire informed consent without having to burden participants with many interactions.
How Viral Are Viral Videos?
Authors: Bauckhage Christian , Hadiji Fabian , Kersting Kristian
Published: November 2022

Within only a few years after the launch of video sharing platforms, viral videos have become a pervasive Internet phenomenon. Yet, notwithstanding growing scholarly interest, the suitability of the viral metaphor seems not to have been studied so far. In this paper, we therefore investigate the attention dynamics of viral videos from the point of view of mathematical epidemiology. We introduce a novel probabilistic model of the progression of infective diseases and use it to analyze time series of YouTube view counts and Google searches. Our results on a data set of almost 800 videos show that their attention dynamics are indeed well accounted for by our epidemic model. In particular, we find that the vast majority of videos considered in this study show very high infection rates.
Editorial Algorithms: Using Social Media to Discover and Report Local News
Authors: Schwartz Raz , Naaman Mor , Teodoro Rannie
Published: November 2022

The role of algorithms in the detection, curation and broadcast of news is becoming increasingly prevalent. To better understand this role we developed CityBeat, a system that implements what we call “editorial algorithms” to find possible news events. This fully functional system collects real time geo-tagged information from social media, finds key stories, makes an editorial decision whether these events are of interest and eventually visualizes these stories on a big screen display. The system was designed in collaboration with journalists and tested at four New York City newsrooms. Our results show that while journalists were receptive to the idea of machine-generated news stories, the actual results of the system confirmed current concerns among journalists and researchers about the dangers of outsourcing news finding tasks to machines. This paper therefore exemplifies how news sourcing systems based on social media may favor specific type of news events, do not report results quickly enough, and cater to a biased population and interests.
CENI: A Hybrid Framework for Efficiently Inferring Information Networks
Authors: Hu Qingbo , Xie Sihong , Lin Shuyang , Wang Senzhang , Yu Philip
Published: November 2022

Information links among users or websites drive the development of countless innovative applications. However, in reality, it is easier for us to observe the timestamps when different nodes in the network react on a message, while the connections empowering the information diffusion remain hidden. This motivates recent extensive studies on the network inference problem: how to uncover the edges from the records of messages disseminated through them. Many existing solutions are computationally expensive, which motivates us to develop an efficient two-step framework, Clustering Embedded Network Inference (CENI). CENI integrates clustering strategies to improve the efficiency of network inference. By clustering nodes on the timelines of messages, we propose two naive implementations of CENI: Infection-centric CENI and Cascade-centric CENI. We further point out the ritical dimension problem of CENI: in order to preserve the node structure hidden in the cascades, we need to first project the nodes into an Euclidean space of certain dimension before clustering.By addressing this problem, we propose the third implementation of the CENI framework: Projection-based CENI. Experiments on two real datasets show that the three CENI models only need around 20% ~ 50% of the running time of some state-of-the-art methods, while the inferred edges have similar or slightly better F-measure.
Distant Supervision for Tweet Classification Using YouTube Labels
Authors: Magdy Walid , Sajjad Hassan , El-Ganainy Tarek , Sebastiani Fabrizio
Published: November 2022

We study an approach to tweet classification based on distant supervision, whereby we automatically transfer labels from one social medium to another. In particular, we apply classes assigned to YouTube videos to tweets linking to these videos. This provides for free a virtually unlimited number of labelled instances that can be used as training data. The experiments we have run show that a tweet classifier trained via these automatically labelled data substantially outperforms an analogous classifier trained with a limited amount of manually labelled data.
Penny for Your Thoughts: Searching for the 50 Cent Party on Sina Weibo
Authors: Yang Xiaofeng , Yang Qian , Wilson Christo
Published: November 2022

Evidence suggests that the Chinese government employs “Internet Commentators” to post propaganda on social media. This group is pejoratively nicknamed the “50 cent party” or Wumao. In this study, we make the first attempt to quantify the size and behavior of the Wumao. Our study leverages a large corpus of data from Sina Weibo (Twitter in China) that includes 26M tweets and comments from 2.7M users over the span of one year. Unfortunately, detecting the Wumao is difficult because there is no ground truth information about them. To overcome this challenge, we apply a series of unsupervised techniques to filter our dataset and isolate suspicious users who exhibit characteristics indicative of being Wumao.
Local Variation of Collective Attention in Hashtag Spike Trains
Authors: Sanli Ceyda , Lambiotte Renaud
Published: November 2022

In this paper, we propose a methodology quantifying temporal patterns of nonlinear hashtag time series. Our approach is based on an analogy between neuron spikes and hashtag diffusion. We adopt the local variation, originally developed to analyze local time delays in neuron spike trains. We show that the local variation successfully characterizes nonlinear features of hashtag spike trains such as burstiness and regularity. We apply this understanding in an extreme social event and are able to observe temporal evaluation of online collective attention of Twitter users to that event.
Deciding What to Display: Maximizing the Information Value of Social Media
Authors: Servia-Rodríguez Sandra , Huberman Bernardo , Asur Sitaram
Published: November 2022

In information-rich environments, the competition for users' attention leads to a flood of content from which people often find hard to sort out the most relevant and useful pieces. Using Twitter as a case study, we applied an attention economy solution to generate the most informative tweets for its users. By considering the novelty and popularity of tweets as objective measures of their relevance and utility, we used the Huberman-Wu algorithm to automatically select the ones that will receive the most attention in the next time interval. Their predicted popularity was confirmed by using Twitter data collected for a period of 2 months.
Anticipating Activity in Social Media Spikes
Authors: Higham Desmond , Mantzaris Alexander V. , Grindrod Peter , Otley Amanda , Laflin Peter
Published: November 2022

We propose a novel mathematical model for the activity of microbloggers during an external, event-driven spike. The model leads to a testable prediction of who would become most active if a spike were to take place. This type of insight into human behaviour has many applications, as it identifies key players who can be targeted with information in real time when the network is most receptive. The model takes account of the fact that dynamic interactions evolve over an underlying, static network that records "who listens to whom". Our fundamental assumption is that, in the case where the entire community has become aware of an external news event, a key driver of activity is the motivation to participate by responding to incoming messages. We validate the resulting algorithm on a large scale Twitter conversation concerning the appointment of a UK Premier League football club manager. We also find that the half-life of a spike in activity can be quantified in terms of the network size and the typical response rate.
Collaborative Visualizations for Wikipedia Critique and Activism
Authors: De Sabbata Stefano , Çöltekin Arzu , Eccles Kathryn , Hale Scott , Straumann Ralph
Published: November 2022

Wikipedia is one of the largest platforms based on the concept of asynchronous, distributed, collaborative work. A systematic collaborative exploration and assessment of Wikipedia content and coverage is however still largely missing. On the one hand editors routinely perform quality and coverage control of individual articles, while on the other hand academic research on Wikipedia is mostly focused on global issues, and only sporadically on local assessment. In this paper, we argue that collaborative visualizations have the potential to fill this gap, affording editors to collaboratively explore and analyse patterns in Wikipedia content, at different scales. We illustrate how a collaborative visualization service can be an effective tool for editors to create, edit, and discuss public visualizations of Wikipedia data. Combined with the large Wikipedia user-base, and its diverse local knowledge, this could result in a large-scale collection of evidence for critique and activism, and the potential to enhance the quantity and quality of Wikipedia content.
Wikipedia, Academia, and Science
Authors: Aibar Eduard
Published: November 2022

This paper presents some results of an ongoing research project on the interactions between Wikipedia and academia. The first part of the project analyses the perception and practices of academic faculty about Wikipedia. It also includes a study on 52 teaching experiences at universities around the world where lecturers have used Wikipedia for designing assignments involving students to edit the free encyclopedia. The second part of the project, still ongoing, is aimed at analyzing the scientific content of Wikipedia, in order to see how the non-expert nature of most of its editors shapes the way science and technology issues are presented in its articles.
Quo Vadis? On the Effects of Wikipedia’s Policies on Navigation
Authors: Lamprecht Daniel , Helic Denis , Strohmaier Markus
Published: November 2022

We propose to study the influences of Wikipedia’s policies on navigation in Wikipedia and describe our methods to study navigational biases, assess the guidelines provided by the Manual of Style, and investigate the neutrality of navigation.
The Transmission of Scientific Knowledge to Wikipedia
Authors: Teplitskiy Misha , Lu Grace , Duede Eamon
Published: November 2022

This paper compares the scientific literature used most often by scientists to the scientific literature referenced on the English-language Wikipedia. Previous studies have raised concerns that editors of science-related articles on Wikipedia are biased toward easily available sources and underrepresent particular scientific fields. Most often, these studies examine references on Wikipedia only but make claims about how well or poorly Wikipedia represents the scientific literature as a whole. In contrast, the present study begins with the scientific literature. We use the Scopus database to identify the 250 most heavily used journals in each of 26 research fields (4620 journals in total), and estimate a variety of models to identify what makes these journals more or less likely to be cited on Wikipedia. We find that, controlling for impact factor and open access policy, Wikipedia over-represents journals from the Social Sciences, and under-represents journals from the Physical Sciences and Health Sciences. An open-access policy is not associated with increased Wikipedia presence. The most significant predictor that a journal will be cited on Wikipedia is its impact factor.
Heuristic AND/OR Search for Solving Influence Diagram
Authors: Lee Junkyu , Marinescu Radu , Dechter Rina
Published: November 2022

An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies.
Embedding Directed Graphs in Potential Fields Using FastMap-D
Authors: Gopalakrishnan Sriram , Cohen Liron , Koenig Sven , Kumar T. K.
Published: November 2022

Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the to-and-fro pairwise distances in directed graphs. FastMap-D learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.
On the Benefits of Randomly Adjusting Anytime Weighted A*
Authors: Bhatia Abhinav , Svegliato Justin , Zilberstein Shlomo
Published: November 2022

Anytime Weighted A*---an anytime heuristic search algorithm that uses a weight to scale the heuristic value of each node in the open list---has proven to be an effective way to manage the trade-off between solution quality and computation time in heuristic search. Finding the best weight, however, is challenging because it depends on not only the characteristics of the domain and the details of the instance at hand, but also the available computation time. We propose a randomized version of this algorithm, called Randomized Weighted A*, that randomly adjusts its weight at runtime and show a counterintuitive phenomenon: RWA* generally performs as well or better than AWA* with the best static weight on a range of benchmark problems. The result is a simple algorithm that is easy to implement and performs consistently well without any offline experimentation or parameter tuning.
ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding
Authors: Chan Shao-Hung , Li Jiaoyang , Gange Graeme , Harabor Daniel , Stuckey Peter J. , Koenig Sven
Published: November 2022

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.
Multi-Target Search in Euclidean Space with Ray Shooting
Authors: Hechenberger Ryan , Harabor Daniel D. , Cheema Muhammad Aamir , Stuckey Peter J. , Le Bodic Pierre
Published: November 2022

The shortest path problem (SPP) asks us to find a minimum length path between two points, usually on a graph. In a Euclidean environment the points are in a 2D plane and here the path must avoid a set of polygonal obstacles. Solution methods for this Euclidean SPP (ESPP) typically convert the continuous 2D map into a discretised representation, like a graph or navigation mesh. RayScan is a recent and fast ESPP algorithm which avoids the preprocessing step by using a combination of "ray shooting" and polygon scanning. In this paper we improve the performance of RayScan using spatial reasoning and ray caching techniques. We also extend the algorithm, from single-target search to a multi-target setting. Comparative game map experiments show a substantial speedup.
Extended Abstract: A Competitive Analysis of Online Multi-Agent Path Finding
Authors: Ma Hang
Published: November 2022

This is an extended abstract of a paper to be published at ICAPS 2021. We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories. We present several complexity and competitiveness results for online MAPF and its algorithms, which provides theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.
Linear-Space Best-First Diagnosis Search
Authors: Rodler Patrick
Published: November 2022

Various model-based diagnosis scenarios require the computation of the most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, to enable successful diagnosis on memory-restricted devices and for memory-intensive problem cases, we propose RBF-HS, a diagnostic search based on Korf’s seminal RBFS algorithm. RBF-HS can enumerate an arbitrary ﬁxed number of fault explanations in best-ﬁrst order within linear space bounds, without sacriﬁcing the desirable soundness or completeness properties. Evaluations using real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space (up to 98 %) while requiring only reasonably more or even less time than Reiter’s HS-Tree, one of the most widely used diagnostic algorithms with the same properties.
How to Speed-Up the Automated Configuration of Optimization Algorithms
Authors: De Souza Marcelo
Published: November 2022

This paper presents a set of capping methods to speed-up the automated configuration of optimization algorithms. These methods use known previous executions to compute a performance envelope, which is used to evaluate new executions and early stop those with unsatisfactory performance. Preliminary experiments on six scenarios show that the capping methods save up to 78% of the configuration effort, while finding configurations of the same quality.
Studying Online Multi-Agent Path Finding
Authors: Morag Jonathan , Stern Roni , Felner Ariel , Atzmon Dor , Boyarski Eli
Published: November 2022

Multi-agent path finding (MAPF) is the problem of planning a set of non-conflicting plans on a graph, for a set of agents. Online MAPF extends MAPF by considering a more realistic problem in which new agents may appear over time.
While planning, an online solver does not know whether and which agents will join in the future. Therefore, in online problems the notion of snapshot-optimal was defined, where only current knowledge is considered. The quality of such a solution may be weaker than the quality of a solution to an equivalent offline MAPF problem (offline-optimality), where the solver is preinformed of all the agents that will appear in the future. In this paper we explore, theoretically and empirically, the quality of snapshot-optimal solutions compared to offline-optimal solutions.
Meta-Level Techniques for Planning, Search, and Scheduling
Authors: Shperberg Shahaf S.
Published: November 2022

Metareasoning is a core idea in AI at that captures the essence of being both human and intelligent. This idea is that much can be gained by thinking (reasoning) about one's own thinking. In the context of search and planning, metareasoning concerns with making explicit decisions about computation steps, by comparing their `cost' in computational resources, against the gain they can be expected to make towards advancing the search for solution (or plan) and thus making better decisions. To apply metareasoning, a meta-level problem needs to be defined and solved with respect to a specific framework or algorithm. In some cases, these meta-level problems can be very hard to solve. Yet, even a fast-to-compute approximation of meta-level problems can yield good results and improve the algorithms to which they are applied. This paper provides an overview of different settings in which we applied metareasoning to improve search, planning and scheduling.
Which MAPF Model Works Best for Automated Warehousing?
Authors: Varambally Sumanth , Li Jiaoyang , Koenig Sven
Published: November 2022

Multi-Agent Path Finding (MAPF) algorithms and their variants can find high-quality collision-free plans for automated warehousing under simplified assumptions about the robot dynamics. However, these simplifying assumptions pose challenging implementational issues as the robots cannot follow the plans precisely. Various robust execution frameworks, such as the Action Dependency Graph (ADG) framework, have been proposed to enable the real-world execution of MAPF plans. Under such a framework, it is unclear how the simplifying assumptions affect the performance of the robots. In this work, we first argue that the ADG framework provides the same robustness guarantees as the single-agent framework (where plans are generated independently for each robot and collisions are avoided through a reservation table), which is widely used in industry. We then improve the efficiency of the ADG framework by integrating it with the Rolling-Horizon Collision-Resolution framework to solve MAPF problems with a persistent stream of online tasks. Using the integrated framework, we compare the standard MAPF model with many of its more complex variants, such as MAPF with rotation, k-robust MAPF, and continuous-time MAPF (taking robot dynamics into account). We examine their effectiveness in improving throughput through realistic simulations of warehouse settings with the Gazebo simulator.
Parallel Beam Search for Combinatorial Optimization (Extended Abstract)
Authors: Frohner Nikolaus , Gmys Jan , Melab Nouredine , Raidl Günther R. , Talbi El-ghazali
Published: November 2022

Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present preliminary results of a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. For sufficiently large problem instances and beam widths our work-in-progress implementation in the JIT-compiled Julia language admits promising speed-ups over 30x on 32 cores with uniform memory access for the Permutation Flow Shop Scheduling (PFSP) problem with flowtime objective.
Sampling from Pre-Images to Learn Heuristic Functions for Classical Planning (Extended Abstract)
Authors: O'Toole Stefan , Ramirez Miquel , Lipovetzky Nir , Pearce Adrian R.
Published: November 2022

We introduce a new algorithm, Regression based Supervised Learning (RSL), for learning per instance Neural Network (NN) defined heuristic functions for classical planning problems. RSL uses regression to select relevant sets of states at a range of different distances from the goal. RSL then formulates a Supervised Learning problem to obtain the parameters that define the NN heuristic, using the selected states labeled with exact or estimated distances to goal states. Our experimental study shows that RSL outperforms, in terms of coverage, previous classical planning NN heuristics functions while requiring a fraction of the training time.
Improving Local Search for Resource-Constrained Planning
Authors: Nakhost Hootan , Hoffmann Jörg , Müller Martin
Published: November 2022

A ubiquitous feature of planning problems — problems involving the automatic generation of action sequences for attaining a given goal — is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.
Adding Diversity to Classical Heuristic Planning
Authors: Linares López Carlos , Borrajo Daniel
Published: November 2022

In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.
Scalable Distributed Monte-Carlo Tree Search
Authors: Yoshizoe Kazuki , Kishimoto Akihiro , Kaneko Tomoyuki , Yoshimoto Haruhiro , Ishikawa Yutaka
Published: November 2022

Monte-Carlo Tree Search (MCTS) is remarkably successful in two-player games, but parallelizing MCTS has been notoriously difficult to scale well, especially in distributed environments. For a distributed parallel search, transposition-table driven scheduling (TDS) is known to be efficient in several domains. We present a massively parallel MCTS algorithm, that applies the TDS parallelism to the Upper Confidence bound Applied to Trees (UCT) algorithm, which is the most representative MCTS algorithm. To drastically decrease communication overhead, we introduce a reformulation of UCT called Depth-First UCT. The parallel performance of the algorithm is evaluated on clusters using up to 1,200 cores in artificial game-trees. We show that this approach scales well, achieving 740-fold speedups in the best case.
The Compressed Differential Heuristic
Authors: Goldenberg Meir , Sturtevant Nathan , Felner Ariel , Schaeffer Jonathan
Published: November 2022

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper, we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) can be tuned to fit any size of memory, even smaller than the size of the state space.Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress
MCTS Based on Simple Rerget
Authors: Tolpin David , Shimony Solomon
Published: November 2022

UCT, a state-of-the art algorithm for Monte Carlo tree search (MCTS),is based on UCB, a policy for the Multi-armed Bandit problem (MAB) thatminimizes the cumulative regret. However, search differs from MAB inthat in MCTS it is usually only the final ``arm pull''that collects a reward, rather than all ``arm pulls''.Therefore, it makes more sense to minimize the simple, rather thancumulative, regret. We introduce policies formulti-armed bandits with lower simpleregret than UCB and develop a two-stage scheme (SR+CR) for MCTSwhich outperforms UCT empirically. We also propose a samplingscheme based on value of information (VOI), achieving an algorithmthat empirically outperforms other proposed algorithms.
E-Graphs: Bootstrapping Planning with Experience Graphs
Authors: Phillips Mike , Cohen Benjamin , Chitta Sachin , Likhachev Maxim
Published: November 2022

In this paper, we develop an online motion planning approach which learns from its planning episodes (experiences) a graph, an Experience Graph. On the theoretical side, we show that planning with Experience graphs is complete and provides bounds on suboptimality with respect to the graph that represents the original planning problem. Experimentally, we show in simulations and on a physical robot that our approach is particularly suitable for higher-dimensional motion planning tasks such as planning for two armed mobile manipulation.
A* Variants for Optimal Multi-Agent Pathfinding
Authors: Goldenberg Meir , Felner Ariel , Stern Roni , Schaeffer Jonathan
Published: November 2022

Several variants of A* have been recently proposed for find-ing optimal solutions for the multi-agent pathfinding (MAPF)problem. We describe the application of the new enhancedpartial-expansion technique to MAPF, show how patterndatabases can be applied on top of this technique and com-pare the different A* variants experimentally.
Non-Optimal Multi-Agent Pathfinding is Solved (Since 1984)
Authors: Röger Gabriele , Helmert Malte
Published: November 2022

Optimal solutions for multi-agent pathfinding problems are often too expensive to compute. For this reason, suboptimal approaches have been widely studied in the literature. Specifically, in recent years a number of efficient suboptimal algorithms that are complete for certain subclasses have been proposed at highly-rated robotics and AI conferences, all mentioning that it is an open problem which subclasses of non-optimal multi-agent pathfinding are tractable. However, it turns out that this problem has already been completely solved in another research community in the 1980s by a constructive proof that provides a polynomial algorithm that is complete for the entire class of problems. In this paper, we would like to bring this earlier related work to the attention of the robotics and AI communities.
Active Stratified Sampling with Clustering-Based Type Systems for Predicting the Search Tree Size of Problems with Real-Valued Heuristics
Authors: Lelis Levi
Published: November 2022

In this paper we advance the line of research launched by Knuth which was later improved by Chen for predicting the size of the search tree expanded by heuristic search algorithms such as IDA*. Chen's Stratified Sampling (SS) uses a partition of the nodes in the search tree called type system to guide its sampling. Recent work has shown that SS using type systems based on integer-valued heuristic functions can be quite effective. However, type systems based on real-valued heuristic functions are often too large to be practical. We use the k-means clustering algorithm for creating effective type systems for domains with real-valued heuristics. Orthogonal to the type systems, another contribution of this paper is the introduction of an algorithm called Active SS. SS allocates the same number of samples for each type. Active SS is the application of the idea of active sampling to search trees. Active SS allocates more samples to the types with higher uncertainty. Our empirical results show that (i) SS using clustering-based type systems tends to produce better predictions than competing schemes that do not use a type system, and that (ii) Active SS can produce better predictions than the regular version of SS.