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

Two-person Positive Shortest Path Games Have Nash Equilibria in Pure Stationary Strategies

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Vyalyi, Mikhail MSIS & RUTCOR Business School Rutgers University 100 Rockafellar Road PiscatawayNJ08854 United States Computer Science Department Khalifa University of Science and Technology Abu Dhabi127788 United Arab Emirates of National Research University Moscow Russia Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences Russia Department of Control and Applied Mathematics Moscow Institute of Physics and Technology Moscow Russia

We prove that every finite two-person shortest path game, where the local cost of every move is positive for each player, has a Nash equilibrium (NE) in pure stationary strategies, which can be computed in polynomial time. We also extend the existence result to infinite graphs with finite out-degrees. Moreover, our proof gives that a terminal NE (in which the play is a path from the initial position to a terminal) exists provided at least one of the two players can guarantee reaching a terminal. If none of the players can do it, in other words, if each of the two players has a strategy that separates all terminals from the initial position s, then, obviously, a cyclic NE exists, although its cost is infinite for both players, since we restrict ourselves to positive games. We conjecture that a terminal NE exists too, provided there exists a directed path from s to a terminal. However, this is open. We extend our result to short paths interdiction games, where at each vertex, we allow one player to block some of the arcs and the other player to choose one of the non-blocked arcs. Assuming that blocking sets are chosen from an independence system given by an oracle, we give an algorithm for computing a NE in time O(|E|(log |V | + τ)), where V is the set of vertices, E is the set of arcs, and τ is the maximum time taken by the oracle on any *** Codes 91A05 © 2024, CC BY.

关键词： Nash equilibrium

Exploiting Robots as Healthcare Resources for Epidemics Management and Support Caregivers 10

学校读者我要写书评

暂无评论

Exploiting Robots as Healthcare Resources for Epidemics Mana...

10th Italian Workshop on Artificial Intelligence and Robotics, AIRO 2023

作者： Napoli, Christian Napoli, Christian Ponzi, Valerio Puglisi, Adriano Russo, Samuele Tibermacine, Imad Eddine Department of Computer Control and Management Engineering Sapienza University of Rome via Ariosto 25 Roma00185 Italy Institute for Systems Analysis and computer Science Italian National Research Council Via dei Taurini 19 Roma00185 Italy Department of Medical Surgical Sciences and Translational Medicine Sapienza University of Rome Via di Grottarossa 1035 Roma00189 Italy Department of Psychology Sapienza University of Rome via dei Marsi 78 Roma00185 Italy

The COVID-19 emergency has exposed the fragility of many Health Care Systems around the world. Two major critical factors have been related to the management of critical care accesses and the availability of healthcare operators. COVID-like diseases are generally transmitted by airborne pathogens that grant a high contagion rate and rapidity. Unfortunately, health operators and medical doctors are the designated first victims of such epidemics. Infected operators (symptomatic or not) must be put at rest due to the potential contagion risk for the patients. In the midst of global health catastrophes such as the COVID-19 pandemic, the healthcare sector is always looking for new ways to improve patient care while reducing the risk of disease transmission. This study takes an innovative approach to the integration of robotic technology in hospital settings in order to increase operational efficiency, protect healthcare personnel, and improve patient outcomes. This study digs into the strategic deployment of robotic resources, with an emphasis on their function in epidemic control and front-line caregiver assistance. We look at how these robots may do different duties, decreasing human-to-human contact and the possibility of viral transmission. We pave the road for a safer, more efficient, and resilient healthcare environment by using the potential of robots as important healthcare resources. © 2024 Copyright for this paper by its authors.

关键词： COVID-19

Distribution of Non-Uniform Complex of Resources in Production Systems

学校读者我要写书评

暂无评论

IFAC-PapersOnLine 2022年第10期55卷 2138-2143页

作者： Dmitry Kononov Meran Furugyan Russian State University for the Humanities Institute of Control Sciences of Russian Academy of Sciences Moscow Russia Federal Research Center Computer Science and Control of Russian Academy of Sciences Moscow Russia

The problem of planning a job complex with the use of resources of various types - renewable (performers who can differ with the productivity) and several types of non-renewable is considered. We allow interruptions, and switching from one performer to another and performing one work simultaneously by several performers. The available number of performers at different times is not constant, and their productivity may vary. A developed algorithm finds the optimal allocation of resources and builds the optimal schedule of jobs. The algorithm based on building a flow network model and modifying the packing procedure.

