Complete and efficient detection of unknown targets is the most popular application of UAV swarms. Under most situations, targets have directional characteristics so that they can only be successfully detected within ...Complete and efficient detection of unknown targets is the most popular application of UAV swarms. Under most situations, targets have directional characteristics so that they can only be successfully detected within specific angles. In such cases, how to coordinate UAVs and allocate optimal paths for them to efficiently detect all the targets is the primary issue to be solved. In this paper, an intelligent target detection method is proposed for UAV swarms to achieve real-time detection requirements. First, a target-feature-information-based disintegration method is built up to divide the search space into a set of cubes. Theoretically, when the cubes are traversed, all the targets can be detected. Then, a Kuhn-Munkres(KM)-algorithm-based path planning method is proposed for UAVs to traverse the cubes. Finally, to further improve search efficiency, a 3 D realtime probability map is established over the search space which estimates the possibility of detecting new targets at each point. This map is adopted to modify the weights in KM algorithm, thereby optimizing the UAVs’ paths during the search process. Simulation results show that with the proposed method, all targets, with detection angle limitations, can be found by UAVs. Moreover, by implementing the 3 D probability map, the search efficiency is improved by 23.4%–78.1%.展开更多
As a result of the popularity of mobile devices,Mobile Crowd Sensing (MCS) has attracted a lot of attention. Task allocation is a significant problem in MCS. Most previous studies mainly focused on stationary spatial ...As a result of the popularity of mobile devices,Mobile Crowd Sensing (MCS) has attracted a lot of attention. Task allocation is a significant problem in MCS. Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers. In this paper,the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks,there are different start times and deadlines. In each round,the tasks are divided into urgent and non-urgent tasks. The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way,so they only receive a fixed payment as employment compensation,while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation. The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase. At the start of each round,the hiring of opportunistic workers is considered because they cost less to complete each task. The Poisson distribution is used to predict the location that the workers are going to visit,and greedily choose the ones with high utility. For participatory workers,the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps,the tasks are assigned to participatory workers by extending the Kuhn-Munkres (KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset,Brightkite,and three typical baseline methods are selected for comparison. Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.展开更多
文摘Complete and efficient detection of unknown targets is the most popular application of UAV swarms. Under most situations, targets have directional characteristics so that they can only be successfully detected within specific angles. In such cases, how to coordinate UAVs and allocate optimal paths for them to efficiently detect all the targets is the primary issue to be solved. In this paper, an intelligent target detection method is proposed for UAV swarms to achieve real-time detection requirements. First, a target-feature-information-based disintegration method is built up to divide the search space into a set of cubes. Theoretically, when the cubes are traversed, all the targets can be detected. Then, a Kuhn-Munkres(KM)-algorithm-based path planning method is proposed for UAVs to traverse the cubes. Finally, to further improve search efficiency, a 3 D realtime probability map is established over the search space which estimates the possibility of detecting new targets at each point. This map is adopted to modify the weights in KM algorithm, thereby optimizing the UAVs’ paths during the search process. Simulation results show that with the proposed method, all targets, with detection angle limitations, can be found by UAVs. Moreover, by implementing the 3 D probability map, the search efficiency is improved by 23.4%–78.1%.
基金National Natural Science Foundation of China(62102275,U20A20182,61873177,62072322)Natural Science Foundation of Jiangsu Province in China(BK20210704)Natural Science Foundation of the Jiangsu Higher Education Institutions of China(21KJB520025).
文摘As a result of the popularity of mobile devices,Mobile Crowd Sensing (MCS) has attracted a lot of attention. Task allocation is a significant problem in MCS. Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers. In this paper,the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks,there are different start times and deadlines. In each round,the tasks are divided into urgent and non-urgent tasks. The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way,so they only receive a fixed payment as employment compensation,while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation. The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase. At the start of each round,the hiring of opportunistic workers is considered because they cost less to complete each task. The Poisson distribution is used to predict the location that the workers are going to visit,and greedily choose the ones with high utility. For participatory workers,the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps,the tasks are assigned to participatory workers by extending the Kuhn-Munkres (KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset,Brightkite,and three typical baseline methods are selected for comparison. Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.
