Spelling suggestions: "subject:"pathfinding"" "subject:"atfinding""
11 |
Synergistic Strategies in Multi-Robot Systems: Exploring Task Assignment and Multi-Agent PathfindingBai, Yifan January 2024 (has links)
Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.
|
12 |
Multi-agentní hledání cest / Multi-agent Path FindingŠvancara, Jiří January 2020 (has links)
Multi-Agent Path Finding (MAPF) is the task to find efficient collision-free paths for a fixed set of agents. Each agent moves from its initial location to its desired destination in a shared environment represented by a graph. The classical definition of MAPF is very simple and usually does not reflect the real world accurately. In this thesis, we try to add several attributes to the MAPF definition so that we overcome this shortcoming. This is done in several steps. First, we present an approach on how to model and solve MAPF via reduction to Boolean satisfiability using Picat programming language. This provides us with a useful model that can be easily modified to accommodate additional constraints. Secondly, we modify MAPF to portray a more realistic world. Specifically, we allow new agents to enter the shared environment during the execution of the found plan, and we relax the requirement on the homogeneousness of the shared environment. Lastly, we experimentally verify the applicability of the novel models on real robots in comparison with the classical MAPF setting.
|
13 |
Multi-agent route planning for uncrewed aircraft systems operating in U-space airspaceAyoub, Yohan January 2023 (has links)
Society today brings a high pace development and demand of Artificial intelligence systems as well as robotics. To further expand and to take one step closer to have Unmanned Aerial Vehicles (UAVs) working in the cities, the European Union Aviation Safety Agency launched a project that introduces U-space airspace, an airspace where UAVs, for instance, are allowed to operate for commercial services.The problems defined for U-space airspace resemble problems defined in the area of multi-agent path finding, such as scaling and traffic etc., resulting an interest to research whether MAPF-solutions can be applied to U-space scenarios. The following thesis extends the state-of-the-art MAPF-algorithm Continuous-time Conflict based search (CCBS) to handle simplified U-space scenarios, as well as extend other A*-based algorithms, such as a version of the Receding Horizon Lattice-based Motion Planning named Extended Multi-agent A* algorithm with Wait-Time (EMAWT) and an extended A* named Extended Multi-agent A* algorithm (EMA) to handle them. Comparisons of the three algorithms resulted in the EMAWT being the most reliable and stable solution throughout all tests, whilst for fewer agents, the CCBS being the clear best solution.
|
14 |
Inteligentní řízení ve strategických hrách / Rational Thinking in Strategic GamesKnotek, David Unknown Date (has links)
The target of this work is a creation of simple strategic game with distinct signs of artificial intelligence. Artificial intelligence will be in project represented on three levels, managerial (global), robotically (local) and assist (associated). In the next phase of the project will be the main attention targeted on graphical side of game, 2D simulator of play, graphical interface a resulting deployment the game. The game will be implemented in language C++, which provide sufficient comfort, and may be used multi-platformly.
|
15 |
Visualization of Ant Pheromone Based Path FollowingSutherland, Benjamin T. 2009 December 1900 (has links)
This thesis develops a simulation and visualization of a path finding algorithm based on
ant pheromone paths created in 3D space. The simulation is useful as a demonstration of
a heuristic approach to NP-complete problems and as an educational tool for
demonstrating how ant colonies gather food. An interactive real time 3D visualization is
built on top of the simulation. A graphical user interface layer allows user interaction
with the simulation and visualization.
|
16 |
Dinaminių kelio paieškos algoritmų tyrimas / Analysis of dynamic path finding algorithmsChabibulin, Linar 26 August 2013 (has links)
Dinaminiai kelio paieškos algoritmai apjungia euristinės ir plečiamos (angl. incremental) paieškos metodus, sprendžiant eiles panašių paieškos uždavinių tiek žinant visą informaciją apie aplinką, tiek neturint jokios informacijos. Yra trys plečiamą paiešką naudojančių algoritmų klasės. Šiame darbe pateikiama trumpa dinaminių kelio paieškos algoritmų, naudojančių plečiamos paieškos metodus analizė. Pagrindinis darbo tikslas – visų trijų plečiamos paieškos klasių algoritmų, kuriuos naudojant gaunamas optimalus kelio paieškos sprendinys aplinkose, kur perėjimų tarp viršūnių svoriai gali didėti ir mažėti, palyginimas. Algoritmai lyginami trijose skirtingose situacijose: stacionarioje, judėjimo link tikslo (angl. goal – directed) bei judančio taikinio (angl. moving – target). Tyrimo rezultatai parodė, jog A* ir FSA* nepasiekiamų viršūnių kiekiui esant ~16000 yra ~23,6% našesni už GAA* ir trečios plečiamos klasės algoritmus, o pasiekiamumą keičiančių viršūnių kiekiui esant ~8000 – 42,3%. Nepasiekiamų viršūnių kiekiui kintant nuo 1000 iki 16000 trečios plečiamos klasės algoritmai yra vidutiniškai ~58,7% našesni už GAA* ir ~54% našesni už A* ir FSA*. Pasiekiamumą keičiančių viršūnių kiekiui kintant nuo 500 iki 8000 trečios plečiamos klasės algoritmai yra vidutiniškai ~69,3% našesni už GAA* ir ~47,8% našesni už A* ir FSA*. / Dynamic path finding algorithms combine heuristic and incremental search methods to solve a series of similar search tasks in both known and unknown environments. There are three classes of incremental search algorithms. In this document we provide a brief summary of dynamic path finding algorithms, that uses incremental search methods, but its main focus is on comparing main algorithms of all three incremental classes, that are guaranteed to give optimal solution in environment where action costs can increase and decrease over time, and showing their strong and weak sides. The algorithms are compared in three different situations: stationary, goal – directed and moving – target. At the end of the document conclusions are given based on performed work. In this paper, research showed that A* and FSA* are ~23,6% more efficient than GAA* and third incremental class algorithms when the amount of untraversable cells is ~16000 and ~42,3% more efficient when the amount of traversability changing cells is ~8000. When the amount of untraversable cells is between 1000 and 16000, the third incremental class algorithms are ~58,7% more efficient than GAA* and ~54% – than A* and FSA*. When the amount of traversability changing cells is between 500 and 8000, the third incremental class algorithms are ~69,3% more efficient than GAA* and ~47,8% – than A* and FSA*.
|
17 |
Online visual merchandising : På e-handelssidor riktade mot den svenska marknaden / Online visual merchandising – Of web sites targeted at the Swedish marketBerggren, Matilda, Nordin, Klara January 2015 (has links)
År 2014, var kläder och skor två av de varukategorier som resulterade i flest transaktioner online, i Sverige. Till följd av att e-handeln växer, behöver företag inom modeindustrin utveckla sin visual merchandising online, så att den är lika effektiv som i fysiska butiker. De amerikanska forskarna Ha, Kwon och Lennon (2007) utvecklade i en studie en taxonomi där de undersökte visual merchandsing-element på den koreanska och amerikanska e-handelsmarknaden. Syftet med denna studie är att testa den taxonomi som Ha et al. (2007) utvecklade, på e-handelssidor riktade mot den svenska marknaden. Resultatet jämförs med den tidigare studien av Ha et al. (2007), följaktligen e-handelssidor på den koreanska och amerikanska marknaden. Detta utförs genom att undersöka om de visual merchandsing-element som Ha et al. (2007) identifierade återfinns på e-handelssidor riktade mot den svenska marknaden, samt om det finns nya visual merchandising-element som kan identifieras på e-handelssidor riktade mot den svenska marknaden. Som metod användes en innehållsanalys där online visual merchandsing-teman studerades på 50 e-handelssidor riktade mot den svenska marknaden. De teman, med underliggande element, som analyserades var navigering, e-handelsmiljön och produktpresentation. Utöver dessa teman lades ytterligare ett tema till, från en studie gjord av Park och Stoel (2002); information. Flertalet andra element observerades som inte fanns med i den tidigare taxonomin av Ha et al. (2007) och dessa adderades till studien. Resultatet visade att vissa av elementen inom online visual merchandsing på den svenska marknaden skiljde sig från de resultat Ha et al. (2007) presenterade i sin studie / In 2014, apparel and shoes was two of the product categories that resulted in most transactions online in Sweden. As a result of the growing interest in e-commerce, companies in the fashion industry needs to develop visual merchandising strategies that can function just as well online as the ones in physical stores. In a study made by the American researchers Ha, Kwon and Lennon (2007), a taxonomy was developed in order to examine visual merchandising elements of apparel retail websites in Korea and The US. The purpose of this study is to test the taxonomy created by Ha et al. (2007) on websites targeted at the Swedish market This will be done by addressing the questions at issue; to examine if the visual merchandising elements that Ha et al. (2007) identified can be found on the web sites in this study and to examine whether there are new elements to identify on the web sites targeted at the Swedish market. A content analysis was used to examine online visual merchandising-themes on 50 Swedish e-commerce sites. The themes analysed, with underlying elements, was environment, manner of presentation, path finding. In addition to these themes another one was added from a study made by Park and Stoel (2002), information. During the analysis several elements that was not included in the previous studies was discovered. These were also added to the taxonomy developed in this study. The findings of the study showed that some of the online visual merchandsing-elements differed on the Swedish market compared to previous studies. Also as mentioned, the taxonomy was further developed. This thesis will henceforth be written in Swedish.
|
18 |
Network Centrality Measures And Their ApplicationsSudarshan, S R 09 1900 (has links) (PDF)
Study of complex networks by researchers from many disciplines has provided penetrating insights on various complex systems. A study of the world wide web from a network theoretic perspective has led to the design of new search engines [65]. The spread of diseases is now better understood by analyzing the underlying social network [26]. The study of metabolic networks, protein-protein interaction networks and the transcriptional regulatory networks with graph theoretic rigor, has led to the growing importance of an interdisciplinary approach [71].
Network centrality measures, which has been of interest to the social scientists, from as long as 1950 [13], is today studied extensively in the framework of complex networks. The thesis is an investigation on understanding human navigation with a network analytic approach using the well established and widely used centrality measures. Experiments were conducted on human participants to observe how people navigate in a complex environment. We made human participants way-find a destination from a source on a complex network and analyzed the paths that were taken. Our analysis established a fact that the learning process involved in navigating better in an unknown network boils down to learning certain strategic locations on the network.
The vertices in the paths taken by the participants, when analyzed using the available centrality measures, enabled us to conclude experimentally that humans are naturally inclined to learn superior ranked vertices to navigate better and reach their intended destination. Our experiments were based on a word game called the word-morph. A generalized version of the experiment was conducted on a 6x6 photo collage with an underlying network hidden from the participant. A detailed analysis of the above experiment established a fact that, when humans are asked to take a goal-directed path, they were prone to take a path that passed through landmark nodes in the network. We call such paths center-strategic.
We then present an algorithm that simulates the navigational strategy adopted by humans. We show empirically that the algorithm performs better than naive random walk based navigational techniques. We observe that the algorithm produces rich center-strategic paths on scale-free networks. We note that the effectiveness of the algorithm is highly dependent on the topology of the network by comparing its functionality on Erdos-Renyi networks and Barabasi-Albert networks.
Then we discuss a lookahead algorithm to compute betweenness centrality in networks under vertex deletion operations. We show that the widely used Brandes algorithm can be modified to a lookahead version. We show that our proposed algorithm performs better than recomputing the betweenness centrality values in the vertex deleted graph. We show that our method works 20% faster than the Brandes algorithm.
|
19 |
Volitelné aktivity v rozvrhování / Optional Activities in SchedulingVlk, Marek January 2021 (has links)
Scheduling allocates scarce resources to activities such that certain constraints are satisfied and specific objectives are optimized. The activities to be executed are com- monly known or determined a priori in the planning stage. To improve the flexibility of scheduling systems, the concept of optional activities was invented. Optional activities are those activities whose presence in the resulting schedule is to be decided. Rather than determining which activities need to be executed and scheduling them in two consecu- tive phases, flexibility and efficiency can be improved significantly when both activity selection and time allocation are integrated within the same solver. Such an approach was implemented in a few Constraint Programming solvers and manifested great perfor- mance on multiple scheduling problems. In this thesis, we apply the concept of optional activities to scheduling problems that do not seem to involve optional activities, such as the production scheduling problem with sequence-dependent non-overlapping setups, but also on problems beyond the scheduling domain, such as the multi-agent path finding problem and its extension with weighted and capacitated arcs. 1
|
20 |
A Flexible Infrastructure for Multi-Agent SystemsSorensen, Gerrit Addison N 02 July 2005 (has links) (PDF)
Multi-Agent coordination and control has been studied for a long time, but has recently gained more interest because of technology improvements allowing smaller, more versatile robots and other types of agents. To facilitate multi-agent experiments between heterogeneous agents, including robots and UAVs, we have created a test-bed with both simulation and hardware capabilities. This thesis discusses the creation of this unique, versatile test-bed for multi-agent experiments, also a unique graph creation algorithm, and some experimental results obtained using the test-bed.
|
Page generated in 0.046 seconds