bluuebunny/crossref_metadata_2025 huggingface dataset:
Lightweight Contextual Ranking of City Pictures: Urban Sociology to the Rescue
Authors: Zambaldi Vinícius , Pesce Joao , Quercia Daniele , Almeida Virgilio
Published: November 2022

To increase mobile user engagement, photo sharing sites are trying to identify interesting and memorable pictures. Past proposals for identifying such pictures have relied on either metadata (e.g., likes) or visual features. In practice, techniques based on  those two inputs  do not always work: metadata is sparse (only few pictures have considerable number of likes), and extracting visual features is computationally expensive. In mobile solutions,  geo-referenced content becomes increasingly important. The premise behind this work is that pictures of a neighborhood is linked to the way the neighborhood is perceived by people: whether it is, for instance, distinctive and beautiful or not.  Since 1970s, urban theories proposed by Lynch, Milgram and Peterson aimed at systematically capturing the way people perceive neighborhoods. Here we tested whether those theories could be put to use for automatically identifying appealing city pictures.  We did so by gathering geo-referenced Flickr pictures in the city of London; selecting six urban qualities associated with those urban theories; computing proxies for those qualities from online social media data; and ranking Flickr pictures based on those proxies. We find that our proposal enjoys three main desirable properties: it is effective, scalable, and aware of contextual changes such as  time of day and weather condition. All this suggests new promising research directions for multi-modal learning approaches that automatically identify appealing city pictures.
Topical Engagement on Twitter: Using Consistency of Activity as a Means of User Segmentation
Authors: Schmidt Aurora , Fink Clay , Bos Nathan
Published: November 2022

In this paper we introduce a measure for the consistency of Twitter user behavior as a way of measuring engagement with a topic. Using this measure of topical engagement, we filter tweets collected from over 90,000 Nigerian users over a three-year period concerning that country’s head of state, President Goodluck Jonathan. We show that this measure effectively identifies a small set of highly engaged users that produce a disproportionate amount of activity, both in tweet volume and mentions of other users. Additionally, we show preferential within-group activity, with these users disproportionately mentioning other highly engaged users. Lastly, we show the potential of using changes in the percentage of engaged users within the overall user set for gauging the significance of events that occurred in Nigeria over the 2011 to early 2013 period.
YouRank: Let User Engagement Rank Microblog Search Results
Authors: Wang Wenbo , Duan Lei , Koul Anirudh , Sheth Amit
Published: November 2022

We propose an approach for ranking microblog search results. The basic idea is to leverage user engagement for the purpose of ranking: if a microblog post received many retweets/replies, this means users find it important and it should be ranked higher. However, simply applying the raw count of engagement may bias the ranking by favoring posts from celebrity users whose posts generally receive a disproportionate amount of engagement regardless of the contents of posts. To reduce this bias, we propose a variety of time window-based outlier features that transfer the raw engagement count into an importance score, on a per user basis. The evaluation on five real-world datasets confirms that the proposed approach can be used to improve microblog search.
Understanding Public Emotional Reactions on Twitter
Authors: Wan Stephen , Paris Cecile
Published: November 2022

Social media has become an important communication medium for people to express their feelings and opinions, sometimes on a daily basis.  We demonstrate a system that helps monitor and understand how people feel about specific topics or events. Using a large vocabulary of emotion words constructed from a number of public domain resources and mapping them to an emotion hierarchy, our system is able to analyse incoming posts gathered on a topic of interest and visualise the emotional pulse of a geographical region as it reacts to that event.  The content analysis component of the tool then enables users to gain insights into the mood variations exhibited. We illustrate the system by exploring the public reaction to a specific recent event: the Sydney siege tragedy on December 15th, 2014.
Leveraging Product Adopter Information from Online Reviews for Product Recommendation
Authors: Wang Jinpeng , Zhao Wayne , He Yulan , Li Xiaoming
Published: November 2022

The availability of the sheer volume of online product reviews makes it possible to derive implicit demographic information of product adopters from review documents. This paper proposes a novel approach to the extraction of product adopter mentions from online reviews. The extracted product adopters are then categorise into a number of different demographic user groups. The aggregated demographic information of many product adopters can be used to characterise both products and users, which can be incorporated into a recommendation method using weighted regularised matrix factorisation. Our experimental results on over 15 million reviews crawled from JINGDONG, the largest B2C e-commerce website in China, show the feasibility and effectiveness of our proposed framework for product recommendation.
WhichStreams: A Dynamic Approach for Focused Data Capture from Large Social Media
Authors: Gisselbrecht Thibault , Denoyer Ludovic , Gallinari Patrick , Lamprier Sylvain
Published: November 2022

