bluuebunny/crossref_metadata_2025 huggingface dataset:
Link and Triadic Closure Delay: Temporal Metrics for Social Network Dynamics
Authors: Zignani Matteo , Gaito Sabrina , Rossi Gian Paolo , Zhao Xiaohan , Zheng Haitao , Zhao Ben
Published: November 2022

Today, numerous models and metrics are available to capture and characterize static properties of online social networks. When it comes to understanding their dynamics and evolution, however, research offers little interms of metrics or models. Current metrics are limited to logical time clocks, and unable to capture interactions with external factors that rely on physical time clocks. In this paper, our goal is to take initial steps towards building a set of metrics for characterizing social network dynamics based on physical time. We focus our attention on two metrics that capture the "eagerness" of users in building social structure. More specifically, we propose metrics of link delay and triadic closure delay, two metrics that capture the time delay between when a link or triadic closure is possible,and when they actually instantiate in the trace. Considered over time or across traces, the value of these metrics can provide insight on the speed at which users act in building and extending their social neighborhoods. We apply these metrics to two real traces of social network dynamics from the Renren and Facebook networks. We show that these metrics are generally consistent across networks, but their differences reveal interesting properties of each system. We argue that they can be attributed to factors such as network maturity, environmental and social contexts, and services offered by network provider, all factors independent of the network topology and captured by our proposed metrics. Finally, we find that triadic closure delays capture the ease of neighbor discovery in social networks, and can be strongly influenced by friend recommendation systems.
Stacked Generalization Learning to Analyze Teenage Distress
Authors: Dinakar Karthik , Weinstein Emily , Lieberman Henry , Selman Robert
Published: November 2022

The internet has become a resource for adolescents who are distressed by social and emotional problems. Social network analysis can provide new opportunities for helping people seeking support online, but only if we understand the salient issues that are highly relevant to participants personal circumstances. In this paper, we present a stacked generalization modeling approach to analyze an online community supporting adolescents under duress. While traditional predictive supervised methods rely on robust hand-crafted feature space engineering, mixed initiative semi-supervised topic models are often better at extracting high-level themes that go beyond such feature spaces. We present a strategy that combines the strengths of both these types of models inspired by Prevention Science approaches which deals with the identification and amelioration of risk factors that predict to psychological, psychosocial, and psychiatric disorders within and across populations (in our case teenagers) rather than treat them post-facto. In this study, prevention scientists used a social science thematic analytic approach to code stories according to a fine-grained analysis of salient social, developmental or psychological themes they deemed relevant, and these are then analyzed by a society of models. We show that a stacked generalization of such an ensemble fares better than individual binary predictive models.
Exploring the Relationship between Membership Turnover and Productivity in Online Communities
Authors: Qin Xiangju , Salter-Townshend Michael , Cunningham Padraig
Published: November 2022

One of the more disruptive reforms associated with the modern Internet is the emergence of online communities working together on knowledge artefacts such as Wikipedia and OpenStreetMap. Recently it has become clear that these initiatives are vulnerable because of problems with membership turnover. This study presents a longitudinal analysis of 891 WikiProjects where we model the impact of member turnover and social capital losses on project productivity. By examining social capital losses we attempt to provide a more nuanced analysis of member turnover. In this context social capital is modelled from a social network perspective where the loss of more central members has more impact. We find that only a small proportion of WikiProjects are in a relatively healthy state with low levels of membership turnover and social capital losses. The results show that the relationship between social capital losses and project performance is U-shaped, and that member withdrawal has significant negative effect on project outcomes. The results also support the mediation of turnover rate and network density on the curvilinear relationship.
Privacy Considerations for Public Storytelling
Authors: Wienberg Christopher , Gordon Andrew
Published: November 2022

The popularity of the web and social media have afforded researchers unparalleled access to content about the daily lives of people. Human research ethics guidelines, while actively expanding to meet the new challenges posed by web research, still rely on offline principles of interaction that are a poor fit to modern technology. In this context, we present a study of the identifiability of authors of socially sensitive content. With the goal of identity obfuscation, we compare this to the identifiability of the same content translated to and then back from a foreign language, focusing on how easily a person could locate the original source of the content. We discuss the risk to these authors presented by dissemination of their content, and consider the implications for research ethics guidelines.
A Platform for Visually Exploring the Development of Wikipedia Articles
Authors: Borra Erik , Laniado David , Weltevrede Esther , Mauri Michele , Magni Giovanni , Venturini Tommaso , Ciuccarelli Paolo , Rogers Richar , Kaltenbrunner Andreas
Published: November 2022

