String Tightening as a Self-Organizing Phenomenon: Computation of Shortest Homotopic Path, Smooth Path, and Convex Hull.

Published on Dec 11, 2020in arXiv: Artificial Intelligence
· DOI :10.1109/TNN.2007.891192
Bonny Banerjee11
Estimated H-index: 11
Sources
Abstract
The phenomenon of self-organization has been of special interest to the neural network community for decades. In this paper, we study a variant of the Self-Organizing Map (SOM) that models the phenomenon of self-organization of the particles forming a string when the string is tightened from one or both ends. The proposed variant, called the String Tightening Self-Organizing Neural Network (STON), can be used to solve certain practical problems, such as computation of shortest homotopic paths, smoothing paths to avoid sharp turns, and computation of convex hull. These problems are of considerable interest in computational geometry, robotics path planning, AI (diagrammatic reasoning), VLSI routing, and geographical information systems. Given a set of obstacles and a string with two fixed terminal points in a two dimensional space, the STON model continuously tightens the given string until the unique shortest configuration in terms of the Euclidean metric is reached. The STON minimizes the total length of a string on convergence by dynamically creating and selecting feature vectors in a competitive manner. Proof of correctness of this anytime algorithm and experimental results obtained by its deployment are presented in the paper.
References26
Newest
#1Bonny Banerjee (U of M: University of Memphis)H-Index: 11
#2B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
Most of the emphasis in path planning, a topic of much interest in several domains, has been on finding the optimal path or at most k optimal paths. However, in domains such as adversarial planning, one of the agents might deliberately take less optimal paths to confuse the opponent, and by the same token an agent, for inferring opponent's intent, has to consider all possible paths that the opponent might take. We introduce the notion of representative paths in free space (2D) and study the prob...
10 CitationsSource
#1Bonny Banerjee (OSU: Ohio State University)H-Index: 11
#2B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
Diagrammatic reasoning (DR) is pervasive in human problem solving as a powerful adjunct to symbolic reasoning based on language-like representations. The research reported in this paper is a contribution to building a general purpose DR system as an extension to a soar-like problem solving architecture. The work is in a framework in which DR is modeled as a process where subtasks are solved, as appropriate, either by inference from symbolic representations or by interaction with a diagram, i.e.,...
9 CitationsSource
#1Bonny Banerjee (OSU: Ohio State University)H-Index: 11
#2B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
Diagrammatic reasoning (DR) requires perceiving information from a diagram and modifying/creating objects in a diagram according to problem solving needs. The perceptions and actions in most DR systems are hand-coded for the specific application. The absence of a general framework for executing perceptions/actions poses as a major hindrance to using them opportunistically. Our goal is to develop a framework for executing a wide variety of specified perceptions and actions across tasks/domains wi...
9 CitationsSource
The phenomenon of self-organization has been of special interest to the neural network community throughout the last couple of decades. In this paper, we study a variant of the self-organizing map (SOM) that models the phenomenon of self-organization of the particles forming a string when the string is tightened from one or both of its ends. The proposed variant, called the string tightening self-organizing neural network (STON), can be used to solve certain practical problems, such as computati...
5 CitationsSource
#1B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
#2Bonny Banerjee (OSU: Ohio State University)H-Index: 11
Diagrammatic reasoning (DR) is pervasive in human problem solving as a powerful adjunct to symbolic reasoning based on language-like representations. However, Artificial Intelligence is overwhelmingly based on symbolic representations, with proportionately scant attention to diagrams. This dissertation is a contribution to building artificial agents that can create and use diagrams as part of their problem solving. The work is in a framework in which DR is modeled as a process in which subtasks ...
8 Citations
3 CitationsSource
#1Howie ChosetH-Index: 3
#1Howie ChosetH-Index: 66
Last. Jean-Claude LatombeH-Index: 79
view all 2 authors...
Robot motion planning has become a major focus of robotics. Research findings can be applied not only to robotics but to planning routes on circuit boards, directing digital actors in computer graphics, robot-assisted surgery and medicine, and in novel areas such as drug design and protein folding. This text reflects the great advances that have taken place in the last ten years, including sensor-based planning, probabalistic planning, localization and mapping, and motion planning for dynamic an...
1,708 Citations
Jan 1, 2005 in AAAI (National Conference on Artificial Intelligence)
#1B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
#2Unmesh Kurup (OSU: Ohio State University)H-Index: 10
Last. Bonny Banerjee (OSU: Ohio State University)H-Index: 11
view all 3 authors...
This paper explores the idea that the cognitive state during problem solving diagrams is bi-modal, one of whose components is the traditional predicate-symbolic representation composed of relations between entities in the domain of interest, while a second component is an internal diagrammatic representation. In parallel with the operators in the symbolic representation that are based on symbol matching and inferencing, there is a set of operators in the diagrammatic component that apply percept...
11 Citations
#1B. Chandrasekaran (OSU: Ohio State University)H-Index: 52
#2Unmesh Kurup (OSU: Ohio State University)H-Index: 10
Last. Robert Winkler (ARL: United States Army Research Laboratory)H-Index: 7
view all 5 authors...
In problem solving a goal/subgoal is either solved by generating needed information from current information, or further decomposed into additional subgoals. In traditional problem solving, goals, knowledge, and problem states are all modeled as expressions composed of symbolic predicates, and information generation is modeled as rule application based on matching of symbols. In problem solving with diagrams on the other hand, an additional means of generating information is available, viz., by ...
38 CitationsSource
#1Sergei Bespamyatnikh (UTD: University of Texas at Dallas)H-Index: 4
We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160-169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411-423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: ...
50 CitationsSource
Cited By0
Newest