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

Multiagent Task Allocation for Dynamic Intelligent Space: auction and Preemption With Ontology Knowledge Graph

IET CYBER-SYSTEMS AND ROBOTICS 2025年第1期7卷

作者： Li, Wei Shang, Jianhang Liu, Guoliang Liu, Zhenhua Tian, Guohui China Telecom Res Inst Big Data & Artificial Intelligence Inst Beijing Peoples R China Shandong Univ Sch Control Sci & Engn Jinan Peoples R China

This paper introduces a pioneering dynamic system optimisation for multiagent (DySOMA) framework, revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems. The core of DySOMA is an advanced auction-based algorithm coupled with a novel task preemption ranking mechanism, seamlessly integrated with an ontology knowledge graph that dynamically updates. This integration not only enhances the efficiency of task allocation among robots but also significantly improves the adaptability of the system to environmental changes. Compared to other advanced algorithms, the DySOMA algorithm shows significant performance improvements, with its RLB 26.8% higher than that of the best-performing Consensus-Based Parallel auction and Execution (CBPAE) algorithm at 10 robots and 29.7% higher at 20 robots, demonstrating its superior capability in balancing task loads and optimising task completion times in larger, more complex environments. DySOMA sets a new benchmark for intelligent robot task scheduling, promising significant advancements in the autonomy and flexibility of robotic systems in complex evolving environments.

关键词： auction algorithm dynamic intelligent spaces multirobot task allocation ontology knowledge graph preemption mechanism smart home

来源：评论

学校读者我要写书评

暂无评论

auction algorithms for market equilibrium

引用

MATHEMATICS OF OPERATIONS RESEARCH 2006年第4期31卷 714-729页

作者： Garg, Rahul Kapoor, Sanjiv IBM India Res Lab New Delhi 110016 India Indian Inst Technol Chicago IL 60616 USA

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of goods. The market equilibrium problem is to compute a price vector that ensures market clearing, i.e., the demand of a positively priced good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in economics. This paper presents a formulation of the market equilibrium problem as a parameterized linear program. We construct a family of duals con-responding to these parameterized linear programs and show that finding the market equilibrium is the same as finding a linear program from this family of linear programs. The market-clearing conditions arise naturally from complementary slackness conditions. We then define an auction mechanism that computes prices such that approximate market clearing is achieved. The algorithm we obtain outperforms previously known methods.

关键词： market equilibrium auction algorithm Walrasian model

来源：评论

学校读者我要写书评

暂无评论

auction algorithms for Market Equilibrium with Weak Gross Substitute Demands and Their Applications 38

Auction Algorithms for Market Equilibrium with Weak Gross Su...

引用

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Garg, Jugal Husic, Edin Vegh, Laszlo A. Univ Illinois Champaign IL 61820 USA London Sch Econ & Polit Sci Dept Math London England

ISBN: (纸本)9783959771801

We consider the Arrow-Debreu exchange market model where agents' demands satisfy the weak gross substitutes (WGS) property. This is a well-studied property, in particular, it gives a sufficient condition for the convergence of the classical tatonnement dynamics. In this paper, we present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands. Such auction algorithms have been previously known for restricted classes of WGS demands only. As an application of our technique, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for NSW with budget separable piecewise linear utility functions;only a pseudopolynomial approximation algorithm was known for this setting previously.

关键词： auction algorithm weak gross substitutes Fisher equilibrium Gale equilibrium Nash social welfare

来源：评论

学校读者我要写书评

暂无评论

PARALLEL SHORTEST-PATH auction algorithmS

引用

PARALLEL COMPUTING 1994年第9期20卷 1221-1247页

作者： POLYMENAKOS, LC BERTSEKAS, DP MIT INFORMAT & DECIS SYST LABCAMBRIDGEMA 02139

In this paper we discuss the parallel implementation of the auction algorithm for shortest path problems. We show that bath the one-sided and the two-sided versions of the algorithm admit asynchronous implementations. We implemented the parallel schemes for the algorithm on a shared memory machine and tested its efficiency under various degrees of synchronization and for different types of problems. We discuss the efficiency of the parallel implementation of the many origins-one destination problem, the all origins-one destination problem, and the many origins-many destinations problem.

关键词： SHORTEST PATH PROBLEM auction algorithm SHARED MEMORY MULTIPROCESSOR PARALLEL IMPLEMENTATION PERFORMANCE RESULTS

来源：评论

学校读者我要写书评

暂无评论

Towards auction algorithms for large dense assignment problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2009年第3期43卷 411-436页

作者： Bus, Libor Tvrdik, Pavel Czech Tech Univ Dept Comp Sci & Engn CR-16635 Prague Czech Republic

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable.

关键词： Linear sum assignment problem auction algorithm Linear optimization Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

An auction Theory Based algorithm for Throughput Maximizing Scheduling in Centralized Cognitive Radio Networks

引用

IEEE COMMUNICATIONS LETTERS 2011年第7期15卷 734-736页

作者： Eraslan, Basak Gozupek, Didem Alagoz, Fatih Bogazici Univ Dept Comp Engn TR-80815 Bebek Turkey

