检索结果-内蒙古大学图书馆

Deep Reinforcement Learning With Adversarial Training for Automated Excavation Using Depth Images

IEEE ACCESS 2022年 10卷 4523-4535页

作者： Osa, Takayuki Aizawa, Masanori Kyushu Inst Technol Dept Human Intelligence Syst Fukuoka 8080135 Japan Kyushu Inst Technol Res Ctr Neuromorph AI Hardware Fukuoka 8080135 Japan RIKEN Ctr Adv Intelligence Project Tokyo 1030027 Japan Komatsu Ltd Hiratsuka Kanagawa 2540913 Japan

Excavation, which is one of the most frequently performed tasks during construction often poses danger to human operators. To reduce potential risks and address the problem of workforce shortage, automation of excavation is essential. Although previous studies have yielded promising results based on the use of reinforcement learning (RL) for automated excavation, the properties of excavation task in the context of RL have not been sufficiently investigated. In this study, we investigate Qt-Opt, which is a variant of Q-learning algorithms for continuous action space, for learning the excavation task using depth images. Inspired by virtual adversarial training in supervised learning, we propose a regularization method that uses virtual adversarial samples to reduce overestimation of Q-values in a Q-learning algorithm. Our results reveal that Qt-Opt is more sample-efficient than state-of-the-art actor-critic methods in our problem setting, and we verify that the proposed method further improves the sample efficiency of Qt-Opt. Our results demonstrate that multiple optimal actions often exist within the process of excavation and the choice of policy representation is crucial for satisfactory performance.

关键词： Excavation Task analysis Training Q-learning Automation Licenses approximation algorithms Construction industry automation machine learning reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically 40

Approximating the Geometric Knapsack Problem in Near-Linear ...

引用

40th International Symposium on Computational Geometry, SoCG 2024

作者： Buchem, Moritz Deuker, Paul Wiese, Andreas Technische Universität München Germany

ISBN: (纸本)9783959773164

One important goal in algorithm design is determining the best running time for solving a problem (approximately). For some problems, we know the optimal running time, assuming certain conditional lower bounds. In this paper, we study the d-dimensional geometric knapsack problem in which we are far from this level of understanding. We are given a set of weighted d-dimensional geometric items like squares, rectangles, or hypercubes and a knapsack which is a square or a (hyper-)cube. Our goal is to select a subset of the given items that fit non-overlappingly inside the knapsack, maximizing the total profit of the packed items. We make a significant step towards determining the best running time for solving these problems approximately by presenting approximation algorithms whose running times are near-linear, i.e., O(n · poly(log n)), for any constant d and any parameter ϵ > 0 (the exponent of log n depends on d and 1/ϵ). In the case of (hyper)-cubes, we present a (1 + ϵ)-approximation algorithm. This improves drastically upon the currently best known algorithm which is a (1 + ϵ)-approximation algorithm with a running time of nOϵ,d(1) where the exponent of n depends exponentially on 1/ϵ and d. In particular, our algorithm is an efficient polynomial time approximation scheme (EPTAS). Moreover, we present a (2 + ϵ)-approximation algorithm for rectangles in the setting without rotations and a (179 + ϵ) ≈ 1.89-approximation algorithm if we allow rotations by 90 degrees. The best known polynomial time algorithms for this setting have approximation ratios of 179 +ϵ and 1.5+ϵ, respectively, and running times in which the exponent of n depends exponentially on 1/ϵ. In addition, we give dynamic algorithms with polylogarithmic query and update times, having the same approximation guarantees as our other algorithms above. Key to our results is a new family of structured packings which we call easily guessable packings. They are flexible enough to guarantee the existence of prof

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

3-D Path Planning Using Improved RRT* Algorithm for Robot-Assisted Flexible Needle Insertion in Multilayer Tissues

IEEE CANADIAN JOURNAL OF ELECTRICAL AND COMPUTER ENGINEERING

引用

IEEE CANADIAN JOURNAL OF ELECTRICAL AND COMPUTER ENGINEERING 2022年第1期45卷 50-62页