关键词： Optimal schedule network model renewable resources non-renewable resources group of performers packing procedure

Tiny CNN for feature point description for document analysis: approach and dataset

学校读者我要写书评

暂无评论

Computer Optics

computer Optics 2022年第3期46卷 429-435页

作者： Sheshkus, Alexander Vladimirovich Chirvonaya, Anastasiya Nikolaevna Arlazarov, Vladimir Lvovich Moscow Institute for Physics Technology Moscow Region Institutskiy per. 9 Dolgoprudny141701 Russia Institute for Systems Analysis Federal Research Center "Computer Science Control" of Russian Academy of Sciences pr. 60-letiya Oktyabrya 9 Moscow117312 Russia Smart Engines Service LLC pr. 60-letiya Oktyabrya 9 Moscow117312 Russia National University of Science Technology "MISIS" Leninskiy prospect 4 Moscow119049 Russia

In this paper, we study the problem of feature points description in the context of document analysis and template matching. Our study shows that specific training data is required for the task especially if we are to train a lightweight neural network that will be usable on devices with limited computational resources. In this paper, we construct and provide a dataset of photo and syn-thetically generated images and a method of training patches generation from it. We prove the ef-fectiveness of this data by training a lightweight neural network and show how it performs in both general and documents patches matching. The training was done on the provided dataset in comparison with HPatches training dataset and for the testing, we solve HPatches testing framework tasks and template matching task on two publicly available datasets with various documents pic-tured on complex backgrounds: MIDV-500 and MIDV-2019. © 2022, Institution of Russian Academy of sciences. All rights reserved.

关键词： Template matching

Safe Intersection Coordination with Mixed Traffic: From Estimation to control

学校读者我要写书评

暂无评论

IFAC-PapersOnLine 2023年第2期56卷 5697-5702页

作者： Xiao Chen Frank J. Jiang Vandana Narri Mustafa Adnan Jonas Mårtensson Karl H. Johansson Division of Decision and Control Systems School of Electrical Engineering and Computer Science KTH Royal Institute of Technology Stockholm Sweden Research and Development Scania CV AB 151 87 Södertälje Sweden

In this paper, we propose an integrated framework for safe intersection coordination of connected and automated vehicles (CAVs) in mixed traffic. An intelligent intersection is introduced as a central node to orchestrate state data sharing among connected agents and enable CAV to acknowledge the presence of human-driven vehicles (HDVs) beyond the line of sight of onboard sensors. Since state data shared between agents might be uncertain or delayed, we design the intelligent intersection to safely compensate for these uncertainties and delays using robust set estimation and forward reachability analysis. When the intersection receives state data from an agent, it first generates a zonotope to capture the possible measurement noise in the state estimate. Then, to compensate for communication and processing delays, it uses forward reachability analysis to enlarge the set to capture all the possible states the agent could have occupied throughout the delays. Finally, using the resulting set as the initial condition, a distributed model predictive control onboard the CAV will plan an invariant safe motion by considering the worst-case behavior of human drivers. As a result, the vehicle is guaranteed to be safe while driving through the intersection. A prototype of our proposed framework is implemented using the Small-Vehicles-for-Autonomy (SVEA) platform. The effectiveness of our framework is evaluated in experiments based on a challenging scenario where the collision would have occurred without efficient coordination.

关键词： Intelligent Transportation Systems Autonomous vehicles Multi-vehicle systems Sensor integration and perception Decentralized control and systems

Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Pitanov, Yelisey Skrynnik, Alexey Andreychuk, Anton Yakovlev, Konstantin Panov, Aleksandr Moscow Institute of Physics and Technology Moscow Russia AIRI Moscow Russia Federal Research Center "Computer Science and Control" the Russian Academy of Sciences Moscow Russia