When looking for information on Wikipedia, Internet users generally just read the latest version of an article. However, in its back-end there is much more: associated to each article are the edit history and talk pages, which together entail its full evolution. These spaces can typically reach thousands of contributions, and it is not trivial to make sense of them by manual inspection. This issue also affects Wikipedians, especially the less experienced ones, and constitutes a barrier for new editor engagement and retention. To address these limitations, Contropedia offers its users unprecedented access to the development of an article, using wiki links as focal points.
Towards Lifestyle Understanding: Predicting Home and Vacation Locations from User's Online Photo Collections
Authors: Zheng Danning , Hu Tianran , You Quanzeng , Kautz Henry , Luo Jiebo
Published: November 2022

Semantic place labeling has been actively studied in the past few years due to its importance in understanding human mobility and lifestyle patterns. In the last decade, the rapid growth of geotagged multimedia data from online social networks provides a valuable opportunity to predict people's POI locations from temporal, spatial and visual cues. Among the massive amount of social media data, one important type of data is the geotagged web images from image-sharing websites. In this paper, we develop a reliable photo classifier based on the Convolutional Neutral Networks to classify the photo-taking scene of real-life photos. We then present a novel approach to home location and vacation locations prediction by fusing together the visual content of photos and the spatiotemporal features of people's mobility patterns. Using a well-trained classifier, we showed that the robust fusion of visual and spatiotemporal features achieves significant accuracy improvement over each of the features alone for both home and vacation detection.
The International Affiliation Network of YouTube Trends
Authors: Platt Edward , Bhargava Rahul , Zuckerman Ethan
Published: November 2022

Online video, a ubiquitous, visual, and highly shareable medium, is well-suited to crossing geographic, cultural,and linguistic barriers. Trending videos in particular,by virtue of reaching a large number of viewers in a short span of time, are powerful as both influencers and indicators of international communication flows. In this work, we study a large set of videos trending across 57 nations, collected from YouTube over a7-month period. We consider the set as a network of content flowing between nations, then develop conditional co-affiliation, a nation-nation co-affiliation index that enables a meaningful interpretation of network path length and the application of betweenness centrality. We observe a highly-interlinked network with remarkably similar co-affiliation levels between very different nations.However, Arabic-speaking nations appear more isolated, with the U.A.E. emerging as a key bridge. By analyzing video trend lifespans, we show that nations having many globally-popular video trends are reliably not the nation where those trends are strongest: we see no evidence to support the widely discussed idea of cultural exporter or trendsetter nations. We model correlations between co-affiliation and a selection of contextual factors. We note a surprisingly complex interaction between migration and shared video trends. Consistent with existing work on video popularity, we find that long trending times within one nation do not necessarily translate to reaching a wide global audience. This work expands on previous studies of the geographic popularity of videos by incorporating trending data and extending our analysis from video-nation affiliations to nation-nation co-affiliations. Characterizing these relationships is key to understanding the international cultural impact and potential of online video.
Why We Filter Our Photos and How It Impacts Engagement
Authors: Bakhshi Saeideh , Shamma David , Kennedy Lyndon , Gilbert Eric
Published: November 2022

A variety of simple graphical filters are available to camera phone users to enhance their photos on the fly; these filters often stylize, saturate or age a photo. In this paper, we present a combination of large-scale data analysis and small scale in-depth interviews to understand filter-work. We look at producers’ practices of photo filtering and gain insights in the roles filters play in engaging photo consumers’ by driving their social interactions. We first interviewed 15 Flickr mobile app users (photo producers) to understand their use and perception of filters. Next, we analyzed how filters affect a photo’s engagement (consumers’ perspective) using a corpus of 7.6 million Flickr photos. We find two groups of serious and casual photographers among filter users. The serious see filters as correction tools and prefer milder effects. Casual photographers, by contrast, use filters to significantly transform their photos with bolder effects. We also find that filtered photos are 21% more likely to be viewed and 45% more likely to be commented on by consumers of photographs. Specifically, filters that increase warmth, exposure and contrast boost engagement the most. Towards the ongoing research in social engagement and photo-work, these findings suggest several practical implications such as designing filters for both serious and casual photographers or designing methods to prioritize and rank content in order to maximize engagement.
Audience Analysis for Competing Memes in Social Media
Authors: Carton Samuel , Park Souneil , Zeffer Nicole , Adar Eytan , Mei Qiaozhu , Resnick Paul
Published: November 2022

