China
Africa
Explore chapters and articles related to this topic
Story of Robots
Published in Junichi Takeno, Self-Aware Robots, 2022
Two solutions are available: a visibility graph and configuration space. A visibility graph is a graph in which all vertices and points of tangency of a curved section of obstacles visible from all vertices and points of tangency of any other obstacles are connected by straight lines (that is, if two vertices or points of tangency can see each other, a segment is drawn between them). The configuration space method provides a technique of increasing the size of obstacles relative to the size of the robot to be used. If the robot is a cylindrical one 30 cm in diameter, for example, it can be treated as a point by increasing the girth of an obstacle by, say, 15 cm. The robot then calculates the shortest path to the goal in the visibility graph while considering itself to be a point.
Path Planning and Optimization
Published in Amit Kumar Tyagi, Niladhuri Sreenath, Handbook of Research of Internet of Things and Cyber-Physical Systems, 2022
Pranjal Paul, G. Venkata Krishna, Arpit Jain
The main advantage of a visibility graph is that it can solve small-scale problems in 2D space generating an optimal path. However, it has quadratic time complexity-O(n$$$$$2) [9] that is, the complexity is directly proportional to the square of input size (n) reducing the efficiency of the visibility graph. For higher dimension space, (non-deterministic polynomial time) NP-hard problems arise. Also, there will be a large probability of collision of vehicles with the obstacle.
Motion Planning: Recent Developments
Published in Shuzhi Sam Ge, Frank L. Lewis, Autonomous Mobile Robots, 2018
Héctor H. González-Baños, David Hsu, Jean-Claude Latombe
In 2D polygonal configuration spaces, both the visibility graph and the Voronoi diagram capture the connectivity of the space exactly: there is a collision-free path in C between two given configurations if and only if there is such a path in the corresponding graphs. So both algorithms are complete for 2D polygonal configuration spaces.
Do environmental characteristics predict spatial memory about unfamiliar environments?
Published in Spatial Cognition & Computation, 2020
Marianna Pagkratidou, Alexia Galati, Marios Avraamides
Another approach for quantifying a spatial environment is VGA, an analytic tool that measures the extent to which any point in a space is visible from any other (Turner, Doxa, O’Sullivan & Penn, 2001). To perform a VGA, a grid of points is first superimposed onto a 2D layout of a space. Then, for each point, all other points that are visible are found and a vertex is added to the graph for each. The set of visible vertices is then stored (Turner, 2001, 2007a). Several measures can then be obtained from the resulting visibility graph, including the measures of visual connectivity, visual integration and through vision. Visual connectivity is a local measure that captures the amount of space directly visible from a point, whereas visual integration of a point is a global measure that captures the number of visual steps it takes to get from that point to any other point within the system. Through vision is a local measure that captures for a grid cell the number of lines of visibility passing through that cell.
Graph-based network generation and CCTV processing techniques for fire evacuation
Published in Building Research & Information, 2021
Jack C. P. Cheng, Keyu Chen, Peter Kok-Yiu Wong, Weiwei Chen, Chun Ting Li
The prerequisite of fire evacuation navigation is to find the optimal path for fire evacuation. In recent years, researchers have come to realize how building information modelling (BIM) can aid the finding of the optimal evacuation path (Cheng et al., 2018). An evacuation path that guides an evacuee to an exit without running into any obstacles can be found if there is access to BIM for such information as details on rooms, dimensions of walls, locations of doors, etc. To find the optimal evacuation path, a graph-based network consisting of nodes and edges that connect the nodes is normally required before using shortest path finding algorithms such as Dijkstra’s algorithm (1959). The graph-based network is commonly constructed with either medial axis transform (MAT) (Lee, 2004) or visibility graph (VG) (Kim et al., 2011). For the same building, a MAT graph, which is mainly formed by the medial axes of rooms and corridors, normally contains fewer edges and requires less computing time than a VG graph, which is formed by connections between the corners of rooms (Chen & Chu, 2016). However, MAT graphs are not suitable for buildings with large open areas such as shopping malls or libraries, because the shortest paths found using medial axes may have large error compared to the real situation. For example, in the lobby of a large hotel, a customer can go straight to the exit rather than walk perpendicularly to the axis of the lobby before heading to the exit. VG can avoid any unnecessary distance in the shortest path obtained from MAT graph and provide a much shorter evacuation path. Nevertheless, the shortest paths obtained by VG are still not satisfactory, as they always pass through corners of rooms or align with walls, either of which is impractical in reality. It is preferable that the method of constructing the graph-based network inherits only the advantages but not the above-mentioned shortcomings from both MAT and VG.
Employing visibility and agent-based accessibility analysis to enhance social interactions in older adult care facilities
Published in Architectural Science Review, 2020
A spatial layout that provides older adults’ enhanced access to social spaces and encourages natural social interaction is essential to improving the quality of living for older adults in care facilities. The accessibility analysis in this study applied two agent-based simulation methods. First, syntactic agent analysis in the form of an exosomatic visual architecture (EVA) was used to investigate the accessibility of occupants based on a holistic interpretation of visibility in a given environment. In EVA, agents move based on pre-processed visual information from visibility graph analysis (Turner and Penn 2002). Visibility graphs enable a higher resolution analysis of spatial properties and deliver better predictions about movement patterns than a line-based analysis (Hillier 1996; Turner et al. 2001). The implementation of this architecture is based on Gibson’s ecological theory on a behavioural model in which human movement rules originate from a concept of affordance, which refers to the use of line-of-sight on a walkable surface (Gibson 1979). Gibson (1979) argues that people are guided by simple perception, responding directly to the affordance captured in the environment rather than any higher cognitive interpretation of the spatial environment. This theory is strongly supportive in studies evaluating the behaviours of older adults. Previous research has shown that visibility affects older adults’ social behaviours, and the use of corridors and wayfinding correlates highly with syntactic integration values (Haq 1999; Haq and Luo 2012). Older adults tend to rest at large convex spaces as they want to observe rather than to be seen (Akan, Ünlü, and Edgü 2017). In older adult care facilities, providing choices for environmental control and easy access to common areas are essential for positive users’ social status (Zeisel 1981; Hanson and Zako 2005). The space syntax methodology has certain limitations methodologically as it only takes into account the two-dimensional visibility data of a given layout. However, it has been considered as a sound methodology for predicting and understanding human behaviours in the built environment. A prior study measuring the spatial and social characteristics of older adult care facilities also employed space syntax to explore the visibility and accessibility of the care centres (Lee, Ostwald, and Lee 2017).