Due to the huge amount of data produced on large social media, capturing useful content usually implies to focus on subsets of data that fit with a pre-specified need. Considering the usual API restrictions of these media, we formulate this task of focused capture as a dynamic data sources selection problem. We then propose a machine learning methodology, named WhichStreams, which is based on an extension of a recently proposed combinatorial bandit algorithm. The evaluation of our approach on various Twitter datasets, with both offline and online settings, demonstrates the relevance of the proposal for leveraging the real-time data streaming APIs offered by most of the main social media.
Analyzing and Modeling Special Offer Campaigns in Location-Based Social Networks
Authors: Zhang Ke , Pelechrinis Konstantinos , Lappas Theodoros
Published: November 2022

The proliferation of mobile handheld devices in combination with the technological advancements in mobile computing has led to a number of innovative services that make use of the location information available on such devices. Traditional yellow pages websites have now moved to mobile platforms, giving the opportunity to local businesses and potential, near-by, customers to connect. These platforms can offer an affordable advertisement channel to local businesses. One of the mechanisms offered by location-based social networks (LBSNs) allows businesses to provide special offers to their customers that connect through the platform. We collect a large time-series dataset from approximately 14 million venues on Foursquare and analyze the performance of such campaigns using randomization techniquesand (non-parametric) hypothesis testing with statistical bootstrapping. Our main finding indicates that this type of promotions are not as effective as anecdote success stories might suggest. Finally, we design classifiers by extracting three different types of features that are able to provide an educated decision on whether a special offer campaign for a local business will succeed or not both in short and long term.
User Effort and Network Structure Mediate Access to Information in Networks
Authors: Kang Jeon-Hyung , Lerman Kristina
Published: November 2022

Individuals' access to information in a social network depends on its distributed and where in the network individuals position themselves. However, individuals have limited capacity to manage their social connections and process information. In this work, we study how this limited capacity and network structure interact to affect the diversity of information social media users receive. Previous studies of the role of networks in information access were limited in their ability to measure the diversity of information. We address this problem by learning the topics of interest to social media users by observing messages they share online with their followers. We present a probabilistic model that incorporates human cognitive constraints in a generative model of information sharing. We then use the topics learned by the model to measure the diversity of information users receive from their social media contacts.We confirm that users in structurally diverse network positions, which bridge otherwise disconnected regions of the follower graph, are exposed to more diverse information. In addition, we identify user effort as an important variable that mediates access to diverse information in social media.Users who invest more effort into their activity on the site not only place themselves in more structurally diverse positions within the network than the less engaged users, but they also receive more diverse information when located in similar network positions.These findings indicate that the relationship between network structure and access to information in networks is more nuanced than previously thought.
Analysis and Prediction of Question Topic Popularity in Community Q&A Sites: A Case Study of Quora
Authors: Maity Suman , Singh Sahni Jot Sarup , Mukherjee Animesh
Published: November 2022

In the past few years, Quora a community-driven social platform for question and answering, has grown exponentially from a small community of users into one of the largest and reliable source of Q&A on the Internet. Quora has a built-in social structure integrated to its backbone; users can follow each other, follow question, topics etc. Apart from the social connections that Quora provides, it has developed a knowledge base nicely organized via hierarchy and relatedness of topics. In this paper, we consider a massive dataset of more than four years and analyze the dynamics of topical growth over time; how various factors affect the popularity of a topic or its acceptance in Q&A community. We also propose a regression model to predict the popularity of the topics and discuss the important discriminating features. We achieve a high prediction accuracy (correlation coefficient ~0.773) with low root mean square error (~1.065). We further categorize thetopics into a few broad classes by implementing a simple Latent Dirichlet Allocation (LDA) model on the question texts associated with the topics. In comparison to the data sample with no categorization, this stratification of the topics enhances the prediction accuracies for several categories. However, for certain categories there seems to a slight decrease in the accuracy values and we present an in-depth discussion analyzing the cause for the same pointing out potential ways for improvement. We believe that this thorough measurement study will have a direct application to a service like recommending trending topics in Quora.
An Image Is Worth More than a Thousand Favorites: Surfacing the Hidden Beauty of Flickr Pictures
Authors: Schifanella Rossano , Redi Miriam , Aiello Luca Maria
Published: November 2022