Existing tools for exploratory analysis of information diffusion in social media focus on the message senders who actively diffuse the meme. We develop a tool for audience analysis, focusing on the people who are passively exposed to the messages, with a special emphasis on competing memes such as propagations and corrections of a rumor. In such competing meme diffusions, important questions include which meme reached a bigger total audience, the overlap in audiences of the two, and whether exposure to one meme inhibited propagation of the other. We track audience members’ states of interaction, such as having been exposed to one meme or another or both. We analyze the marginal impact of each message in terms of the number of people who transition between states as a result of that message. These marginal impacts can be computed efficiently, even for diffusions involving thousands of senders and millions of receivers. The marginal impacts provide the raw material for an interactive tool, RumorLens, that includes a Sankey diagram and a network diagram. We validate the utility of the tool through a case study of nine rumor diffusions. We validate the usability of the tool through a user study, showing that nonexperts are able to use it to answer audience analysis questions.
What MMO Communities Don’t Do: A Longitudinal Study of Guilds and Character Leveling, Or Not
Authors: Poor Nathaniel
Published: November 2022

Guilds, a primary form of community in many online games, are thought to both aid gameplay and act as social entities. This work uses a three-year scrape of one game, World of Warcraft, to study the relationship between guild membership and advancement in the game as measured by character leveling, a defining and often studied metric. 509 guilds and 90,581 characters are included in the analysis from a three-year period with over 36 million observations, with linear regression to measure the effect of guild membership. Overall findings indicate that guild membership does not aid character leveling to any significant extent. The benefits of guilds may be replicated by players in smaller guilds or not in guilds through game affordances and human sociability.
Social Cues and Interest in Reading Political News Stories
Authors: Agapie Elena , Munson Sean
Published: November 2022

People tend to prefer information sources that agree with their viewpoints, as predicted by the selective exposure theory, and to associate with people who are like them, a process known as homophily. Scholars raise fears that the combination of these factors can limit the diversity of viewpoints to which people are exposed, particularly when people find news through social network sites. In this study, we evaluate whether we can use annotations showing that a story was shared by people who are in some way similar to encourage people to read articles that may challenge their viewpoints. Most annotations (shared city, employer, music tastes, liked organizations, and friendship) had no discernable effect on reading interest compared to no annotation. Shared job type, though, led to decreased interest in reading an article. Although people consider themselves similar to others sharing news articles, this predominantly does not change their reading interest.
Digital Rendezvous: Experiences of Students, Staff, and Alumni on a Campus Memory Map
Authors: Powell Allison , Hendrick Brian , Ganguli Arpan , Sargsyan Tatevik , Shah Shagun , Tkavc-Dubokovic Eva
Published: November 2022

This project aims to develop interactive maps, where students, stuff, and alumni can share their memories about a physical space: a university campus. We propose creating several digital maps of the LSE for past decades, where individuals associated with the university can map their memories with current or past physical spaces around the campus. The visualization of historical and current transformation of this physical landscape will potentially promote ties in this community of association and contribute to the growing body of work on collaborative memory and geo-socially located imaginaries.
On Inference of Sense of Place from Geo-Social Networks
Authors: Kursad Oz Bilgehan , Taskaya Temizel Tugba
Published: November 2022

The aim of the study is to investigate whether individuals report the places they are attached to in location-based services, and whether there is a relationship between the attachment scores of these places and their corresponding check-in frequency information. A survey is conducted to measure the degree of place attachment of individuals based on self-reported locations. Then their Foursquare log data is collected which includes their check-in and venue information. Our results show that the majority of the participants check in to locations that they are attached to. Attachment score is shown to be related to the check-in frequency. The tips left for venues include terms and phrases, suggesting place attachment.
Eliciting Disease Data from Wikipedia Articles
Authors: Fairchild Geoffrey , De Silva Lalindra , Del Valle Sara , Segre Alberto
Published: November 2022

Traditional disease surveillance systems suffer from several disadvantages, including reporting lags and antiquated technology, that have caused a movement towards internet-based disease surveillance systems. Internet systems are particularly attractive for disease outbreaks because they can provide data in near real-time and can be verified by individuals around the globe. However, most existing systems have focused on disease monitoring and do not provide a data repository for policy makers or researchers. In order to fill this gap, we analyzed Wikipedia article content. We demonstrate how a named-entity recognizer can be trained to tag case counts, death counts, and hospitalization counts in the article narrative that achieves an F1 score of 0.753. We also show, using the the 2014 West African Ebola virus disease epidemic article as a case study, that there are detailed time series data that are consistently updated that closely align with ground truth data. We argue that Wikipedia can be used to create the first community-driven open-source emerging disease detection, monitoring, and repository system.
A Lightly Supervised Approach to Role Identification in Wikipedia Talk Page Discussions
Authors: Ferschke Oliver , Yang Diyi , Rosé Carolyn
Published: November 2022

