More Like this

1. Conflict-Based Search with Optimal Task Assignment

   Hoenig, W. ; Kiesel, S. ; Tinka, A. ; Durham, J. ; Ayanian, N. ( January 2018 , Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems)

   We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees. 

   more » « less
2. Global planning of accelerated degradation tests based on exponential dispersion degradation models

   https://doi.org/10.1002/nav.21923  

   Lee, I‐Chen ; Tseng, Sheng‐Tsaing ; Hong, Yili ( July 2020 , Naval Research Logistics (NRL))

   The accelerated degradation test (ADT) is an efficient tool for assessing the lifetime information of highly reliable products. However, conducting an ADT is very expensive. Therefore, how to conduct a cost‐constrained ADT plan is a great challenging issue for reliability analysts. By taking the experimental cost into consideration, this paper proposes a semi‐analytical procedure to determine the total sample size, testing stress levels, the measurement frequencies, and the number of measurements (within a degradation path) globally under a class of exponential dispersion degradation models. The proposed method is also extended to determine the global planning of a three‐level compromise plan. The advantage of the proposed method not only provides better design insights for conducting an ADT plan, but also provides an efficient algorithm to obtain a cost‐constrained ADT plan, compared with conventional optimal plans by grid search algorithms.

    

   more » « less
3. AccPar: Tensor Partitioning for Heterogeneous Deep Learning Accelerators

   https://doi.org/10.1109/HPCA47549.2020.00036  

   Song, Linghao ; Chen, Fan ; Zhuo, Youwei ; Qian, Xuehai ; Li, Hai ; Chen, Yiran ( February 2020 , 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA))

   Deep neural network (DNN) accelerators as an example of domain-specific architecture have demonstrated great success in DNN inference. However, the architecture acceleration for equally important DNN training has not yet been fully studied. With data forward, error backward and gradient calculation, DNN training is a more complicated process with higher computation and communication intensity. Because the recent research demonstrates a diminishing specialization return, namely, “accelerator wall”, we believe that a promising approach is to explore coarse-grained parallelism among multiple performance-bounded accelerators to support DNN training. Distributing computations on multiple heterogeneous accelerators to achieve high throughput and balanced execution, however, remaining challenging. We present ACCPAR, a principled and systematic method of determining the tensor partition among heterogeneous accelerator arrays. Compared to prior empirical or unsystematic methods, ACCPAR considers the complete tensor partition space and can reveal previously unknown new parallelism configurations. ACCPAR optimizes the performance based on a cost model that takes into account both computation and communication costs of a heterogeneous execution environment. Hence, our method can avoid the drawbacks of existing approaches that use communication as a proxy of the performance. The enhanced flexibility of tensor partitioning in ACCPAR allows the flexible ratio of computations to be distributed among accelerators with different performances. The proposed search algorithm is also applicable to the emerging multi-path patterns in modern DNNs such as ResNet. We simulate ACCPAR on a heterogeneous accelerator array composed of both TPU-v2 and TPU-v3 accelerators for the training of large-scale DNN models such as Alexnet, Vgg series and Resnet series. The average performance improvements of the state-of-the-art “one weird trick” (OWT) and HYPAR, and ACCPAR, normalized to the baseline data parallelism scheme where each accelerator replicates the model and processes different input data in parallel, are 2.98×, 3.78×, and 6.30×, respectively. 

   more » « less
4. Fast Cascading Outage Screening based on Deep Convolutional Neural Network and Depth-First Search

   https://doi.org/10.1109/TPWRS.2020.2969956  

   Du, Yan ; Li, Fangxing Fran ; Zheng, Tongxin ; Li, Jiang ( July 2020 , IEEE Transactions on Power Systems)

   In this paper, a data-driven method is proposed for fast cascading outage screening in power systems. The proposed method combines a deep convolutional neural network (deep CNN) and a depth-first search (DFS) algorithm. First, a deep CNN is constructed as a security assessment tool to evaluate system security status based on observable information.With its automatic feature extraction ability and the high generalization, a well-trained deep CNN can produce estimated AC optimal power flow (ACOPF) results for various uncertain operation scenarios, i.e., fluctuated load and system topology change, in a nearly computation-free manner. Second, a scenario tree is built to represent the potential operation scenarios and the associated cascading outages. The DFS algorithm is developed as a fast screening tool to calculate the expected security index value for each cascading outage path along the entire tree, which can be a reference for system operators to take predictive measures against system collapse. The simulation results of applying the proposed deep CNN and the DFS algorithm on standard test cases verify their accuracy, and the computational efficiency is thousands of times faster than the model-based traditional approach, which implies the great potential of the proposed algorithm for online applications. 

   more » « less
5. Lazy incremental search for efficient replanning with bounded suboptimality guarantees

   https://doi.org/10.1177/02783649241227869  

   Lim, Jaein ; Ghanei, Mahdi ; Lawson, R. Connor ; Srinivasa, Siddhartha ; Tsiotras, Panagiotis ( January 2024 , The International Journal of Robotics Research)

   We present a lazy incremental search algorithm, Lifelong-GLS (L-GLS), along with its bounded suboptimal version, Bounded L-GLS (B-LGLS) that combine the search efficiency of incremental search algorithms with the evaluation efficiency of lazy search algorithms for fast replanning in problem domains where edge evaluations are more expensive than vertex expansions. The proposed algorithms generalize Lifelong Planning A* (LPA*) and its bounded suboptimal version, Truncated LPA* (TLPA*), within the Generalized Lazy Search (GLS) framework, so as to restrict expensive edge evaluations only to the current shortest subpath when the cost-to-come inconsistencies are propagated during repair. We also present dynamic versions of the L-GLS and B-LGLS algorithms, called Generalized D* (GD*) and Bounded Generalized D* (B-GD*), respectively, for efficient replanning with non-stationary queries, designed specifically for navigation of mobile robots. We prove that the proposed algorithms are complete and correct in finding a solution that is guaranteed not to exceed the optimal solution cost by a user-chosen factor. Our numerical and experimental results support the claim that the proposed integration of the incremental and lazy search frameworks can help find solutions faster compared to the regular incremental or regular lazy search algorithms when the underlying graph representation changes often.

    

   more » « less