The dynamics of attention in social media tend to obey power laws. Attention concentrates on a relatively small number of popular items and neglecting the vast majority of content produced by the crowd. Although popularity can be an indication of the perceived value of an item within its community, previous research has hinted to the fact that popularity is distinct from intrinsic quality. As a result, content with low visibility but high quality lurks in the tail of the popularity distribution. This phenomenon can be particularly evident in the case of photo-sharing communities, where valuable photographers who are not highly engaged in online social interactions contribute with high-quality pictures that remain unseen. We propose to use a computer vision method to surface beautiful pictures from the immense pool of near-zero-popularity items, and we test it on a large dataset of creative-commons photos on Flickr. By gathering a large crowdsourced ground truth of aesthetics scores for Flickr images, we show that our method retrieves photos whose median perceived beauty score is equal to the most popular ones, and whose average is lower by only 1.5%.
Crowds, Gigs, and Super Sellers: A Measurement Study of a Supply-Driven Crowdsourcing Marketplace
Authors: Ge Hancheng , Caverlee James , Lee Kyumin
Published: November 2022

The crowdsourcing movement has spawned a host of successful efforts that organize large numbers of globally-distributed participants to tackle a range of tasks. While many demand-driven crowd marketplaces have emerged (like Amazon Mechanical Turk, often resulting in workers that are essentially replace-able), we are witnessing the rise of supply-driven marketplaces where specialized workers offer their expertise. In this paper, we present a comprehensive data-driven measurement study of one prominent supply-driven marketplace -- Fiverr -- wherein we investigate the sellers and their offerings (called "gigs"). As part of this investigation, we identify the key features distinguishing "super sellers" from regular participants and develop a machine learning based approach for inferring the quality of gigs, which is especially important for the vast majority of gigs with little feedback.
Predicting Privacy Behavior on Online Social Networks
Authors: Dong Cailing , Jin Hongxia , Knijnenburg Bart
Published: November 2022

Online Social Networks (OSNs) have come to play an increasingly important role in our social lives, and their inherent privacy problems have become a major concern for users. Can we assist consumers in their privacy decision-making practices, for example by predicting their preferences and giving them personalized advice? In order to accomplish this, we would need to study the factors that affect users’ privacy decision-making practices. In this paper, we intend to comprehensively investigate these factors in light of two common OSN scenarios: the case where other users request access to the user’s information, and the case where the user shares this information voluntarily. Using a real-life dataset from Google+ and three location-sharing datasets, we identify behavioral analogs to psychological variables that are known to affect users’ disclosure behavior: the trustworthiness of the requester/information audience, the sharing tendency of the receiver/information holder, the sensitivity of the requested/shared information, the appropriateness of the request/sharing activity, as well as some contextual information. We also explore how these factors work to affect the privacy decision making. Based on these factors we build a privacy decisionmaking prediction model that can be used to give users personalized advice regarding their privacy decisionmaking practices.
Patterns in Interactive Tagging Networks
Authors: Yamaguchi Yuto , Yoshida Mitsuo , Faloutsos Christos , Kitagawa Hiroyuki
Published: November 2022

How do users behave if they can tag each other in social networks?In this paper, we answer this question by studying the interactive tagging network constructed by Twitter lists. Twitter lists can be regarded as the tagging process; a user (i.e., tagger) creates a list with a name (i.e., tag) and adds other users (i.e., tagged users) into the list. This tagging network is by nature different from the resource tagging networks (e.g., Flickr and Delicious) because users on this network can tag each other. We address the following research questions: (RQ1) What is the common patterns and the difference between the interactive tagging network and the resource tagging networks? (RQ2) Do users tag each other on the interactive tagging network? And if so, to what extent? (RQ3) What is the difference between the two types of relationships on Twitter: who-tags-whom and who-follows-whom? By quantitatively studying million-scale networks, we found the pervasive patterns across the different tagging networks, and the interactive patterns within the interactive tagging network. This study sheds light on the underlying characteristics of the interactive tagging network, which is relevant to the social scientists and the system designers of the tagging systems.
Voting Behaviour and Power in Online Democracy: A Study of LiquidFeedback in Germany's Pirate Party
Authors: Kling Christoph , Kunegis Jérôme , Hartmann Heinrich , Strohmaier Markus , Staab Steffen
Published: November 2022