In this paper we describe an application of a lightly supervised Role Identification Model (RIM) to the analysis of coordination in Wikipedia talk page discussions. Our goal is to understand the substance of important coordination roles that predict quality of the Wikipedia pages where the discussions take place. Using the model as a lens, we present an analysis of four important coordination roles identified using the model, including Workers, Critiquers, Encouragers, and Managers.
Towards Better Visual Tools for Exploring Wikipedia Article Development — The Use Case of "Gamergate Controversy"
Authors: Flöck Fabian , Laniado David , Stadthaus Felix , Acosta Maribel
Published: November 2022

We present a comparative analysis of three tools for visually exploring the revision history of a Wikipedia article. We do so on the use case of "Gamergate Controversy", an article that has been the setting of a major editor dispute in the last half of 2014 and early 2015, resulting in multiple editor bans and gathering news media attention. We show how our tools can be used to visually explore editor disagreement interactions and networks, as well as conflicted content and provenance, and present some of the results. We argue that these individual tools could benefit from synergies by combining them and lay out a possible architecture for doing so.
Unpacking the Structure of Knowledge Diffusion in Wikipedia: Local Biases, Noble Prizes and the Wisdom of Crowds
Authors: Dondio Pierpaolo , Casnici Niccolo , Squazzoni Flaminio
Published: November 2022

This paper investigates the diffusion of around 100,000 articles about literary authors in 52 versions of Wikipedia. We studied how Wiki versions replicate articles of authors belonging to a particular linguistic group and we collected findings about the potential mechanisms governing the replication process and its fairness. Results showed that diffusion of articles follows a power law, governed by strong preferences among versions, with a high number of isolated articles only present in one Wikipedia version. We found that the English Wiki has a prominent role in diffusing knowledge. However, results also showed that other Wikipedia versions were fundamental to building a rich global corpus of knowledge. Classical Greek and Latin authors resulted the most replicated set of entries. We found that geographic proximity and linguistic similarity was pivotal to explaining mutual links between Wikis. Finally, despite the presence of preference mechanisms, we found how the relative importance that each Wikipedia versions assigns to the set of authors of each language is significantly correlated with an expert-based ranking built on the outcome of various international literary awards, including the Nobel Prize. Moreover, we showed how Wikipedia exhibits a strong Wisdom of Crowds effect, with the collective opinion of all the Wikipedia versions showing a correlation with the experts higher than any individual Wikipedia version, with a value for Pearson's’ r of about 0.9.
Multi-Directional Search
Authors: Atzmon Dor , Li Jiaoyang , Felner Ariel , Nachmani Eliran , Shperberg Shahaf , Sturtevant Nathan , Koenig Sven
Published: November 2022

In the Multi-Agent Meeting (MAM) problem, the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding optimal meeting locations for multiple agents. A number of admissible heuristics are proposed and experiments demonstrate the benefits of MM*.
A Simple and Fast Bi-Objective Search Algorithm
Authors: Hernández Ulloa Carlos , Yeoh William , Baier Jorge , Suazo Luis , Zhang Han , Koenig Sven
Published: November 2022

Many interesting search problems can be formulated as bi-objective search problems; for example, transportation problems where both travel distance and time need to be minimized. Multi-objective best-ﬁrst search algorithms need to maintain the set of undominated paths from the start state to each state to compute a set of paths from a given start state to a given goal state (the Pareto-optimal solutions) such that no path in the set is dominated by another path in the set. Each time they ﬁnd a new path to a state n, they perform a dominance check to determine whether such a path dominates any of the previously found paths to n. Existing algorithms do not perform these checks efﬁciently, requiring at least a full iteration over the Open list per check. In this paper, we present the ﬁrst multi-objective algorithm that performs these checks efﬁciently. Indeed, Bi-Objective A* (BOA*)—our algorithm—requires constant time to check for dominance. Our experimental evaluation shows that BOA*is orders-of-magnitude faster than state-of-the-art search algorithms, such as NAMOA*, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
Moving Agents in Formation in Congested Environments
Authors: Li Jiaoyang , Sun Kexuan , Ma Hang , Felner Ariel , Kumar T. K. , Koenig Sven
Published: November 2022