作者： Zhang, Yongkang Ju, Zhiyang Zhang, Hui Qi, Zhi Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China

In the field of minimally invasive surgery, flexible needles can avoid blood vessels and organs more flexibly compared to rigid needles. One of the main challenges when using flexible needles to reach lesions is planning a suitable path. Due to the non-holonomic characteristic of the flexible needle dynamics and the tissue deformation caused by the needle tip during the insertion, the accessibility and safety of the needle's states need to be considered in the path planning stage. In this article, we propose an adaptable algorithm by improving the canonical rapidly exploring random trees* (RRT*) algorithm to compute a path for the flexible needle to reach targets in a layered tissue environment. The improved RRT* algorithm that addresses the motion constraints of the flexible needle renders the computed path comparatively smoother and optimal in some approximation sense. In the proposed algorithm, a strategy of adapting some of its parameters for different tissues during the insertion is developed, which improves the safety of surgeries. Moreover, the path cost used in the algorithm takes the potential fields of surrounding obstacles into account, which is used to deal with the influence of the local movement of tissues during the needle puncture process. Simulations are conducted to verify the effectiveness of the proposed algorithm. The results show that the improved RRT* algorithm generates a smooth and safe path which satisfies the motion constraints of the flexible needle in layered tissue environment.

关键词： Needles Path planning Planning approximation algorithms Nonhomogeneous media Kinematics Inverse problems Flexible needle insertion multilayer tissues path planning rapidly exploring random trees* (RRT*)

来源：评论

学校读者我要写书评

暂无评论

FastDTW is Approximate and Generally Slower Than the Algorithm it Approximates

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第8期34卷 3779-3785页

作者： Wu, Renjie Keogh, Eamonn J. Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA

Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time.

关键词： Time series analysis approximation algorithms Time measurement Task analysis Classification algorithms Data mining Heart beat Dynamic time warping time series analysis similarity measures data mining

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the Steiner tree problem with bounded edge-length

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 20-36页

作者： Chen, Chi-Yeh Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn 1 Univ Rd Tainan Taiwan

This work firstly studies the Steiner tree problem with bounded edge-length din which dis the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of dln4d/d+ln4-1 + epsilon for general graphs and approximation ratio of 73.d/60.d+13 + epsilon for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + epsilon for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Steiner trees approximation algorithms Network design Randomized algorithms Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

Data Deduplication With Random Substitutions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第10期68卷 6941-6963页

作者： Lou, Hao Farnoud, Farzad Univ Virginia Dept Elect & Comp Engn Charlottesville VA 22903 USA Univ Virginia Dept Comp Sci Charlottesville VA 22903 USA

Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more computationally efficient and are thus widely used in large scale storage systems. In this paper, we provide an information-theoretic analysis of the performance of deduplication algorithms on data streams in which repeats are not exact. We introduce a source model in which probabilistic substitutions are considered. More precisely, each symbol in a repeated string is substituted with a given edit probability. Deduplication algorithms in both the fixed-length scheme and the variable-length scheme are studied. The fixed-length deduplication algorithm is shown to be unsuitable for the proposed source model as it does not take into account the edit probability. Two modifications are proposed and shown to have performances within a constant factor of optimal for a specific class of source models with the knowledge of model parameters. We also study the conventional variable-length deduplication algorithm and show that as source entropy becomes smaller, the size of the compressed string vanishes relative to the length of the uncompressed string, leading to high compression ratios.

关键词： Symbols Entropy Data models Probabilistic logic Analytical models approximation algorithms Genomics Chunking data compression data deduplication source coding substitution edits

来源：评论

学校读者我要写书评

暂无评论

Real-Time Schedule of Microgrid for Maximizing Battery Energy Storage Utilization

引用

IEEE TRANSACTIONS ON SUSTAINABLE ENERGY 2022年第3期13卷 1356-1369页