In recent years, political parties have adopted Online Delegative Democracy platforms such as LiquidFeedback to organise themselves and their political agendas via a grassroots approach. A common objection against the use of these platforms is the delegation system, where a user can delegate his vote to another user, giving rise to so-called super-voters, i.e. powerful users who receive many delegations. It has been asserted in the past that the presence of these super-voters undermines the democratic process, and therefore delegative democracy should be avoided. In this paper, we look at the emergence of super-voters in the largest delegative online democracy platform worldwide, operated by Germany’s Pirate Party. We investigate the distribution of power within the party systematically, study whether super-voters exist, and explore the influence they have on the outcome of votings conducted online. While we find that the theoretical power of super-voters is indeed high, we also observe that they use their power wisely. Super-voters do not fully act on their power to change the outcome of votes, but they vote in favour of proposals with the majority of voters in many cases thereby exhibiting a stabilising effect on the system. We use these findings to present a novel class of power indices that considers observed voting biases and gives significantly better predictions than state-of-the-art measures.
Taxonomy-Based Discovery and Annotation of Functional Areas in the City
Authors: Vaca Carmen , Quercia Daniele , Bonchi Francesco , Fraternali Piero
Published: November 2022

Mapping the functional use of city areas (e.g., mapping clusters of hotels or of electronic shops) enables a variety of applications (e.g., innovative way-finding tools). To do that mapping, researchers have recently processed geo-referenced data with spatial clustering algorithms. These algorithms usually perform two consecutive steps: they cluster nearby points on the map, and then assign labels (e.g., 'electronics') to the resulting clusters. When applied in the city context, these algorithms do not fully work, not least because they consider the two steps of clustering and labeling as separate. Since there is no reason to keep those two steps separate, we propose a framework that clusters points based not only on their density but also on their semantic relatedness. We evaluate this framework upon Foursquare data in the cities of Barcelona, Milan, and London. We find that it is more effective than the baseline method of DBSCAN in discovering functional areas. We complement that quantitative evaluation with a user study involving 111 participants in the three cities. Finally, to illustrate the generalizability of our framework, we process temporal data with it and successfully discover seasonal uses of the city.
On the Users’ Efficiency in the Twitter Information Network
Authors: Babaei Mahmoudreza , Grabowicz Przemyslaw , Valera Isabel , Gomez-Rodriguez Manuel
Published: November 2022

Social media systems have increasingly become digital information marketplaces, where users produce, consume and share information and ideas, often of public interest. In this context, social media users are their own curators of information — however, they can only select their information sources, who they follow, but cannot choose the information they are exposed to, which content they receive. A natural question is thus to assess how efficient are users at selecting their information sources. In this work, we model social media users as information processing systems whose goal is acquiring a set of (unique) pieces of information. We then define a computational framework, based on minimal set covers, that allows us both to evaluate every user's performance as information curators within the system. Our framework is general and applicable to any social media system where every user follows others within the system to receive the information they produce. We leverage our framework to investigate the efficiency of Twitter users at acquiring information. We find that user's efficiency typically decreases with respect to the number of people she follows. A more efficient user tends to be less overloaded and, as a consequence, any particular piece of information lives longer in the top of her timeline, thus facilitating her to actually read the information. Finally, while most unique information a user receives could have been acquired through a few users, less popular information requires following many different users.
Assessing the Structural Correlates between Friendship Networks and Conversational Agency in Facebook Groups
Authors: Polonski Vyacheslav , Hogan Bernie
Published: November 2022

To what extent do friendship ties influence the conversation structure in open groups? Openly accessible Facebook groups offer the opportunity to examine how individuals leverage their existing friendship relations when speaking to a large and often heterogeneous audience. For example, those with many friends in the group may receive more positive signals from others and also may have their content validated more easily. Thus, while the group is ostensibly open to all, existing relationships may impede such openness on a practical level. We employ a stratified sample of 30 Facebook groups from UK Russell Group universities. Using multilevel regression, we examine the effects of several structural metrics at both the actor and group level on the magnitude of three conversational metrics: likelihood of initiating a conversation, responding to a conversation and receiving responses for content. We find that aspects of individual network positions, e.g. degree-centrality and eigenvector-centrality, as well as qualities of the group e.g. group-density and modularity, have a consistent and highly significant effect on conversational metrics, while the strength of these relationships clearly varies by group type. We contextualise our findings via Gibson’s notion of “conversational agency”, and point to future directions for designing and managing online communities.
Let's Talk about Talks: Supporting Knowledge Exchange Processes on Wiki Discussion Pages
Authors: Heimbuch Sven , Bodemer Daniel
Published: November 2022

Complex knowledge exchange processes in collaborative knowledge building settings within Wikis can be either supported by providing guidance in form of cognitive group awareness information or by explicitly guiding learners with the help of collaboration scripts. Potentials of analysing and supporting discussants' knowledge building processes focussed on the level of talk pages have still been rarely researched. Our research project comprises a series of three experimental studies and one qualitative study to determine which kind of support is most beneficial for varying types of learners working with Wikis. For this research different fields of computer-supported collaborative learning are integrated and both quantitative and qualitative methods are applied to provide comprehensive analyses in order to provide opportunities for other related research. Presenting and discussing aspects of our research and first results could be beneficial for future research. Our findings suggest that Wiki talk page users can benefit from additional structuring aids.
A Guide to Budgeted Tree Search
Authors: Sturtevant Nathan , Helmert Malte
Published: November 2022