In this paper, we formalize and study the Moving Agents in Formation (MAiF) problem, that combines the tasks of finding short collision-free paths for multiple agents and keeping them in close adherence to a desired formation. Previous work includes controller-based algorithms, swarm-based algorithms, and potential-field-based algorithms. They usually focus on only one or the other of these tasks, solve the problem greedily without systematic search, and thus generate costly solutions or even fail to find solutions in congested environment. In this paper, we develop a two-phase search algorithm, called SWARM-MAPF, whose first phase is inspired by swarm-based algorithms (in open regions) and whose second phase is inspired by multi-agent path-finding (MAPF) algorithms (in congested regions). In the first phase, SWARM-MAPF selects a leader among the agents and finds a path for it that is sufficiently far away from the obstacles so that the other agents can preserve the desired formation around it. It also identifies the critical segments of the leader's path where the other agents cannot preserve the desired formation and the refinement of which has thus to be delegated to the second phase. In the second phase, SWARM-MAPF refines these segments. Theoretically, we prove that SWARM-MAPF is complete. Empirically, we show that SWARM-MAPF scales well and is able to find close-to-optimal solutions.
Decision Tree Learning-Inspired Dynamic Variable Ordering for the Weighted CSP
Authors: Xu Hong , Sun Kexuan , Koenig Sven , Satish Kumar T. K.
Published: November 2022

The weighted constraint satisfaction problem (WCSP) is a powerful mathematical framework for combinatorial optimization. The branch and bound search paradigm is very successful in solving the WCSP but critically depends on the ordering in which variables are instantiated. In this paper, we introduce a new framework for dynamic variable ordering for solving the WCSP. This framework is inspired by regression decision tree learning. Variables are ordered dynamically based on samples of random assignments of values to variables as well as their corresponding total weights. Within this framework, we propose four variable ordering heuristics (sdr, inv-sdr, rr and inv-rr). We compare them with many other state-of-the-art dynamic variable ordering heuristics, and show that sdr and rr outperform them on many real-world and random benchmark instances.
Counting Vertex-Disjoint Shortest Paths in Graphs
Authors: Botea Adi , Mattetti Massimiliano , Kishimoto Akihiro , Marinescu Radu , Daly Elizabeth
Published: November 2022

Finding a shortest path in a graph is at the core of many combinatorial search problems. A closely related problem refers to counting the number of shortest paths between two nodes. Such problems are solvable in polynomial time in the size of the graph. However, more realistic problem formulations could additionally specify constraints to satisfy. We study the problem of counting the shortest paths that are vertex disjoint and can satisfy additional constraints. Specifically, we look at the problems of counting vertex-disjoint shortest paths in edge-colored graphs, counting vertex-disjoint shortest paths with directional constraints, and counting vertex-disjoint shortest paths between multiple source-target pairs. We give a detailed theoretical analysis, and show formally that all of these three counting problems are NP-complete in general.
A Measure of Quality for IDA* Heuristics
Authors: Clausecker Robert K. P. , Schintke Florian
Published: November 2022

We present a novel way to judge the performance of IDA* heuristics. With this measure of heuristic quality η, different heuristics for the same problem space can be compared objectively without regards to a particular problem instance. We show how η can be used to model the performance expectations of PDB heuristics. By drawing histograms of the contributions of different parts of the search space to η, we show what parts are most critical to the quality of a heuristic and contribute to the long-standing question on what h values are most critical to the performance of an IDA* heuristic.
Finding the Exact Diameter of a Graph with Partial Breadth-First Searches
Authors: Korf Richard E.
Published: November 2022

The diameter of a graph is the longest shortest path between two nodes. This paper
presents an improved algorithm for finding the exact diameter of an undirected
graph. Rather than performing complete breadth-first searches, these
searches can be terminated early. The algorithm is readily parallelized, and is
used to find the diameters of 4-peg Tower of Hanoi problem-space
graphs with up to 18 discs. Performance improvements range from a
factor of almost 2 to 5.88 over the previous state of the art.
Suboptimally Solving the Watchman Route Problem on a Grid with Heuristic Search
Authors: Yaffe Tamir , Skyler Shawn , Felner Ariel
Published: November 2022

In the Watchman Route Problem (WRP) we are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one cell on the path. WRP was recently formalized and optimally solved with heuristic search. In this paper we show how the previous optimal methods can be relaxed and modified to obtain suboptimal solvers that are much faster than the optimal solvers without sacrificing too much the quality of the solution. In particular, we present three methods that intelligently prune away large subtrees. We then derive bounded suboptimal solvers, suboptimal solvers without bounds and anytime variants of these. All these algorithms are backed up with experimental evidence that show their benefits compared to existing approaches.
Improving Continuous-Time Conflict Based Search
Authors: Andreychuk Anton , Yakovlev Konstantin , Boyarski Eli , Stern Roni
Published: November 2022

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for n agents in a graph such that each agent reaches its goal vertex and the agents do not collide with each other while moving along these paths. While different problem statements of MAPF exist, we are focused on MAPFr (Walker, Sturtevant, and Felner 2018), in which actions’ durations can be non-uniform, agents have geometric shapes, and time is continuous. Continuous-time conflict-based search (CCBS) (Andreychuk et al. 2019) is a recently proposed algorithm for finding optimal solutions to MAPFr problems. In this work, we propose several improvements to CCBS based on known improvements to the Conflictbased search (CBS) algorithm (Sharon et al. 2015) for classical MAPF, namely Disjoint Splitting (DS), Prioritizing Conflicts (PC), and high-level heuristics. We evaluate the impact of these improvements experimentally on both roadmaps and grids. Our results show that CCBS with these improvements is able to solve significantly more problems.
Adversary Strategy Sampling for Effective Plan Generation
Authors: Chrpa Lukáš , Rytíř Pavel , Horčík Rostislav , Čuhel Jan , Livochka Anastasiia , Edelkamp Stefan
Published: November 2022