In this work we study a well-known and challenging problem of Multi-agent Pathfinding, when a set of agents is confined to a graph, each agent is assigned a unique start and goal vertices and the task is to find a set of collision-free paths (one for each agent) such that each agent reaches its respective goal. We investigate how to utilize Monte-Carlo Tree Search (MCTS) to solve the problem. Although MCTS was shown to demonstrate superior performance in a wide range of problems like playing antagonistic games (e.g. Go, Chess etc.), discovering faster matrix multiplication algorithms etc., its application to the problem at hand was not well studied before. To this end we introduce an original variant of MCTS, tailored to multi-agent pathfinding. The crux of our approach is how the reward, that guides MCTS, is computed. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior, while leaving them freedom to get off the track if it is needed to avoid collisions. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure. Empirically we show that the suggested method outperforms the baseline planning algorithm that invokes heuristic search, e.g. A*, at each re-planning step. © 2023, CC BY.

关键词： Multi agent systems

Improved Anonymous Multi-Agent Path Finding Algorithm

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Ali, Zain Alabedeen Yakovlev, Konstantin Moscow Institute of Physics and Technology Moscow Russia Federal Research Center for Computer Science and Control The Russian Academy of Sciences Moscow Russia AIRI Moscow Russia

We consider the Anonymous Multi-Agent Path-Finding (AMAPF) problem where the agents are confined to a graph, a set of goal vertices is given, and each of these vertices has to be reached by some agent. The problem is to find an assignment of the goals to the agents as well as the collision-free paths, and we seek to find the solution with the minimal makespan. A well-established approach to solving this problem is by reducing it to a special type of graph search problem, i.e. to the problem of finding a maximum flow on an auxiliary graph induced by the input one. The size of the former graph may be very large, and the search on it may become a bottleneck. To this end, we suggest a specific search algorithm that leverages the idea of exploring the search space not through considering separate search states but rather bulks of them simultaneously. That is, we implicitly compress, store, and expand bulks of the search states as single states, reducing the runtime and memory consumption. Empirically, the resultant AMAPF solver demonstrates superior performance compared to the state-of-the-art competitor and is able to solve all publicly available MAPF instances from the well-known MovingAI benchmark in less than 30 seconds. Copyright © 2023, The Authors. All rights reserved.

关键词： Benchmarking

Numerical Modeling of Oxygen Diffusion in Tissue Spheroids Undergoing Fusion Using Functional Representation and Finite Volumes

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vilinski-Mazur, Katherine Kirillov, Bogdan Rogozin, Oleg Kolomenskiy, Dmitry Center for Materials Technologies Skolkovo Institute of Science and Technology Moscow Russia Center for Precision Genome Editing and Genetic Technologies for Biomedicine Institute of Gene Biology Russian Academy of Sciences Moscow Russia Federal Research Center"Computer Science and Control" Russian Academy of Sciences Moscow Russia

A three-dimensional cell culture called a spheroid serves as a foundational entity in a wide variety of modern tissue engineering applications, including 3D-bioprinting and preclinical drug testing. Lack of oxygen within tissue spheroids hinders metabolism of cells and eventually leads to cell death. Prevention of necrosis is crucial to success of tissue engineering methods and such prevention requires estimation of cell viability in the spheroid. We propose a novel approach for numerical modeling of diffusion in tissue spheroids during their fusion. The approach is based on numerical solutions of partial differential equations and the application of Function Representations (FRep) framework for geometric modeling. We present modeling of oxygen diffusion based on meshes derived from the geometry of fusing spheroids, a method for selecting optimal spheroid size, and several statistics for estimating cellular viability. Our findings provide insights into oxygen diffusion in three-dimensional cell cultures thus improving the robustness of biotechnological methods that employ tissue spheroids. © 2025, CC BY.

关键词： Cell death

Evaluation of Safety Constraints in Autonomous Navigation with Deep Reinforcement Learning ?

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Angulo, Brian Gorbov, Gregory Panov, Aleksandr Yakovlev, Konstantin Moscow Institute of Physics and Technology Dolgoprudny Russia AIRI Moscow Russia Federal Research Center for Computer Science Control Russian Academy of Sciences Moscow Russia

While reinforcement learning algorithms have had great success in the field of autonomous navigation, they cannot be straightforwardly applied to the real autonomous systems without considering the safety constraints. The later are crucial to avoid unsafe behaviors of the autonomous vehicle on the road. To highlight the importance of these constraints, in this study, we compare two learnable navigation policies: safe and unsafe. The safe policy takes the constraints into account, while the other does not. We show that the safe policy is able to generate trajectories with more clearance (distance to the obstacles) and makes less collisions while training without sacrificing the overall performance. Copyright © 2023, The Authors. All rights reserved.

关键词： Reinforcement learning