More Like this

1. A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection

   https://doi.org/10.1007/978-3-031-15707-3_32  

   Liu, L.; Truszczynski, M.; Lierler Y. (August 2022, Logic Programming and Nonmonotonic Reasoning)

   Answer set programming (ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. We describe a system and its implementation that given a set of encodings and a training set of instances, builds performance models for the encodings, predicts the execution time of these encodings on new instances, and uses these predictions to select an encoding for solving. 

   more » « less
2. Effective Heuristics for Multi-Robot Path Planning in Warehouse Environments

   Han, Shuai D.; Yu, Jingjin (August 2019, THE 2ND IEEE INTERNATIONAL SYMPOSIUM ON MULTI-ROBOT AND MULTI-AGENT SYSTEMS)

   In this preliminary study, we propose a new centralized decoupled algorithm for solving one-shot and dynamic optimal multi-robot path planning problems in a grid- based setting mainly targeting warehouse like environments. In particular, we exploit two novel and effective heuristics: path diversification and optimal sub-problem solution databases. Preliminary evaluation efforts demonstrate that our method achieves promising scalability and good solution optimality. 

   more » « less
3. Scheduling Stochastic Jobs - Complexity and Approximation Algorithms

   Tao, L. (May 2021, Proceedings of the International Conference on Automated Planning and Scheduling)

   null (Ed.)

   Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the β-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution. 

   more » « less
4. Delay-Efficient and Reliable Data Relaying in UltraDense Networks using Rateless Codes

   L. Yao, M. Hashemi (January 2020, Delay-Efficient and Reliable Data Relaying in UltraDense Networks using Rateless Codes)

   null (Ed.)

   We investigate the problem of delay-efficient and reliable data delivery in ultra-dense networks (UDNs) that constitute macro base stations (MBSs), small base stations (SBSs), and mobile users. Considering a two-hop data delivery system, we propose a partial decode-and-forward (PDF) relaying strategy together with a simple and intuitive amicable encoding scheme for rateless codes to significantly improve user experience in terms of end-to-end delay. Simulation results verify that our amicable encoding scheme is efficient in improving the intermediate performance of rateless codes. It also verifies that our proposed PDF significantly improves the performance of the decode-and-forward (DF) strategy, and that PDF is much more robust against channel degradation. Overall, the proposed strategy and encoding scheme are efficient towards delay-sensitive data delivery in the UDN scenarios. 

   more » « less
5. Multi-Agent Motion Planning for Differential Drive Robots Through Stationary State Search

   https://doi.org/10.1609/aaai.v39i22.34503  

   Yan, Jingtian; Li, Jiaoyang (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   Multi-Agent Motion Planning (MAMP) finds various applications in fields such as traffic management, airport operations, and warehouse automation. In many of these environments, differential drive robots are commonly used. These robots have a kinodynamic model that allows only in-place rotation and movement along their current orientation, subject to speed and acceleration limits. However, existing Multi-Agent Path Finding (MAPF)-based methods often use simplified models for robot kinodynamics, which limits their practicality and realism. In this paper, we introduce a three-level framework called MASS to address these challenges. MASS combines MAPF-based methods with our proposed stationary state search planner to generate high-quality kinodynamically-feasible plans. We further extend MASS using an adaptive window mechanism to address the lifelong MAMP problem. Empirically, we tested our methods on the single-shot grid map domain and the lifelong warehouse domain. Our method shows up to 400% improvements in terms of throughput compared to existing methods. 

   more » « less