A Novel Method for Optimal Sensor and Actuator Placements: The “Infinite Value Algorithm”
Subject Areas : Electrical EngineeringMahdi Zavar 1 , Mohammad Shahraeini 2 , Alireza Safa 3 , Niki Manouchehri 4
1 - Department of Electrical Engineering, Faculty of Engineering, Golestan University, Gorgan, Iran
2 - Department of Electrical Engineering, Golestan University, Gorgan, Iran
3 - Department of Electrical Engineering, Golestan University, Gorgan, Iran
4 - Department of Electrical Engineering,, Golestan University, Gorgan, Iran
Keywords: Infinite value algorithm, Sensor placement, Actuator placement, Observability, Controllability,
Abstract :
Cyber-physical systems rely heavily on the functionality of sensors and actuators to operate effectively. Sensors transfer measurements from the physical part to the control and cyber part and while actuators that play the role of applying control signals to the physical part. The placement of sensors and actuators is an important issue for ensuring system’s observability and controllability. This placement should be done in way that the system remains controllable and observable with fewest number of sensors and actuators.. Minimizing the number of sensors and actuators has a significant effect on cost and energy reduction. In this study, a new approach is introduced based on the existing paths and non-existent paths between the states of a system. In the proposed approach, the non-existent paths are defined as infinite paths. The best nodes are selected as the location of sensors and actuators based on the infinite paths and their numbers. The numerical simulations illustrate that the Infinite Value Algorithm has performed better in the placements in this way that it has consumed the unique solution in less time compared the Genetic Algorithms.
[1] Bakirtzis, Georgios, Christina Vasilakopoulou, and Cody H Fleming. "Compositional Cyber-Physical Systems Modeling." arXiv preprint arXiv:2101.10484 (2021).
[2] Ho, Nicholas, Pooi-Mun Wong, Ngoc-Son Hoang, Dun-Kai Koh, Matthew Chin Heng Chua, and Chee-Kong Chui. "Cps-Based Manufacturing Workcell for the Production of Hybrid Medical Devices." Journal of Ambient Intelligence and Humanized Computing 12 (2021): 10865-79.
[3] Tavčar, Jože, Jože Duhovnik, and Imre Horváth. "From Validation of Medical Devices Towards Validation of Adaptive Cyber-Physical Systems." Journal of Integrated Design and Process Science 23, no. 1 (2019): 37-59.
[4] Castillo-Martínez, Diego Hilario, Adolfo Josué Rodríguez-Rodríguez, Adrian Soto, Alberto Berrueta, David Tomás Vargas-Requena, Ignacio R Matias, Pablo Sanchis, Alfredo Ursúa, and Wenceslao Eduardo Rodríguez-Rodríguez. "Design and on-Field Validation of an Embedded System for Monitoring Second-Life Electric Vehicle Lithium-Ion Batteries." Sensors 22, no. 17 (2022): 6376.
[5] Hu, Zhongxu, Shanhe Lou, Yang Xing, Xiao Wang, Dongpu Cao, and Chen Lv. "Review and Perspectives on Driver Digital Twin and Its Enabling Technologies for Intelligent Vehicles." IEEE Transactions on Intelligent Vehicles (2022).
[6] Li, Ning, Haiyi Sun, Xin Jing, and Zhongtang Chen. "Dynamic Modeling and Aperiodically Intermittent Strategy for Adaptive Finite-Time Synchronization Control of the Multi-Weighted Complex Transportation Networks with Multiple Delays." Chinese Physics B 30, no. 9 (2021): 090507.
[7] Wu, Jianping, and Dongping Fang. "Role of Cps in Smart Cities." Cyber-Physical Systems in the Built Environment (2020): 255-72.
[8] Cui, Yi, Feifei Bai, Tapan Saha, and Jalil Yaghoobi. "Authenticating Source Information of Distribution Synchrophasors at Intra-State Locations for Cyber-Physical Resilient Power Networks." International Journal of Electrical Power & Energy Systems 139 (2022): 108009.
[9] Khan, Izhar Ahmed, Dechang Pi, Nasrullah Khan, Zaheer Ullah Khan, Yasir Hussain, Asif Nawaz, and Farman Ali. "A Privacy-Conserving Framework Based Intrusion Detection Method for Detecting and Recognizing Malicious Behaviours in Cyber-Physical Power Networks." Applied Intelligence (2021): 1-16.
[10] Cui, Xinyue. "Cyber-Physical System (Cps) Architecture for Real-Time Water Sustainability Management in Manufacturing Industry." Procedia CIRP 99 (2021): 543-48.
[11] Liu, Yongtuo, Sara Magliacane, Miltiadis Kofinas, and Efstratios Gavves. "Graph Switching Dynamical Systems." arXiv preprint arXiv:2306.00370 (2023).
[12] Vazirgiannis, Michalis. "Gnns and Graph Generative Models for Biomedical Applications." Proceedings of the ACM Web Conference 2023, Austin, TX, USA, Association for Computing Machinery, 2023.
[13] Adamos, Konstantinos, George Stergiopoulos, Michalis Karamousadakis, and Dimitris Gritzalis. "Enhancing Attack Resilience of Cyber-Physical Systems through State Dependency Graph Models." International Journal of Information Security (2023): 1-12.
[14] Bodkhe, Umesh, Dhyey Mehta, Sudeep Tanwar, Pronaya Bhattacharya, Pradeep Kumar Singh, and Wei-Chiang Hong. "A Survey on Decentralized Consensus Mechanisms for Cyber Physical Systems." IEEE Access 8 (2020): 54371-401.
[15] Mittal, Saurabh, and Andreas Tolk. Complexity Challenges in Cyber Physical Systems: Using Modeling and Simulation (M&S) to Support Intelligence, Adaptation and Autonomy. John Wiley & Sons, 2019.
[16] Abbas, Arbab Waseem, and Safdar Nawaz Khan Marwat. "Scalable Emulated Framework for Iot Devices in Smart Logistics Based Cyber-Physical Systems: Bonded Coverage and Connectivity Analysis." IEEE Access 8 (2020): 138350-72.
[17] Fataliyev, Tahmasib Kh, and Shakir A Mehdiyev. "Integration of Cyber-Physical Systems in E-Science Environment: State-of-the-Art, Problems and Effective Solutions." International Journal of Modern Education and Computer Science 11, no. 9 (2019): 35.
[18] Colabianchi, Silvia, Francesco Costantino, Giulio Di Gravio, Fabio Nonino, and Riccardo Patriarca. "Discussing Resilience in the Context of Cyber Physical Systems." Computers & Industrial Engineering 160 (2021): 107534.
[19] Leitold, Dániel, Ágnes Vathy-Fogarassy, and János Abonyi. "Network-Based Observability and Controllability Analysis of Dynamical Systems: The Nocad Toolbox." F1000Research 8 (2019).
[20] Civera, Marco, Marica Leonarda Pecorelli, Rosario Ceravolo, Cecilia Surace, and Luca Zanotti Fragonara. "A Multi‐Objective Genetic Algorithm Strategy for Robust Optimal Sensor Placement." Computer‐Aided Civil and Infrastructure Engineering 36, no. 9 (2021): 1185-202.
[21] Dhuri, KD, and P Seshu. "Multi-Objective Optimization of Piezo Actuator Placement and Sizing Using Genetic Algorithm." Journal of sound and vibration 323, no. 3-5 (2009): 495-514.
[22] Peng, Yuhuai, Alireza Jolfaei, Qiaozhi Hua, Wen-Long Shang, and Keping Yu. "Real-Time Transmission Optimization for Edge Computing in Industrial Cyber-Physical Systems." IEEE Transactions on Industrial Informatics 18, no. 12 (2022): 9292-301.
[23] Zhou, Xin, Xiaodong Gou, Tingting Huang, and Shunkun Yang. "Review on Testing of Cyber Physical Systems: Methods and Testbeds." IEEE Access 6 (2018): 52179-94.
[24] Tutte, William Thomas. Graph Theory. Vol. 21: Cambridge university press, 2001.
[25] Shahraeini, Mohammad, Panayiotis Kotzanikolaou, and Mehrab Nasrolahi. "Communication Resilience for Smart Grids Based on Dependence Graphs and Eigenspectral Analysis." IEEE Systems Journal 16, no. 4 (2022): 6558-68.
[26] Bhunia, Pintu, Santanu Bag, and Kallol Paul. "Bounds for Eigenvalues of the Adjacency Matrix of a Graph." Journal of Interdisciplinary Mathematics 22, no. 4 (2019): 415-31.
[27] Shahraeini, Mohammad, Shahla Khormali, and Ahad Alvandi. "Optimal Pmu Placement Considering Reliability of Measurement System in Smart Grids." Paper presented at the 2022 12th International Conference on Computer and Knowledge Engineering (ICCKE), 2022.
[28] Xie, Jun, Qiguang Miao, Ruyi Liu, Wentian Xin, Lei Tang, Sheng Zhong, and Xuesong Gao. "Attention Adjacency Matrix Based Graph Convolutional Networks for Skeleton-Based Action Recognition." Neurocomputing 440 (2021): 230-39.
[29] Jungers, Raphael M, Atreyee Kundu, and WPMH Heemels. "Observability and Controllability Analysis of Linear Systems Subject to Data Losses." IEEE Transactions on Automatic Control 63, no. 10 (2017): 3361-76.
[30] Yan, Jiayuan, Bin Hu, Zhi-Hong Guan, Tao Li, and Ding-Xue Zhang. "On Controllability and Observability of a Class of Fractional-Order Switched Systems with Impulse." Nonlinear Analysis: Hybrid Systems 50 (2023): 101378.
[31] Chen, Chen, Ruiyue Peng, Lei Ying, and Hanghang Tong. "Fast Connectivity Minimization on Large-Scale Networks." ACM Transactions on Knowledge Discovery from Data (TKDD) 15, no. 3 (2021): 1-25.
[32] Sun, Wen, Junxia Guan, Jinhu Lü, Zhigang Zheng, Xinghuo Yu, and Shihua Chen. "Synchronization of the Networked System with Continuous and Impulsive Hybrid Communications." IEEE Transactions on Neural Networks and Learning Systems 31, no. 3 (2019): 960-71.
[33] Bopardikar, Shaunak D. "A Randomized Approach to Sensor Placement with Observability Assurance." Automatica 123 (2021): 109340. https://doi.org/https://doi.org/10.1016/j.automatica.2020.109340.
[34] Manohar, Krithika, J Nathan Kutz, and Steven L Brunton. "Optimal Sensor and Actuator Selection Using Balanced Model Reduction." IEEE Transactions on Automatic Control 67, no. 4 (2021): 2108-15. https://doi.org/https://doi.org/10.1109/TAC.2021.3082502.
[35] Takahashi, Shun, Yasuo Sasaki, Takayuki Nagata, Keigo Yamada, Kumi Nakai, Yuji Saito, and Taku Nonomura. "Sensor Selection by Greedy Method for Linear Dynamical Systems: Comparative Study on Fisher-Information-Matrix, Observability-Gramian and Kalman-Filter-Based Indices." IEEE Access (2023). https://doi.org/https://doi.org/10.1109/ACCESS.2023.3291415.
[36] Yamada, Keigo, Yasuo Sasaki, Takayuki Nagata, Kumi Nakai, Daisuke Tsubakino, and Taku Nonomura. "Efficient Sensor Node Selection for Observability Gramian Optimization." Sensors 23, no. 13 (2023): 5961. https://doi.org/https://doi.org/10.3390/s23135961.
[37] Shirajuddin, Talhah Mohamad, Nur Shazwani Muhammad, and Jazuri Abdullah. "Optimization Problems in Water Distribution Systems Using Non-Dominated Sorting Genetic Algorithm Ii: An Overview." Ain Shams Engineering Journal 14, no. 4 (2023): 101932.
[38]Shahraeini, Mohammad. “Modified Erdős–Rényi Random Graph Model for Generating Synthetic Power Grids.” IEEE Systems Journal. Institute of Electrical and Electronics Engineers (IEEE), 2023. https://doi.org/10.1109/jsyst.2023.3339664.
Journal of Applied Dynamic Systems and Control,Vol.7, No.1, 2024: 13-25
| 23 |
A Novel Method for Optimal Sensor and Actuator Placements: The “Infinite Value Algorithm”
Mahdi Zavar1,Mohammad Shahraeini2*, Alireza Safa3,Niki Manouchehri4
1 Department of Electrical Engineering, Golestan University, Gorgan, Iran. Email:m.zavar400@stu.gu.ac.ir
2* CorrespondingAuthor :Department of Electrical Engineering, Golestan University, Gorgan, Iran.
Email:m.shahr@gu.ac.ir
3Department of Electrical Engineering, Golestan University, Gorgan, Iran.
Email:a.safa@gu.ac.ir
4 Department of Electrical Engineering, Golestan University, Gorgan, Iran. Email: n.manouchehri400@stu.gu.ac.ir
Received: 2024.01.12; Accepted: 2024.04.03
Abstract–Cyber-physical systems rely heavily on the functionality of sensors and actuators to operate effectively. Sensors transfer measurements from the physical part to the control and cyber part and while actuators that play the role of applying control signals to the physical part. The placement of sensors and actuators is an important issue for ensuring system’s observability and controllability. This placement should be done in way that the system remains controllable and observable with fewest number of sensors and actuators.. Minimizing the number of sensors and actuators has a significant effect on cost and energy reduction. In this study, a new approach is introduced based on the existing paths and non-existent paths between the states of a system. In the proposed approach, the non-existent paths are defined as infinite paths. The best nodes are selected as the location of sensors and actuators based on the infinite paths and their numbers.The numerical simulations illustrate that the Infinite Value Algorithm has performed better in the placements in this way that it has consumed the unique solution in less time compared the Genetic Algorithms.
Keywords:Infinite value algorithm, Sensor placement, Actuator placement, Observability, Controllability.
1. Introduction
Cyber-physical systems (CPSs) integrate physical components with cyber capabilities, revolutionizing industries like electrical infrastructure and communication systems, to create a networked environment [1]. These systems also incorporate the concept of system dynamics, which means that physics and dynamics are intertwined. CPSs and networks form a pervasive computing platform that underlies many modern technologies. They are created by integrating and interconnecting physical equipment and systems from an engineering perspective and different algorithms, enabling them to influence each other. Since CPSs aim to control the dynamics of physical systems, they can be considered dynamic systems. Examples include medical devices [2, 3], communication peripherals [4], intelligent vehicles [5], transportation networks [6, 7], power generation networks [8, 9], and water distribution systems [10]. CPS is closely related to buzzwords such as the Internet of Things, Industry 4.0, Industrial Internet, and Machine-to-Machine. All of these reflect a vision of modern technology that connects the physical world with the world of information.
Graph-based algorithms can be used to analyze and model switched-mode systems [11]. A recent study proposed a new approach using graphs to model switching dynamical systems, capturing interactions between objects, and learning both intra-object and inter-object mode-switching behavior. This method has been successfully applied to model various real-world systems, from crowds of people to groups of immune cells and swarms. Additionally, graph models are gaining popularity in various fields such as social networks, knowledge graphs, and protein-protein interaction networks. Furthermore, a recent work explores the potential of graph models in the biomedical field and introduces a new framework for creating medical records as graphs while maintaining privacy [12].
1.1 CPS Challenges
CPSs pose numerous challenges, with modeling being the most crucial. Modeling helps to analyze how a system works, determine necessary criteria, and tackle other challenges confidently [13]. Other challenges include ensuring security, managing complexity, scalability, integration, and resilience of the system, which become more critical as the dimensions and size of the systems increase [14-18]. Another challenge is observability and controllability, which has recently gained attention from researchers. Observability and controllability allow for establishing a connection between the physical and cyber parts of the system through a series of equipment.
To address this challenge and control and observe a CPS, sensors and actuators must be placed correctly. Leitold and his colleagues have proposed an approach based on Tarjan's algorithm, which locates sensors by finding strongly connected components (SCC) in the system's graph. However, this approach has four significant flaws. Firstly, finding SCCs differs depending on the starting location of the algorithm. Secondly, the location of sensors in SCCs is not unique. Thirdly, the number of sensors is more than required for system observability. Finally, this approach is only used for placing sensors [19].
Using optimization algorithms such as the Genetic Algorithms (GAs) is another way to place sensors and actuators. However, these algorithms require defining the cost function and necessary conditions for execution, leading to many iterations that take a lot of time to execute. Additionally, the final answer is not unique for large systems. Moreover, these algorithms must be executed twice and separately for the placement of sensors and actuators, further complicating the placement process and increasing execution time [20, 21].
1.2Motivation and Contribution
The presented approach utilizes a graph-based method that leverages the system's structural model and adjacency matrix to identify both existing and non-existing paths between system states. While previous methods have limitations, the Infinite Value Algorithm (IVA) addresses these issues. The IVA offers several advancements, such as:
i. The simultaneous placement of sensors and actuators
ii. Achieving observability and controllability with a minimal number of sensors and actuators
iii. Unique results for sensor and actuator placement
iv. Significantly short time to reach the answers
1.3Paper Structure
To provide context for the proposed approach, Section 2 defines key concepts and terms used in the research, including state space model (SSM) and its two sets of equations: state equations and output equations. Section 3 outlines the proposed approach and provides pseudocode for its implementation. To improve the approach's effectiveness, Section 4 briefly discusses the use of GAs and related settings. To evaluate the effectiveness of the proposed approach, Section 5 presents simulations of two systems with 10 and 100 states, created using Erdős–Rényi random graphs. These simulations are evaluated by IVA and GAs, highlighting the advantages of IVA over previous methods. Finally, Section 6 presents conclusions based on the simulations.
2. Preliminaries
2.1 State Space Model
A SSM is a method for describing the behavior of a dynamic system using variables known as states. These states represent the internal state of the system, even if they cannot be observed directly, but can be inferred from available measurements. SSM consists of two sets of equations: state equations and output equations.
State equations illustrate how states change over time and are often expressed as first-order differential equations. They can be represented using matrices and vectors. For a linear time-invariant system with n state variables and m inputs, the state equations can be expressed as:
(1) |
|
(2) |
|
(3) |
|
|
(a) |
|
(b) |
Fig. 1.(a) Undirected graph, (b) Directed Graph or digraph
A path is a sequence of connected edges that allows one to move from one node to another in a graph. The length of a path is determined by the number of edges it covers. A simple path does not repeat vertices or edges, except for the initial and final vertices. In Fig. 1(a), the path is formed by two edges. Figure 2 shows a path between 4 nodes, from node 1 to node 4 with three edges.
Fig. 2.A directed path with 4 nodes
2.3Adjacency Matrix
Each graph is drawn with a matrix called adjacency matrix. This matrix shows the relationship between the states of a CPS and is a square matrix whose dimensions are equal to the number of states or system nodes [26-28].
The adjacency matrix denoted by in (4) is an matrix where each row and column corresponds to a vertex. The value of in the matrix indicates whether there is an edge between vertices and . For a directed graph, if there is a directed edge from node i to node j, then has a value of one. If there is no directed edge from vertex to vertex , is set to zero. It is important to note that the diagonal entry in the adjacency matrix indicates whether there is a self-loop at node or not. It can be set to a specified value if self-loops are allowed, or zero otherwise.
(4) |
|
(5) |
|
(6) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(7) |
|
(8) |
|
Algorithm 1.Shortest Path | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ShortestPath(): | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Require: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ensure: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1.foreach nodedo | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2.totalPath | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
end for | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sort | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Algorithm 2.Infinite Value Algorithm | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Require: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ensure: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1. findNum | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2. Call ShortestPath() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4. whiledo | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5.foreach nodedo | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6.ifth node hasn’t path to th node then | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
foreach nodedo | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ifth node has path to th nodethen | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
end if | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
end for | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
foreach nodedo | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ifth node hasn’t path to th nodethen | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
15. end if | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
16.end for | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
17.foreach do | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
18. selectBest() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
19. selectMinInf() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
20.end for | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
21.Set new from | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
22.end if | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
23.end for | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
24. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The same process is done for sensor placement | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
(9) |
|
(10) |
|
(11) |
|
(12) | Cost observability or controllability |
(13) |
Another change has been made in the GA condition and cost function so that the number of sensors and actuators can be minimized. It can be seen in (13) cost functions and theirs conditions. However, the stopping condition this time is finding the minimum number of sensors and actuators to guarantee observability and controllability.
5. Simulation and Analysis
In this section, for 10-state and 100-state systems, the directed Erdős–Rényirandom graph model is used to compare IVA and GA. We have followed the approach presented in [38] to produce random directed graphs. All simulations and results are done in MATLAB software1.The GA has been executed 10 times in such a way as to confirm the controllability and observability of the system.
5.1 The 10-state System
The first simulation is a system with 10 nodes, or a system that has 10 states in its state space model. The nodes or states of the 10-state system and their connections are expressed based on the adjacency matrix (14).
|