Effective plan generation in adversarial environments has to take into account possible actions of adversary agents, i.e., the agent should know what the competitor will likely do.
In this paper we propose a novel approach for estimating strategies of the adversary, sampling actions that interfere with the agent's ones. The estimated competitor strategies are used in plan generation by considering that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the agent's deadlines. Missing these deadlines entails additional plan cost.
Exploiting Learned Policies and Learned Heuristics in Bounded-Suboptimal Search
Authors: Greco Matias
Published: November 2022

Machine Learning (ML) has made significant progress to perform different tasks, such as image classification, speech recognition, and natural language processing, mainly driven by deep learning. Also, ML algorithms, through learning policies or heuristics estimates, have demonstrated potential for solving deterministic problems that would usually be solved using search techniques. Nevertheless, in solving a search problem with purely learning techniques, it is not possible to deliver guarantees regarding the quality of the solution. This research explores how a learned policy or heuristic can be integrated with a bounded-suboptimal search algorithm using Focal Search, sorting the FOCAL list using the concept of discrepancies to speed up the search. On the experimental side, we train a simple neural network as a learned policy and the DeepCubeA as a learned heuristic for the 15-puzzle domain. The results show that a learned policy or heuristic can reduce, at least, one order of magnitude, the expansions than WA* with the same bound and deliver better solution quality.
Generalized Longest Path Problems
Authors: Dahan Gal , Tabib Itay , Shimony Eyal Solomon , Felner Ariel
Published: November 2022

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest.
We create a common framework of longest constrained path in a graph that contains these two problems, as well as other interesting maximum path problems, as special cases.
We analyze properties of this general framework,
produce bounds on the path length that can be used as
admissible heuristics for all problem types therein.
For the special cases of longest simple path and snakes,
these heuristics are shown to reduce the number of
expansions when searching for a maximal path, which in
some cases leads to reduced search time despite the significant overhead of computing these heuristics.
Mutex Propagation in Multi-Agent Path Finding for Large Agents
Authors: Zhang Han , Li Yutong , Li Jiaoyang , Kumar T. K. Satish , Koenig Sven
Published: November 2022

Mutex propagation and its concomitant symmetry-breaking techniques have proven useful in Multi-Agent Path Finding (MAPF) with point agents. In this paper, we show that they can be easily generalized to richer MAPF problems. In particular, we demonstrate their application to MAPF with ``Large'' Agents (LA-MAPF). Here, agents can occupy multiple points at the same time according to their fixed shapes and sizes. While existing rule-based symmetry-breaking techniques are difficult to generalize from point agents to large agents, mutex-based symmetry-breaking techniques can be generalized easily. In a Conflict-Based Search (CBS) framework for LA-MAPF, we also develop a mutex-based conflict-selection strategy to further enhance the efficiency of the search. Through experiments on various maps, we show that our techniques significantly improve MC-CBS, a state-of-the-art optimal LA-MAPF algorithm, in terms of both success rate and runtime.
A Conflict Avoidance Table for Continuous Conflict-Based Search (Extended Abstract)
Authors: Coppé Vianney , Schaus Pierre
Published: November 2022

Conflict-Based Search is a state-of-the-art algorithm solving the Multi-Agent Path Finding problem. Given multiple agents with start and goal locations, the problem is to find a set of collision-free paths of minimal cost. Continuous Conflict-Based Search is a recent adaptation of this algorithm for continuous time and agents with physical shapes. However, an important ingredient has not been adapted to this continuous version: the Conflict Avoidance Table. It is used as a tie-breaking strategy in single-agent search phases to favor paths causing fewer conflicts with the other agents. This paper explains how the R-Tree can be used as a Conflict Avoidance Table for Continuous Conflict-Based Search. The experiments show that using the Conflict Avoidance Table can reduce the number of nodes expanded by the algorithm by a large margin. As a result, the solving time is improved proportionally and especially when using the implementation based on R-Trees as opposed to a naive implementation.
IPO-MAXSAT: Combining the In-Parameter-Order Strategy for Covering Array Generation with MaxSAT Solving (Extended Abstract)
Authors: Hiess Irene , Kampel Ludwig , Wagner Michael , Simos Dimitris E.
Published: November 2022