Budgeted Tree Search (BTS), a variant of Iterative Budgeted Exponential Search, is a new algorithm that has the same performance as IDA* on problems where the state space grows exponentially, but has far better performance than IDA* in other cases where IDA* fails. The goal of this paper is to provide a detailed guide to BTS with worked examples to make the algorithm more accessible to practitioners in heuristic search.
Generalizing Multi-Agent Path Finding for Heterogeneous Agents
Authors: Atzmon Dor , Zax Yonathan , Kivity Einat , Avitan Lidor , Morag Jonathan , Felner Ariel
Published: November 2022

Multi-Agent Path Finding (MAPF) is the problem of finding non-colliding paths for multiple agents. The classical problem assumes that all agents are homogeneous, with a fixed size and behavior. However, in reality agents are heterogeneous, with different sizes and behaviors. In this paper, we generalize MAPF to G-MAPF for the case of heterogeneous agents. We then show how two previous settings of large agents and k-robust agents are special cases of G-MAPF. Finally, we introduce G-CBS, a variant of the Conflict-Based Search (CBS) algorithm for G-MAPF, which does not cause significant extra overhead.
Generalized Conflict-Directed Search for Optimal Ordering Problems
Authors: Chen Jingkai , Zhang Yuening , Fang Cheng , Williams Brian C.
Published: November 2022

Solving planning and scheduling problems for multiple tasks with highly coupled state and temporal constraints is notoriously challenging. An appealing approach to effectively decouple the problem is to judiciously order the events such that decisions can be made over sequences of tasks. As many problems encountered in practice are over-constrained, we must instead find relaxed solutions in which certain requirements are dropped. This motivates a formulation of optimality with respect to the costs of relaxing constraints and the problem of finding an optimal ordering under which this relaxing cost is minimum. In this paper, we present Generalized Conflict-directed Ordering (GCDO), a branch-and-bound ordering method that generates an optimal total order of events by leveraging the generalized conflicts of both inconsistency and suboptimality from sub-solvers for cost estimation and solution space pruning. Due to its ability to reason over generalized conflicts, GCDO is much more efficient in finding high-quality total orders than the previous conflict-directed approach CDITO. We demonstrate this by benchmarking on temporal network configuration problems, which involves managing networks over time and makes necessary tradeoffs between network flows against CDITO and Mixed Integer-Linear Programing (MILP). Our algorithm is able to solve two orders of magnitude more benchmark problems to optimality and twice the problems compared to CDITO and MILP within a runtime limit, respectively.
SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems
Authors: Oren Joel , Ross Chana , Lefarov Maksym , Richter Felix , Taitler Ayal , Feldman Zohar , Di Castro Dotan , Daniel Christian
Published: November 2022

We study combinatorial problems with real world applications such as machine scheduling, routing, and assignment. We propose a method that combines Reinforcement Learning (RL) and planning. This method can equally be applied to both the offline, as well as online, variants of the combinatorial problem, in which the problem components (e.g., jobs in scheduling problems) are not known in advance, but rather arrive during the decision-making process. Our solution is quite generic, scalable, and leverages distributional knowledge of the problem parameters.
We frame the solution process as an MDP, and take a Deep Q-Learning approach wherein states are represented as graphs, thereby allowing our trained policies to deal with arbitrary changes in a principled manner.
Though learned policies work well in expectation, small deviations can have substantial negative effects in combinatorial settings. We mitigate these drawbacks by employing our graph-convolutional policies as non-optimal heuristics in a compatible search algorithm, Monte Carlo Tree Search, to significantly improve overall performance. We demonstrate our method on two problems: Machine Scheduling and Capacitated Vehicle Routing. We show that our method outperforms custom-tailored mathematical solvers, state of the art learning-based algorithms, and common heuristics, both in computation time and performance.
From Classical to Colored Multi-Agent Path Finding
Authors: Barták Roman , Ivanová Marika , Švancara Jiří
Published: November 2022

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents moving in a shared environment, while each agent has specified its own destination. Colored MAPF generalizes MAPF by defining groups of agents that share a set of destination locations. In the paper, we evaluate several approaches to optimally solve colored MAPF problem, namely, a method based on network flows, an extended version of conflict-based search, and two models using Boolean satisfiability. We also investigate methods for obtaining lower bounds on optimal solutions based on constraint and continuous relaxation techniques.
Solving Sokoban with Forward-Backward Reinforcement Learning
Authors: Shoham Yaron , Elidan Gal
Published: November 2022

