Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant on the wellknown christofides' algorithm for the TSP, called the Best-of-Many christofides' algorithm...
详细信息
ISBN:
(纸本)9783662483503;9783662483497
Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant on the wellknown christofides' algorithm for the TSP, called the Best-of-Many christofides' algorithm. The algorithm involves sampling a spanning tree from the solution to the standard LP relaxation of the TSP, and running christofides' algorithm on the sampled tree. In this paper we perform an experimental evaluation of the Best-of-Many christofides' algorithm to see if there are empirical reasons to believe its performance is better than that of christofides' algorithm. In our experiments, all of the implemented variants of the Best-of-Many christofides' algorithm perform significantly better than christofides' algorithm;an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good.
One of the crucial challenges in networked Unmanned Aerial Vehicles (UAVs) is to configure them to serve as aerial base stations (BSs) for collecting data from distributed Internet of Things (IoT) devices in a region ...
详细信息
One of the crucial challenges in networked Unmanned Aerial Vehicles (UAVs) is to configure them to serve as aerial base stations (BSs) for collecting data from distributed Internet of Things (IoT) devices in a region devoid of backbone connectivity. To address this challenge, it is required to compute optimized trajectories of UAVs to collect data while considering the different activation patterns of IoT devices. We propose a scheme to optimize the trade-off between the number of covered IoT devices and the travel time of UAVs. The formulated cost minimization problem is the capacitated single depot vehicle routing problem (CSDVRP), which is NP-hard. We propose a solution scheme named Cost-Effective Data Aggregation for UAV-Enabled IoT Networks (CEDAN), which operates in four steps. First, it determines the optimized hovering locations (HLs) for UAVs. Subsequently, CEDAN determines the optimized route adopting christofides's approximation algorithm for Travelling Salesman Problem (TSP). Further, a split function produces the optimized trajectories for all UAVs. Finally, a route adjustment algorithm applies the cost function and rearranges the order of visiting each HL. Extensive simulation results depict that the CEDAN outperforms than Clarke-Wright (CW) savings heuristics, CEDAN without route adjustment (CWRA), and Zhan et al., respectively.
The manuscript presents a high-level mission planning for multi-agent indoor systems. The high-level mission planning separates the mission goals between the agents, plans the order of the mission goals, and provides ...
详细信息
ISBN:
(纸本)9798350393101;9798350393095
The manuscript presents a high-level mission planning for multi-agent indoor systems. The high-level mission planning separates the mission goals between the agents, plans the order of the mission goals, and provides corridors serving as constraints for a real-time controller of the multi-agent system in which the real-time controller searches for optimal paths while resolving conflicts between the agents. The proposed algorithm uses a highly optimized tree data structure to represent a 3D indoor environment. Then the set of adjacent tree nodes defines the shortest possible corridor to fulfill the mission goals while avoiding obstacles in the indoor environment. Planning the mission goals order and assignment to agents is an NP-hard problem that we solve using heuristic algorithms to find a viable solution before the mission starts. This work implements a multi-objective optimization algorithm combining a genetic algorithm and simulated annealing to find a viable solution for the mission as a composition of the unobstructed corridors between the individual mission goals found by the A* path planning algorithm. The evaluation of the proposed high-level mission planning in a typical indoor environment finds a viable solution in time, even for a large number of mission goals. Also, the behavior of the multi-agent system is easily altered to prefer solutions minimizing the total traveled distance or distributing the workload evenly between the agents based on the mission character.
During the COVID-19 pandemic, social distancing has been applied worldwide to reduce the risk of infection. In hospitals, this requires a new strategy for movement management in the corridors to avoid cross-overs and ...
详细信息
ISBN:
(纸本)9781538674628
During the COVID-19 pandemic, social distancing has been applied worldwide to reduce the risk of infection. In hospitals, this requires a new strategy for movement management in the corridors to avoid cross-overs and satisfy social distancing requirements. In this paper, we study the problem of routing and path finding for two flows of patients (COVID-19 and Non-COVID) in the hospital during the pandemic using as many disjoint paths as possible. We present two scenarios based respectively on an offline and an online method to model the routing and labeling of the hospital paths and compare them using a simulation tool. The simulation result shows the proposed solutions outperform the baseline which is based on the Dijkstra algorithm. This outcome can help increase safety by considering the guideline for COVID-19 and Non-COVID patients in healthcare centers during the pandemic.
Owing to the flexibility and low cost, cooperative Unmanned Aerial Vehicles(UAVs) have been attractive in multi-target positioning recently. Although it is popular and easy to accomplish, positioning based on trilater...
详细信息
Owing to the flexibility and low cost, cooperative Unmanned Aerial Vehicles(UAVs) have been attractive in multi-target positioning recently. Although it is popular and easy to accomplish, positioning based on trilateration method still faces challenges under scenarios with multiple UAVs. First, large accumulated errors will be brought if a single UAV is used to perform trilateration on same targets. Second, due to the mobility of targets, the time interval between UAVs performing twice successive distance measurement on one target cannot be long for positioning precision. Finally, the limited energy provided by onboard battery limits the time for UAVs to perform tasks. Once the energy used by some of the UAVs reaches limitation, the whole positioning mission will fail. Thus, to complete the mission of locating multiple targets, this paper is intended to minimize the maximum energy consumption among all UAVs. We formulate the problem, and decompose it into two subproblems, one of which plans the routes for UAV groups and the other plans the routes for UAVs in a group. To solve the first subproblem, a heuristic algorithm called adjusted genetic algorithm (AGA) is proposed to plan trajectories for all UAV groups under constraints on maximum energy consumption. To guarantee stable performance and reduce computation complexity, we propose an approximation algorithm, Tree Decomposition united with christofides algorithm (TDCA), and the approximation ratio is proved to be (3 * N '/(2*(N ' 1))), where N ' denotes the number of UAV groups. For the second subproblem, a two-step greedy heuristic algorithm is proposed to plan trajectories for UAVs in same groups. Extensive simulations show that compared to existing algorithms, the proposed algorithms can reduce up to 26.6% maximum and 26.3% average energy consumption.
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by christofides in 1976 and is well know...
详细信息
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by christofides in 1976 and is well known as "the christofides algorithm". Recently, some authors started calling it "christofides-Serdyukov algorithm", pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukov's findings and a translation of his article from Russian into English. (C) 2020 Elsevier Inc. All rights reserved.
This paper presents a method for automatic sensor placement for model-based robot vision. In such a vision system, the sensor often needs to be moved from one pose to another around the object to observe all features ...
详细信息
This paper presents a method for automatic sensor placement for model-based robot vision. In such a vision system, the sensor often needs to be moved from one pose to another around the object to observe all features of interest. This allows multiple three-dimensional (3-D) images to be taken from different vantage viewpoints. The task involves determination of the optimal sensor placements and a shortest path through these viewpoints. During the sensor planning, object. features are resampled as individual points attached with surface normals. The optimal sensor placement graph is achieved by a genetic algorithm in which a min-max criterion is used for the evaluation. A shortest path is determined by christofides algorithm. A Viewpoint Planner is developed to generate the sensor placement plan. It includes many functions, such as 3-D animation of the object geometry, sensor specification, initialization of the viewpoint number and their distribution, viewpoint evolution, shortest path computation, scene simulation of a specific viewpoint, parameter amendment. Experiments are also carried out on a real robot vision system to demonstrate the effectiveness of the proposed method.
暂无评论