Covering arrays (CAs) are discrete objects appearing in combinatorial design theory that find practical applications, most prominently in software testing. The generation of optimized CAs is a difficult combinatorial optimization problem being subject to ongoing research. Previous studies have shown that many different algorithmic approaches are best suited for different instances of CAs. In this extended abstract we describe the IPO-MAXSAT algorithm, which adopts the prominent IPO strategy for CA generation and uses MaxSAT solving
to optimize the occurring sub-problems.
Urban Traffic Control via Planning with Global State Constraints (Extended Abstract)
Authors: Ivankovic Franc , Vallati Mauro , Chrpa Lukáš , Roveri Marco
Published: November 2022

Planning with global state constraints is an extension of classical planning such that some properties of each state are derived via a set of rules common to all states. This approach is important for the application of planning techniques in manipulating cyber-physical systems, and has been shown to be effective in practice. Urban Traffic Control (UTC) deals with the control and management of traffic in urban regions, and includes the optimisation of traffic signals configuration to minimise traffic congestion and travel delays. In this paper, we briefly introduce how to cast the UTC problem into the formalism of planning with global state constraints, and we perform a preliminary experimental evaluation considering significant scenarios taken from the literature, and a new one based on real-world data. The results show that the approach is feasible, and the quality of generated solutions has been confirmed in simulation using existing symbolic models.
On the Reformulation of Discretised PDDL+ to Numeric Planning (Extended Abstract)
Authors: Percassi Francesco , Scala Enrico , Vallati Mauro
Published: November 2022

PDDL+ is an expressive planning formalism that enables the modelling of hybrid discrete-continuous domains. The resulting models are notoriously difficult to cope with, and few planning engines are natively supporting PDDL+. To foster the use of PDDL+, this paper revisits a set of recently proposed translations allowing to reformulate a PDDL+ task into a PDDL2.1 one. Such translations permit the use of a wider set of engines to solve complex hybrid problems.
Sparse Decision Diagrams for SAT-based Compilation of Multi-Agent Path Finding (Extended Abstract)
Authors: Surynek Pavel
Published: November 2022

Multi-agent path finding (MAPF) represents a task of finding non-colliding paths for agents via which they can navigate from their initial positions to specified goal positions. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MAPF to a different formalism for which an efficient solver exists. In this paper, we enhance the existing Boolean satisfiability-based (SAT) algorithm for MAPF via using sparse decision diagrams representing the set of candidate paths for each agent, from which the target Boolean encoding is derived, considering more promising paths before the less promising ones are taken into account. Suggested sparse diagrams lead to a smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach are kept. Specifically, considering the candidate paths sparsely instead of considering them all makes the SAT-based approach more competitive for MAPF on large maps.
Deep RRT*
Authors: Dang Xuzhe , Chrpa Lukáš , Edelkamp Stefan
Published: November 2022

Sampling-based motion planning algorithms such as Rapidly exploring Random Trees (RRTs) have been used in robotic applications for a long time. In this paper, we propose a method that combines deep learning with RRT* method. We use a neural network to learn a sample strategy for RRT*.We evaluate Deep RRT* in a collection of 2D scenarios. The results demonstrate that our algorithm could find collision-free paths efficiently and fast, and can be generalized to unseen environments.
Search-Based Path Planning with Homotopy Class Constraints
Authors: Bhattacharya Subhrajit , Kumar Vijay , Likhachev Maxim
Published: November 2022

Goal-directed path planning is one of the basic and widely studied problems in the field of mobile robotics. Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of finding least-cost paths restricted to a specific homotopy class or finding least-cost paths that do not belong to certain homotopy classes arises frequently in such applications as predicting paths for dynamic entities and computing heuristics for path planning with dynamic constraints. In the present work, we develop a compact way of representing homotopy classes and propose an efficient method of graph search-based optimal path planning with constraints on homotopy classes. The method is based on representing the environment of the robot as a complex plane and making use of the Cauchy Integral Theorem. We prove optimality of the method and show its efficiency experimentally.
SoCS 2010 Organization
Authors: Felner Ariel , Sturtevant Nathan
Published: November 2022

List of organizers, chairs, program committee, and reviewers for the SoCS 2010 International Symposium.
Heuristic Contraction Hierarchies with Approximation Guarantee
Authors: Geisberger Robert , Schieferdecker Dennis
Published: November 2022

