Yifei Li

In this letter, we study the Multi-Size Agent Path Finding (MSAPF) problem, which is a generalization of the Multi-Agent Path Finding (MAPF) problem and has a wider range of practical applications in intelligent transportation. Compared to the well-known MAPF problem in which each agent only occupies one grid, multi-size agents in MSAPF have different sizes and may occupy multiple grids. Different sizes result in two bottlenecks in finding conflict-free paths. One is that conflicts between the shortest paths of multi-size agents are difficult to resolve, and the other is that numerous new conflicts are likely to occur when resolving one conflict. Existing MAPF algorithms are inefficient in solving MSAPF because they only consider conflicts involving a single grid or between adjacent grids, and few works focus on solving these bottlenecks of MSAPF. To solve MSAPF, we propose a novel and complete algorithm named Global Planning and Local Update (GPLU), which is a two-level algorithm and can efficiently find conflict-free paths for multi-size agents. GPLU is an unbounded sub-optimal algorithm that cannot find the optimal solution. However, we prove that GPLU is complete, which means that GPLU can return solutions for solvable MSAPF instances if such solutions exist. To improve the efficiency of GPLU, we propose two optimization strategies. The former improves efficiency while ensuring completeness, and the latter reduces the time complexity of GPLU to polynomial time. Extensive experiments conducted on a popular benchmark show that our proposed algorithms can support 20%$\sim$116.67% more multi-size agents than existing MAPF/MSAPF algorithms.

Recently, heterogeneous mobile robots (HMRs) have been widely implemented in warehouses or factories with limited space to improve efficiency. HMRs have different capabilities and sizes, which leads to two bottlenecks in the task planning for HMRs in an online environment. One is that it is hard to efficiently find high-quality task assignment results between heterogeneous tasks and HMRs because heterogeneous tasks need to be completed by HMRs of different capabilities. The other is that finding collision-free paths for HMRs of different sizes to complete assigned tasks is hard to satisfy the real-time demand. Existing works mainly consider solving these two bottlenecks separately while ignoring the mutual influence between the results of task assignment and collision-free path finding. To solve these issues, in this paper, we formally define the Online Task Planning with Collision Avoidance for HMRs (OTCH) problem, in which the platform aims to find the best task assignment and collision-free paths for HMRs to complete as many heterogeneous tasks as possible while minimizing the total cost containing the path cost and the delay cost. To solve the OTCH problem, we propose a novel task planning framework that considers task assignment and collision-free path finding simultaneously. Within this framework, we first present an aggregation algorithm to accelerate calculations. Then, we propose a network-flow-based task assignment algorithm to find a high-quality task assignment between heterogeneous tasks and HMRs in each batch. Finally, we propose a novel and efficient path finding algorithm to find collision-free paths for HMRs to complete assigned tasks while satisfying real-time demand. In addition, we not only analyze the complexity of the OTCH problem in detail but also give theoretical analysis for our proposed algorithms. Extensive experiments in a real-world dataset and two simulated datasets show that our proposed algorithms outperform the state-of-the-art while having the best scalability.

Social images shared on social media are often associated with geo-tagged information and text descriptions. Given a set of keywords and a spatial location, geo-tagged social image search can retrieve top-k image objects that best match query parameters in terms of spatial distance and tag similarity of social images. However, due to improper parameter settings, users may notice that some expected images are missing and wonder why these objects do not appear in the query results. This paper studies the why-not top-k social image search question and proposes efficient query refinement algorithms, aiming to minimally modify users' initial queries to reintroduce missing objects. We first develop a baseline algorithm that traverses each possible query parameter sequentially to find the best refinement parameters. Then, we propose a fast search algorithm with two optimization strategies named lower ranking nodes pruning and early stop pruning, which can improve performance by quickly removing low-ranking social images. In addition, we propose an efficient boundary search algorithm that can determine the ranking of missing images at a low time cost. We also extend the proposed techniques to handle multiple missing images. Extensive experimental results demonstrate that the proposed solution is two orders of magnitude faster than baseline and is effective in a wide range of settings.

Recently, heterogeneous automated guided vehicles (AGVs) are widely deployed to improve the work efficiency of the logistics warehouse with limited space. While completing various tasks to improve efficiency and reduce transport costs, heterogeneous AGVs also bring new challenges to task planning in warehouses because of their different shapes, speeds, and capabilities. Briefly, it is difficult to efficiently calculate the costs for heterogeneous AGVs to complete tasks and assign heterogeneous AGVs suitable tasks in real time. Inspired by this, in this paper, we study the Task Planning for Heterogeneous AGVs (TPHA) problem, in which the warehouse assigns tasks to suitable heterogeneous AGVs to minimize the total cost containing the travel cost and the tardiness cost. To solve the TPHA problem, we propose a novel framework that considers the route planning and task assignment simultaneously. Within this framework, we first present an efficient cost computation algorithm to calculate costs between tasks and heterogeneous AGVs. Then, we present two task assignment algorithms to assign tasks to suitable heterogeneous AGVs. Finally, we propose an improved route planning algorithm for further improving the processing time and reducing the total cost. Compared with state-of-the-art, extensive experiments on both real and synthesized datasets examine that our proposed algorithms can save 91.83% $\sim$ 97.19% of processing time and reduce 29.08% of the total cost at most.

The booming of mobile internet and crowdsourcing technology has offered great opportunities for first and last mile logistics (FLML) service. Unlike the traditional FLML service that separates the parcel collection in the first mile from the parcel delivery in the last mile, a new type of crowdsourced FLML service integrates parcel collection and parcel delivery services as a whole, which can significantly improve the efficiency of FLML service. Briefly, in a crowdsourced FLML service, the platform assigns the customers’ triggered pick-up parcels to the couriers who are delivering drop-off parcels in terms of the real-time status of couriers (e.g., capacity, location, and schedule). Existing works solving the crowdsourced FLML problem only consider the utility maximization for the platform but ignore the incentive to the utilities of couriers. Inspired by this, in this paper, we investigate a novel type of crowdsourced FLML problem, namely Auction-based Crowdsourced FLML (ACF) , where the platform assigns the couriers with suitable pick-up parcels based on the preferences of couriers with the goal of maximizing the social welfare of the platform and couriers. To solve the ACF problem, we present a novel auction model named Multi-attribute Reverse Vickrey (MRV) , where the couriers bid on parcels according to their preferences for parcels. Based on the MRV model, we present three efficient assignment algorithms to assign parcels to couriers. In addition, we give theoretical analysis for our proposed algorithms. Extensive experiments examine the efficiency and effectiveness of our solutions.