作者： Xue, Xizhen Ai, Xiaomeng Fang, Jiakun Cui, Shichang Jiang, Yazhou Yao, Wei Chen, Zhe Wen, Jinyu Huazhong Univ Sci & Technol Sch Elect & Elect Engn State Key Lab Adv Electromagnet Engn & Technol Wuhan 430074 Peoples R China Clarkson Univ Dept Elect & Comp Engn Potsdam NY 13676 USA Aalborg Univ Dept Energy Technol DK-9220 Aalborg Denmark

This paper proposes a real-time schedule model of a microgrid (MG) for maximizing battery energy storage (BES) utilization. To this end, a BES life model is linearized using piece-wise linearization and big-M method to assess the BES life loss (BLL) in a real-time manner. The cost-effective schedule model of the MG with multiple energy resources aims to maximize BES utilization while ensuring its sufficient lifespan. Corresponding to the optimization model, approximate dynamic programming (ADP) for maximizing BES utilization (ADP-MBU) in the real-time schedule is proposed to optimize the system under stochastic environments. In ADP-MBU, a new value function approximation method employing the BES cumulative life loss (BCLL) is developed to improve the optimality and applicability. The proposed ADP-MBU algorithm can achieve satisfactory approximate optimality while reflecting the variation of real-time BLL. Case studies validate the applicability of the proposed MG schedule model and the advantages of the proposed ADP-MBU algorithm.

关键词： Schedules Real-time systems Costs Computational modeling Optimization approximation algorithms Wind forecasting Real-time schedule microgrid maximize BES utilization approximate dynamic programming BES cumulative life loss

来源：评论

学校读者我要写书评

暂无评论

Online EV Scheduling algorithms for Adaptive Charging Networks with Global Peak Constraints

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2022年第3期7卷 537-548页

作者： Alinia, Bahram Hajiesmaili, Mohammad H. Lee, Zachary J. Crespi, Noel Mallada, Enrique Telecom SudParis Inst Mines Telecom Dept Networks & Mobile Multimedia Serv RS2M F-91000 Evry France Univ Massachusetts Coll Informat & Comp Sci Amherst MA 01003 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA

This paper tackles online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The technical challenge is the need for online solution design since in practical scenarios the scheduler has no or limited information of future arrivals in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. For offline setting, we devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions.

关键词： approximation algorithms Scheduling Electric vehicle charging Scheduling algorithms Adaptive systems Electronic mail Charging stations Electric vehicle online scheduling approximation algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Modifications to Finite Difference Algorithm for Polynomial Phase Signal Parameter Estimation

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2022年第1期58卷 496-507页

作者： Madsen, Nathan Cao, Siyang Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA

The finite difference (FD) algorithm is a recently proposed algorithm for single-component polynomial phase signal (PPS) parameter estimation. It can handle high-order PPSs, while being computationally simple. A drawback of the algorithm is that it cannot operate at lower signal-to-noise ratios (SNRs). We propose modifications to allow the FD algorithm to operate at lower SNRs. The modifications are magnitude weighting for phase values, phase difference filtering, and iterating the polynomial refinement step. Simulation shows that these modifications can reduce the algorithm's SNR threshold by 5 dB, without greatly increasing the computational complexity.

关键词： approximation algorithms Signal to noise ratio Phase estimation Standards Indexes Frequency estimation Estimation Finite difference (FD) parameter estimation phase estimation phase unwrapping polynomial phase signals (PPSs)

来源：评论

学校读者我要写书评

暂无评论

Cleaning Uncertain Data With Crowdsourcing-A General Model With Diverse Accuracy Rates

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第8期34卷 3629-3642页

作者： Zhang, Chen Zhang, Haodi Xie, Weiteng Liu, Nan Li, Qifan Jiang, Di Lin, Peiguang Wu, Kaishun Chen, Lei Shandong Univ Finance & Econ Sch Comp Sci & Technol Jinan 250014 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China WeBank AI Shenzhen 518052 Peoples R China Guangzhou HKUST Fok Ying Tung Res Inst Guangzhou Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions.

关键词： Crowdsourcing Cleaning Uncertainty Data integrity approximation algorithms Urban areas Databases Crowdsourcing cleaning uncertain data approximation algorithm heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：