We present a new heuristic point-to-point shortest path algorithm based on contraction hierarchies (CH). Given an epsilon >= 0, we can prove that the length of the path computed by our algorithm is at most (1 + ε) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid adding shortcuts even when a replacement path is (1+epsilon) times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.
Adaptive K-Parallel Best-First Search: A Simple but Efficient Algorithm for Multi-Core Domain-Independent Planning
Authors: Vidal Vincent , Bordeaux Lucas , Hamadi Youssef
Published: November 2022

Motivated by the recent hardware evolution towards multi-core machines, we investigate parallel planning techniques in a shared-memory environment. We consider, more specifically, parallel versions of a best-first search algorithm that run K threads, each expanding the next best node from the open list. We show that the proposed technique has a number of advantages. First, it is (reasonably) simple: we show how the algorithm can be obtained from a sequential version mostly by adding parallel annotations. Second, we conduct an extensive empirical study that shows that this approach is quite effective.  It is also dynamic in the sense that the number of nodes expanded in parallel is adapted during the search. Overall we show that the approach is promising for parallel domain-independent, suboptimal planning.
Directed Plateau Search for MAX-k-SAT
Authors: Sutton Andrew , Howe Adele , Whitley L.
Published: November 2022

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space.  This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks.  We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.
The Logic of Benchmarking: A Case Against State-of-the-Art Performance
Authors: Ruml Wheeler
Published: November 2022

This note marshals arguments for three points. First, it is better to test on small benchmark instances than to solve the largest possible ones. This eases replication and allows a more diverse set of instances to be tested. There are few conclusions that one can draw from running on large benchmarks that can't also be drawn from running on small benchmarks. Second, experimental evaluation should focus on understanding algorithm behavior and forming predictive models, rather than on achieving state-of-the-art performance on toy problems. Third, it is more important to develop search techniques that are robust across multiple domains than ones that only give state-of-the-art performance in a single domain. Robust techniques are more likely be useful to others.
A Novel Technique for Compressing Pattern Databases in the Pancake Sorting Problems
Authors: Keshtkaran Morteza , Taghizadeh Roohollah , Ziarati Koorush
Published: November 2022

In this paper we present a lossless technique to compress pattern databases (PDBs) in the Pancake Sorting problems. This compression technique together with the choice of zero-cost operators in the construction of additive PDBs reduces the memory requirement for PDBs in these problems to a great extent, thus making otherwise intractable problems able to be efficiently handled. Also, using this method, we can construct some problem-size independent PDBs. This precludes the necessity of constructing new PDBs for new problems with different numbers of pancakes. In addition to our compression technique, by maximizing over the heuristic value of additive PDBs and the modified version of the gap heuristic, we have obtained powerful heuristics for the burnt pancake problem.
Faster Optimal and Suboptimal Hierarchical Search
Authors: Leighton Michael , Ruml Wheeler , Holte Robert
Published: November 2022

In problem domains for which an informed admissible heuristic function is not available, one attractive approach is hierarchical search. Hierarchical search uses search in an abstracted version of the problem to dynamically generate heuristic values. This paper makes two contributions to hierarchical search. First, we propose a simple modification to the state-of-the-art algorithm Switchback that reduces the number of expansions (and hence the running time) by approximately half, while maintaining its guarantee of optimality. Second, we propose a new algorithm for suboptimal hierarchical search, called Switch. Empirical results suggest that Switch yields faster search than straightforward modifications of Switchback, such as weighting the heuristic or greedy search. The success of Switch illustrates the potential for further research on specifically suboptimal hierarchical search.
Planning in Domains with Cost Function Dependent Actions
Authors: Phillips Mike , Likhachev Maxim
Published: November 2022

In a number of graph search-based planning problems, the value of the cost function that is being minimized also affects the set of possible actions at some or all the states in the graph. In such planning problems, the cost function typically becomes one of the state variables thereby increasing the dimensionality of the planning problem, and consequently the size of the graph that represents the problem. In this paper, we show how to avoid this increase in the dimensionality for weighted search (with bounded suboptimality) whenever the availability of the actions is monotonically non-increasing with the increase in the cost function.
Distance Learning in Agent-Centered Heuristic Search
Authors: Sturtevant Nathan
Published: November 2022

Real-time agent-centric algorithms have been used for learning and solving problems since the introduction of the LRTA* algorithm in 1990. In this time period, numerous variants have been produced, however, they have generally followed the same approach in varying parameters to learn a heuristic which estimates the remaining cost to arrive at a goal state. This short paper discusses the history and implications of learning g-costs, both alone and in conjunction with learning h-costs as an introduction to the new f-LRTA* algorithm which learns both.