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 theTask 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, namelyAuction-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 namedMulti-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.