Despite seminal advances in reinforcement learning in recent years, many domains where the rewards are sparse, e.g. given only at task completion, remain quite challenging. In such cases, it can be beneficial to tackle the task both from its beginning and end, and make the two ends meet. Existing approaches that do so, however, are not effective in the common scenario where the strategy needed near the end goal is very different from the one that is effective earlier on.

In this work we propose a novel RL approach for such settings. In short, we first train a backward-looking agent with a simple relaxed goal, and then augment the state representation of the forward-looking agent with straightforward hint features. This allows the learned forward agent to leverage information from backward plans, without mimicking their policy.

We demonstrate the efficacy of our approach on the challenging game of Sokoban, where we substantially surpass learned solvers that generalize across levels, and are competitive with SOTA performance of the best highly-crafted systems. Impressively, we achieve these results while learning from a small number of practice levels and using simple RL techniques.
A Hierarchical Approach to Multi-Agent Path Finding
Authors: Zhang Han , Yao Mingze , Liu Ziang , Li Jiaoyang , Terr Lucas , Chan Shao-Hung , Kumar T. K. Satish , Koenig Sven
Published: November 2022

Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.
Avoiding Monochromatic Rectangles Using Shift Patterns
Authors: Liu Zhenjun , Chew Leroy , Heule Marijn J. H.
Published: November 2022

We show that enforcing shift patterns significantly reduces the cost to construct grids without monochromatic rectangles. Additionally, we prove that all valid 3-colorings of a 10 by 10 grid are isomorphic.
Landmark Heuristics for Lifted Planning - Extended Abstract
Authors: Wichlacz Julia , Höller Daniel , Hoffmann Jörg
Published: November 2022

Planning problems are usually modeled using lifted representations, they specify predicates and action schemas using variables over a finite universe of objects. However, current planning systems like Fast Downward need a grounded (propositional) input model. The process of grounding might result in an exponential blowup of the model size. This limits the application of grounded planning systems in practical applications. Recent work introduced an efficient planning system for lifted heuristic search, but the work on lifted heuristics is still limited. In this extended abstract, we introduce a novel lifted heuristic based on landmarks, which we extract from the lifted problem representation. Preliminary results on a benchmark set specialized to lifted planning show that there are domains where our approach finds enough landmarks to guide the search more effective than the heuristics available.
A Memory-Bounded Best-First Beam Search and Its Application to Scheduling Halide Programs
Authors: Gao Chao , Chen Jingwei , Mo Tong , Sajed Tanvir , Jui Shangling , Qin Min , Gong Laiyuan , Lu Wei
Published: November 2022

Beam search is a popular algorithm for solving real-world problems --- especially where search space is an enormously large tree but real-time solutions are most preferred.
We present a memory-bounded best-first beam search (MB2FBS), which can be viewed as an improved and generalized version of standard beam search in trees.
The algorithm takes three parameters --- in contrast to the singular parameter beam size in standard beam search.
We discuss how to recover standard beam search and how to realize other search behavior by setting these three parameters correspondingly. In particular, we show that the principal version of MB2FBS can be thought as an algorithm whose search expense is similar or upper bounded by beam search of certain beam size; however it often finds better solutions as it decides the number of nodes to be searched each depth dynamically with respect cost landscape.
We apply our algorithm for tensor program auto-scheduling in Halide, an important industrial problem that uses tree search for optimizing tensor program executions.
We show that the principal variants of MB2FBS deliver better empirical results than the highly optimized beam search counterpart. Most importantly, it finds superior schedules while no more computation cost is used for search, which is highly desirable for real-time program compilation and optimization.
Meeting at the Border of Two Separate Domains
Authors: Tabacaru Alexandru Paul , Atzmon Dor , Felner Ariel
Published: November 2022

To transmit information or transfer an object, two agents may need to reach the same location and meet. Often, such two agents operate in two separate environments and they can only meet at border locations. For example, a ship, sailing in the sea, needs to meet a truck traveling on land. These two agents are able to meet only at the shoreline. We call this problem the Meeting at the Border problem (MATB). In MATB, the optimal meeting location at the border is required, where the cost of a meeting location is the sum of the two shortest paths to that location. We show how to optimally solve MATB with heuristic search and suggest a novel heuristic function that estimates the cost of meeting at the border. Indeed, our new heuristic significantly enhances search algorithms in 2D and 3D domains.
Local Motif Clustering via (Hyper)Graph Partitioning
Authors: Chhabra Adil , Fonseca Faraj Marcelo , Schulz Christian
Published: November 2022