In this letter we propose an auction theory based algorithm for throughput maximizing scheduling in centralized cognitive radio networks (CRN). In the considered CRN scheme, a centralized base station coordinates the assignment of frequencies and time slots to cognitive users with multiple antennas. Our proposed algorithm uses first-price sealed bid auction mechanism in which frequency and time slot pairs are considered as the auctioned resources and cognitive users are the bidders. The experimental results show that our computationally efficient algorithm yields very close throughput performance to the optimization software CPLEX values.

关键词： auction algorithm first price sealed bid auction resource allocation scheduling dynamic spectrum access cognitive radio networks

来源：评论

学校读者我要写书评

暂无评论

Multi-unmanned Aerial Vehicle Cooperative Task Allocation algorithm Based on Improved Distributed Cooperative auction

Multi-unmanned Aerial Vehicle Cooperative Task Allocation Al...

引用

International Conference on Autonomous Unmanned Systems (ICAUS)

作者： Bao, Kanghua Yi, Shuang Zhang, Hongjiang He, Pengsheng Southwest Comp Co Ltd Chongqing 400060 Peoples R China Chongqing Univ Chongqing 400044 Peoples R China

ISBN: (纸本)9789819904815;9789819904792;9789819904785

In order to make better use of and coordinate unmanned aerial vehicle (UAV) resources and realize the function of UAV autonomous collaborative task execution, an improved distributed collaborative auction algorithm is proposed for the complex allocation problem of multi-UAV and multiple tasks. A new auction mechanism is developed. The algorithm has wider applicability and can solve various allocation problems such as "one to one, one to many, many to one, many to many". Simulation results show that the improved algorithm has good results in solving different allocation problems, and it is easier to get the optimal income, which proves the effectiveness of the algorithm.

关键词： Multiple unmanned aerial vehicle Task assignment auction algorithm

来源：评论

学校读者我要写书评

暂无评论

State-of-the-Art auction algorithms for Multi-depot Bus Scheduling Problem Considering Depot Workload Balancing Constraints

引用

FUZZY INFORMATION AND ENGINEERING 2020年第2期12卷 253-273页

作者： Niksirat, M. Birjand Univ Technol Dept Comp Sci Birjand Iran

This paper deals with multi-depot bus scheduling (MDBS) problem. Depot workload balancing constraints are introduced. In this case, the problem can be stated as a two-objective multi-commodity flow problem with soft constraints. Two state-of-the-art heuristics are developed including schedule-based and cluster-based heuristics, both of them extend auction algorithm. Also three different approaches are proposed to satisfy depot workload balancing constraints. The convergence of each algorithm is investigated and its complexity obtained. To illustrate the main concepts and results, a small example is solved. Also, to demonstrate the performance of the proposed algorithms, some benchmark examples are considered and CPU-time and optimality gap are compared. The results show a great improvement in the CPU time and quality of the solution of the proposed algorithms. Also the extension of the proposed algorithms under epsilon-scaling approach is analysed.

关键词： auction algorithm multi-depot bus scheduling problem multi-commodity flow problem assignment problem depot workload balancing constraints

来源：评论

学校读者我要写书评

暂无评论

New auction algorithms for the assignment problem and extensions

引用

RESULTS IN CONTROL AND OPTIMIZATION 2024年 14卷

作者： Bertsekas, Dimitri Arizona State Univ Sch Comp & Augmented Intelligence Computat Decis Making Tempe AZ 85281 USA

We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by persons for objects and the attendant market equilibrium, which underlie real-life auction processes. We distinguish between two fundamentally different types of bidding mechanisms: aggressive and cooperative. Mathematically, aggressive bidding relies on a notion of approximate coordinate descent in dual space, an epsilon-complementary slackness condition to regulate the amount of descent approximation, and the idea of epsilon-scaling to resolve efficiently the price wars that occur naturally as multiple bidders compete for a smaller number of valuable objects. Cooperative bidding avoids price wars through detection and cooperative resolution of any competitive impasse that involves a group of persons. We discuss the relations between the aggressive and the cooperative bidding approaches, we derive new algorithms and variations that combine ideas from both of them, and we also make connections with other primal-dual methods, including the Hungarian method. Furthermore, our discussion points the way to algorithmic extensions that apply more broadly to network optimization, including shortest path, max-flow, transportation, and minimum cost flow problems with both linear and convex cost functions.

关键词： Linear assignment problem auction algorithm Optimal solution Duality theory

来源：评论

学校读者我要写书评

暂无评论

D2D Social Selection Relay algorithm Combined with auction Principle

引用

SENSORS 2022年第23期22卷 9265-9265页

作者： Wang, Hairui Wang, Yijun Tang, Luping Xia, Yongqiang Changchun Univ Sci & Technol Sch Elect & Informat Engn Changchun 130022 Peoples R China

In a D2D (device-to-device) communication system, this paper proposes a relay selection strategy based on social perception. Firstly, the social threshold is introduced into the D2D relay network to screen and filter the potential relay users, thus effectively reducing the detection cost. Then, an auction algorithm is used to motivate the relay users to increase their transmission power. The simulation results show that the algorithm not only improves the throughput but also reduces the probability of a system outage.

关键词： D2D social perception social threshold auction algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：