AI-Artificial Intelligence is everywhere …
even in pipe routing. A recent article illustrates that fact. Excerpts appear
below.
TIP: Find additional articles on the same topic by Googling pipe routing multi agent path finding
One result …
Multi-Agent Path Finding - Sven Koenig
idm-lab.org/slides/mapf-tutorial.pdf
Feb 7, 2017 - Task: find collision-free paths for the agents from their start to their goal .... Rapid random restarts help to solve more multi-agent path find
///////
Position Paper: From Multi-Agent Pathfinding to Pipe Routing
Gleb Belov,1 Liron Cohen,2 Maria Garcia de la Banda,1 Daniel Harabor,1 Sven Koenig, 2 XinruiWei 1
1 Monash University, Australia
2 University of Southern California 44fgleb.belov, daniel.haraborg@monash.edu, skoenig@usc.edu
Abstract
The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that many recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on abstract PR instances. We also discuss further research necessary to tackle real-world piperouting instances of interest to industry today. This opens up a new direction of industrial relevance for the MAPF research community.
Introduction
The 3D Pipe Routing (PR) problem is a common industrial problem that appears when designing the layout of industrial plants, such as oil refineries, natural gas processing stations, water treatment facilities, and the type of power plants used in ships and submarines. Designing the layout of such a plant requires finding 3D location coordinates for every piece of equipment in the plant (equipment allocation problem), and finding a 3D route for every pipe that connects two pieces of equipment (PR problem). The aim is to minimize the total cost of the plant (which can run into multi-billion dollar budgets), while ensuring safety and correct functionality. Figure 1 shows a layout for part of a natural gas plant. Differences in the quality of the final layout, can have a very significant impact on the cost of these plants, including the cost of the pipes and associated support structures, which are known to take the largest share: up to 80% of the purchased equipment cost or 20% of the fixed-capital investment (Peters and Timmerhaus, 2004). However, finding high-quality plant layouts is remarkably difficult due to the size of these plants and the complexity of the associated constraints. As a result, layouts are still designed manually, taking multiple engineers many months (or even years) to complete. This process is inefficient, costly and the results may vary in quality, since they largely depend on the experience of the piping and layout engineers. Current research into automatic plant layout commonly divides it into two phases. The first phase performs equipment allocation, that is, finds 3D positions for all equipment that minimise a total cost and satisfy all equipment constraints, such as min/max distances and maintenance access requirements. In this phase the cost of the pipes is approximated using rough measures, such as Manhattan distances. The second phase solves the PR problem, that is, finds 3D routes for all pipes connecting the (already allocated) equipment, that minimize the pipe costs (based on their length) and satisfy all pipe constraints, such as no two pipe routes collide and they are all appropriately supported. In such setting, the start and end position of each pipe is given as input (referred to as nozzles), representing the pipe’s connection to its source/target equipment.
The PR problem is similar to the 2D Multi-Agent Path Finding (MAPF) problem, which searches for collisionfree paths for several agents from given start locations to given goal locations in a known 2D environment. Thus, a solution to a MAPF instance is a set of blocked cells in x-yt space, while a solution to the corresponding PR instance is the corresponding set of blocked cells in x-y-z space. In this paper, we show how to use this similarity to apply several recently developed optimal and bounded-suboptimal MAPF algorithms to the PR problem. We also discuss the performance of some of these algorithms on different sets of PR instances. Finally, we discuss further research necessary to tackle real-world pipe-routing instances of interest to industry today. This opens up a new direction of industrial relevance for the MAPF research community.
Conclusion
In this paper we have shown that the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment, is similar to the 2D MAPF problem. This is important because it indicates that many recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. To demonstrate this, we have evaluated the success rate, solution quality and efficiency of three MAPF algorithms (CBS, ECBS(1.01) and ECBS(1.05)) in several different environments. Results show that MAPF algorithms are able to find solutions for large instances with optimal or near optimal quality. This provides strong incentives to the MAPF research community to perform the further research necessary to tackle realworld pipe-routing instances of interest to industry today.
Free full text source: https://arxiv.org/abs/1905.08412
///////
TIP: Find additional articles on the same topic by Googling pipe routing multi agent path finding
One result …
Multi-Agent Path Finding - Sven Koenig
idm-lab.org/slides/mapf-tutorial.pdf
Feb 7, 2017 - Task: find collision-free paths for the agents from their start to their goal .... Rapid random restarts help to solve more multi-agent path find
///////
Position Paper: From Multi-Agent Pathfinding to Pipe Routing
Gleb Belov,1 Liron Cohen,2 Maria Garcia de la Banda,1 Daniel Harabor,1 Sven Koenig, 2 XinruiWei 1
1 Monash University, Australia
2 University of Southern California 44fgleb.belov, daniel.haraborg@monash.edu, skoenig@usc.edu
Abstract
The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that many recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on abstract PR instances. We also discuss further research necessary to tackle real-world piperouting instances of interest to industry today. This opens up a new direction of industrial relevance for the MAPF research community.
Introduction
The 3D Pipe Routing (PR) problem is a common industrial problem that appears when designing the layout of industrial plants, such as oil refineries, natural gas processing stations, water treatment facilities, and the type of power plants used in ships and submarines. Designing the layout of such a plant requires finding 3D location coordinates for every piece of equipment in the plant (equipment allocation problem), and finding a 3D route for every pipe that connects two pieces of equipment (PR problem). The aim is to minimize the total cost of the plant (which can run into multi-billion dollar budgets), while ensuring safety and correct functionality. Figure 1 shows a layout for part of a natural gas plant. Differences in the quality of the final layout, can have a very significant impact on the cost of these plants, including the cost of the pipes and associated support structures, which are known to take the largest share: up to 80% of the purchased equipment cost or 20% of the fixed-capital investment (Peters and Timmerhaus, 2004). However, finding high-quality plant layouts is remarkably difficult due to the size of these plants and the complexity of the associated constraints. As a result, layouts are still designed manually, taking multiple engineers many months (or even years) to complete. This process is inefficient, costly and the results may vary in quality, since they largely depend on the experience of the piping and layout engineers. Current research into automatic plant layout commonly divides it into two phases. The first phase performs equipment allocation, that is, finds 3D positions for all equipment that minimise a total cost and satisfy all equipment constraints, such as min/max distances and maintenance access requirements. In this phase the cost of the pipes is approximated using rough measures, such as Manhattan distances. The second phase solves the PR problem, that is, finds 3D routes for all pipes connecting the (already allocated) equipment, that minimize the pipe costs (based on their length) and satisfy all pipe constraints, such as no two pipe routes collide and they are all appropriately supported. In such setting, the start and end position of each pipe is given as input (referred to as nozzles), representing the pipe’s connection to its source/target equipment.
The PR problem is similar to the 2D Multi-Agent Path Finding (MAPF) problem, which searches for collisionfree paths for several agents from given start locations to given goal locations in a known 2D environment. Thus, a solution to a MAPF instance is a set of blocked cells in x-yt space, while a solution to the corresponding PR instance is the corresponding set of blocked cells in x-y-z space. In this paper, we show how to use this similarity to apply several recently developed optimal and bounded-suboptimal MAPF algorithms to the PR problem. We also discuss the performance of some of these algorithms on different sets of PR instances. Finally, we discuss further research necessary to tackle real-world pipe-routing instances of interest to industry today. This opens up a new direction of industrial relevance for the MAPF research community.
Conclusion
In this paper we have shown that the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment, is similar to the 2D MAPF problem. This is important because it indicates that many recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. To demonstrate this, we have evaluated the success rate, solution quality and efficiency of three MAPF algorithms (CBS, ECBS(1.01) and ECBS(1.05)) in several different environments. Results show that MAPF algorithms are able to find solutions for large instances with optimal or near optimal quality. This provides strong incentives to the MAPF research community to perform the further research necessary to tackle realworld pipe-routing instances of interest to industry today.
Free full text source: https://arxiv.org/abs/1905.08412
///////
No comments:
Post a Comment