Local clustering consists of finding a good cluster around a seed node in a graph. Recently local motif clustering has been proposed: it is a local clustering approach based on motifs rather than edges. Since this approach is recent, most algorithms to solve it are extensions of statistical and numerical methods previously used for local clustering, while combinatorial approaches are still few and simple. In this work, we build a (hyper)graph to represent the motif-distribution around the seed node. We solve this model using sophisticated (hyper)graph partitioners. On average, our algorithm computes clusters six times faster and three times better than the state-of-the-art for the triangle motif.
An Online Approach for Multi-Agent Path Finding Under Movement Uncertainty (Extended Abstract)
Authors: Levy Elad , Shani Guy , Stern Roni
Published: November 2022

In this work, we address the problem of finding paths for multiple agents while avoiding collisions between them, where agents' actions have stochastic outcomes.
The objective is to create a joint policy for all agents that minimize the expected sum of costs of getting all agents to their goals, while guaranteeing that collisions never occur.
Unlike previous work on multi-agent pathfinding (MAPF), the stochastic outcomes are not limited to delays, and thus the set of locations each agent may end up at can be very large.
Consequently, offline planning is prohibitively expensive since collisions between agents may occur in many locations and time steps, while avoiding them is a hard constraint.
Instead, we propose a suboptimal online approach in which each agent follows its individually-optimal policy until it detected potential collisions in the future. Then, the potentially conflicting agents create a joint policy for resolving the potential collision.
We evaluated this policy experimentally on existing an MAPF benchmark, modified to include stochasticity. The results show that we are able to find high quality solutions for non-trivial grids with up to 12 agents, significantly surpassing several baseline approaches.
Multi-agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way? (Extended Abstract)
Authors: Švancara Jiří , Obermeier Philipp , Husár Matej , Barták Roman , Schaub Torsten
Published: November 2022

This paper extends a study on improving the performance of reduction-based solvers for the problem of multi-agent pathfinding. The task is to navigate a set of agents in a graph without collisions. Solvers that reduce this problem to other formalisms often have issues scaling to larger instances in terms of the graph size. A previous study suggests that pruning the graph of most vertices based on a randomly chosen shortest path for each agent. In this paper, we study the effect of different choices of these paths.
Additive Heuristic for Four-Connected Gridworlds
Authors: Anderson Kenneth
Published: November 2022

Memory-based heuristic techniques have been used to effectively reduce search times in implicit graphs. Recently, these techniques have been applied to improving search times in explicit graphs. This paper presents a new memory-based, additive heuristic that can be used on a type of explicit graph: the four-connected gridworld. The heuristic reduces the number of expanded nodes by up to five times, reduces execution time by up to 29 times, and can efficiently accommodate graph changes.
Searching for a k-Clique in Unknown Graphs
Authors: Stern Roni , Kalech Meir , Felner Ariel
Published: November 2022

Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowledge of edge probabilities to reduce the required exploration cost. We demonstrate the efficiency of the proposed approaches on simulated random and scale free graphs as well as on real online web crawls.
Landmark Heuristics for the Pancake Problem
Authors: Helmert Malte
Published: November 2022

We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.
A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding
Authors: Khorshid Mokhtar , Holte Robert , Sturtevant Nathan
Published: November 2022

Multi-agent pathfinding, where multiple agents must travel to their goal locations without getting stuck, has been studied in both theoretical and practical contexts, with a variety of both optimal and sub-optimal algorithms proposed for solving problems. Recent work has shown that there is a linear-time check for whether a multi-agent pathfinding problem can be solved in a tree, however this was not used to actually produce solutions. In this paper we provide a constructive proof of how to solve multi-agent pathfinding problems in a tree that culminates in a novel approach that we call the tree-based agent swapping strategy (TASS). Experimental results showed that TASS can find solutions to the multi-agent pathfinding problem on a highly crowded tree with 1000 nodes and 996 agents in less than 8 seconds. These results are far more efficient and general than existing work, suggesting that TASS is a productive line of study for multi-agent pathfinding.
Efficient and Complete Centralized Multi-Robot Path Planning
Authors: Luna Ryan , Bekris Kostas
Published: November 2022

Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This work proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. The algorithm employs two primitives: a "push" operation where a robot moves toward its goal until no further progress can be made, and a "swap" operation that allows two robots to swap positions without altering the configuration of any other robot. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique has highly competitive computation time and easily scales to problems involving 100s of robots, solving them in under 5 seconds.
Invited Speakers
Authors: Cazenave Tristan , Edelkamp Stefan
Published: November 2022

Abstracts of the invited talks presented at the Fifth Annual Symposium on Combinatorial Search held in 2012.
Are We There Yet? — Estimating Search Progress
Authors: Thayer Jordan , Stern Roni , Lelis Levi
Published: November 2022

Heuristic search is a general problem solving technique. While most evaluations of heuristic search focus on the speed of search, there are relatively few techniques for predicting when search will end. This paper provides a study of progress estimating techniques for optimal, suboptimal, and bounded suboptimal heuristic search algorithms. We examine two previously proposed techniques, search velocity and search vacillation, as well as two new approaches, path-based estimation and distribution-based estimation. We find that both new approaches are better at estimating the remaining amount of search effort than previous work in all three varieties of search, occasionally erring by less than 5%.
A Theoretical Framework for Studying Random Walk Planning
Authors: Nakhost Hootan , Mueller Martin
Published: November 2022

Random walks are a relatively new component used in several state of the art satisficing planners. Empirical results have been mixed: while the approach clearly outperforms more systematic search methods such as weighted A* on many planning domains, it fails in many others. So far, the explanations for these empirical results have been somewhat ad hoc. This paper proposes a formal framework for comparing the performance of random walk and systematic search methods. Fair homogenous graphs are proposed as a graph class that represents characteristics of the state space of prototypical planning domains, and is simple enough to allow a theoretical analysis of the performance of both random walk and systematic search algorithms. This gives well-founded insights into the relative strength and weaknesses of these approaches. The close relation of the models to some well-known planning domains is shown through simplified but semi-realistic planning domains that fulfill the constraints of the models. One main result is that in contrast to systematic search methods, for which the branching factor plays a decisive role, the performance of random walk methods is determined to a large degree by the Regress Factor, the ratio between the probabilities of progressing towards and regressing away from a goal with an action. The performance of random walk and systematic search methods can be compared by considering both branching and regress factors of a state space.
Fast, Optimal Pathfinding with Compressed Path Databases
Authors: Botea Adi
Published: November 2022

Most existing pathfinding methods are based on runtime search. Despite an impressive progress achieved in recent years, search-based methods could explore, in bad cases, large portions of a map, leading to an increased running time. We take a significantly different approach from search-based methods. Given a map, our program precomputes all-pairs shortest paths (APSP) information. APSP data are compressed, reducing the size dramatically with no information loss. We call the resulting data a compressed path database (CPD). At runtime, optimal moves are retrieved one by one until a complete (or partial, if desired) optimal path is retrieved. CPDs lead to a fast path computation, eliminating the need for runtime search. The first move lag is very low, as each move is retrieved independently from subsequent moves. The price to pay includes a significant preprocessing time and memory to build and store a CPD.
On Improving Plan Quality via Local Enhancements
Authors: Balyo Tomas , Bartak Roman , Surynek Pavel
Published: November 2022

There exist planning algorithms that can quickly find sub-optimal plans even for large problems and planning algorithms finding optimal plans but only for smaller problems. We attempt to integrate both approaches. We present an anytime technique for improving plan quality (decreasing the plan makespan) via substituting parts of the plan by better sub-plans. The technique guarantees optimality though it is primarily intended to quickly improve plan quality. We experimentally compare various approaches to local improvements.
Invited Speakers
Authors: Beck J. , Cooperman Gene
Published: November 2022

Abstracts of the invited speaker talks Modeling, Global Constraints, and Decomposition by J. Christopher Beck and Applications of Graph Search in Group Theory and Proteomics by Gene Cooperman, presented that the 2013 SoCS Symposium.
Constrained Symbolic Search: On Mutexes, BDD Minimization and More
Authors: Torralba Álvaro , Alcázar Vidal
Published: November 2022

Symbolic search allows saving large amounts of memory compared to regular explicit-state search algorithms. This is crucial in optimal settings, in which common search algorithms often exhaust the available memory. So far, the most successful uses of symbolic search have been bidirectional blind search and the generation of abstraction heuristics like Pattern Databases. Despite its usefulness, several common techniques in explicit-state search have not been employed in symbolic search. In particular, mutexes and other constraining invariants, techniques that have been proven essential when doing regression, are yet to be exploited in conjunction with BDDs. In this paper we analyze the use of such constraints in symbolic search and its combination with minimization techniques common in BDD manipulation. Experimental results show a significant increase in performance, considerably above the current state of the art in optimal planning.