42 research outputs found
Knowledge, Belief, and Noisy Sensing in the Situation Calculus
No full textKnowledge, Belief, and Noisy Sensing in the Situation Calculus Patricio D. Simari Master of Science Graduate Department of Computer Science University of Toronto 2004 The extension to the situation calculus presented by Bacchus et al. formalizes the concept of noisy actions and shows how an agent can update its beliefs, which are modeled probabilistically, when relying on noisy sensors and e#ectors. The extensions of Scherl and Levesque and Shapiro et al. also model knowledge and belief. While assuming noiseless actions and dealing with boolean beliefs, these frameworks support properties of knowledge and belief such as introspection about current and past beliefs. Here, it is shown how such properties of belief can be formalized and supported in the probabilistic Bacchus et al. extension. In addition, the concept of sensor coarseness is introduced and it is shown how it can be modeled in the Bacchus et al. framework. Finally, it is shown that the Bacchus et al. framework can function in a way which is equivalent to using conditional probability densities to combine noisy sensor readings
Preface
No full textThe FoIKS symposia provide a biennial forum for presenting and discussing theoretical and applied research on information and knowledge systems. The goal is to bring together researchers with an interest in this subject, share research experiences , promote collaboration, and identify new issues and directions for future research. Another characteristic of the FoIKS symposia is that they are a forum for intensive discussions. Speakers are given ample time to present their results, expound relevant background information, and put their research into context. Furthermore, participants are asked in advance to prepare a first response to a contribution of another author in order to initiate discussion. FoIKS 2016 solicited original contributions on foundational aspects of information and knowledge systems. This included submissions that apply ideas, theories or methods from specific disciplines to information and knowledge systems. Examples of such disciplines are discrete mathematics, logic and algebra, model theory, information theory, complexity theory, algorithmics and computation, statistics, and optimization
Discrete Morse versus Watershed Decompositions of Tessellated Manifolds
No full textWith improvements in sensor technology and simulation methods, datasets are growing in size, calling for the investigation of efficient and scalable tools for their analysis. Topological methods, able to extract essential features from data, are a prime candidate for the development of such tools. Here, we examine an approach based on discrete Morse theory and compare it to the well-known watershed approach as a means of obtaining Morse decompositions of tessellated manifolds endowed with scalar fields, such as triangulated terrains or tetrahedralized volume data. We examine the theoretical aspects as well as present empirical results based on synthetic and real-world data describing terrains and 3D scalar fields. We will show that the approach based on discrete Morse theory generates segmentations comparable to the watershed approach while being theoretically sound, more efficient with regard to time and space complexity, easily parallelizable, and allowing for the computation of all descending and ascending i-manifolds and the topological structure of the two Morse complexes
Towards Combined Task and Motion Planning for Autonomous Underwater Vehicles
No full textDegree Awarded: Ph.D. Electrical Engineering and Computer Science. The Catholic University of AmericaIn oceanic research and development, autonomous underwater vehicles (AUVs) provide scientists with the ability to augment expensive manned operations at a lower cost while simultaneously exploring regions that were previously inaccessible to scientists. While the cost of these AUVs is often nontrivial, the ability to autonomously sample data from varying regions over extended time periods removes the necessity of human operations which require much higher overhead costs. Scientists are now leveraging the unique abilities of AUVs to explore new environments, scientists are now starting to use AUVs to perform sophisticated missions in deep ocean environments, under the polar ice caps, or throughout dangerous minefields in the littoral. The success of these missions, however, depends on the ability of the AUV to autonomously perform complex tasks.Toward this goal, this dissertation seeks to enhance the capabilities of AUVs so that they are able to autonomously plan the high-level actions and the low-level motions needed to accomplish complex missions. A framework is developed which makes it possible to specify such missions in a structured language resembling English, and it automatically plans the actions and motions that the AUV needs to execute in order to accomplish the mission. The mission-specification language is grounded in well-established logical formalisms such as Regular Languages and Linear Temporal Logic. The inherent structure of the mission-specification language makes it possible to construct sophisticated mission such as exploring unknown areas, searching for objects of interest, or collecting data. In doing so, the framework alleviates the burden imposed on human operators who currently need to manually input highly detailed mission specifications into multiple configuration files, which increases the risk for mission failure due to human error. Instead, the framework makes it possible for the human operators to specify the missions in an easy-to-use, structured language.The technical contribution of the dissertation stems from a novel treatment of the combined mission and motion-planning problem as a hybrid search over discrete and continuous layers. Leveraging advances in AI and Robotics, a hybrid-planning framework is developed which combines high-level AI mission planning with low-level sampling-based motion planning. High-level planning, which operates over a discrete and abstract layer, breaks down the overall mission into a sequence of tasks. Sampling-based motion planning conducts a search over the feasible motions of the AUV in order to compute a trajectory that enables the AUV to accomplish each task. When sampling-based motion planning fails to make progress it requests another high-level plan from the AI planning layer. This interplay between high-level discrete planning and sampling-based motion planning is crucial to the success of the framework.The hybrid framework can be used with any AUV. Extensive experiments have been conducted with high-fidelity simulators and real AUVs, such as OceanServer Iver2 AUV and Reliant Bluefin-21 AUV. The experimental results show the ability of the approach to effectively plan collision-free and dynamically-feasible trajectories that enable the AUV to carry out sophisticated missions, such as inspection of numerous areas, data collection, and reacquisition and identification in Mine Countermeasures. The success of the hybrid framework highlight the potential of the approach to enhance the autonomy of AUVs, making it possible to carry out sophisticated missions at a lower operational cost
Hierarchical mesh segmentation editing through rotation operations
No full textAbstract. Hierarchical and multi-resolution models are well known tools used in may application domains for representing an object at varying levels of detail. In the case of segmentations computed on a mesh, a hierarchical model can be structured as a binary tree representing the hierarchy of the region merging operations performed on the original segmentation for reducing its resolution. In this paper, we address the problem of modifying a hierarchical segmentation in order to augment its expressive power. We adapt two well-known operators defined for modifying binary trees, namely left and right rotation, to the case of hierarchical segmentations. Such operators are then applied to modify-ing a given hierarchy based on a user-defined function and based on a user-defined segmentation.
Algorithms in 3D Shape Segmentation
No full textSurfaces in 3D are often represented by polygonal meshes and point clouds obtained from 3D modeling tools or acquisition processes such as laser range scanning. While these formats are very flexible and allow the representation of a wide variety of shapes, they are rarely appropriate in their raw form for the range of applications that benefit from their use. Their decomposition into simpler constituting parts is referred to as shape segmentation, and its automation remains a challenging area within computer science.
We will present and analyze different aspects of shape segmentation. We begin by looking at useful segmentation criteria and present a categorization of current methods according to which type of criteria they address, dividing them into affinity-based, model-fitting, and property-based approaches.
We then present two algorithmic contributions in the form of a model-based and a property-based segmentation approaches. These share the goals of automatically finding redundancy in a shape and propose shape representations that leverage this redundancy to achieve descriptive compactness. The first is a method for segmenting a surface into piece-wise ellipsoidal parts, motivated by the fact that most organic objects and many manufactured objects have large curved areas. The second is an algorithm for robustly detecting global and local planar-reflective symmetry and a hierarchical segmentation approach based on this detection method.
We note within these approaches the variation in segmentations resulting from different criteria and propose a way to generalize the segmentation problem to heterogenous criteria. We introduce a framework and relevant algorithms for multi-objective segmentation of 3D shapes which allow for the incorporation of domain-specific knowledge through multiple objectives, each of which refers to one or more segmentation labels. They can assert properties of an individual part or they can refer to part interrelations. We thus cast the segmentation problem as an optimization minimizing an aggregate objective function which combines all objectives as a weighted sum.
We conclude with a summary and discussion of the contributions presented, lessons learned, and a look at the open questions remaining and potential avenues of continued research.Ph
Extraction and Remeshing of Ellipsoidal Representations From Mesh Data
No full textDense 3D polygon meshes are now a pervasive product of various modelling and scanning processes that need to be subsequently processed and structured appropriately for various applications. In this paper we address the restructuring of dense polygon meshes using their segmentation based on a number of ellipsoidal regions. We present a simple segmentation algorithm where connected components of a mesh are fit to ellipsoidal surface regions. The segmentation of a mesh into a small number of ellipsoidal elements makes for a compact geometric representation and facilitates efficient geometric queries and transformations. We also contrast and compare two polygon remeshing techniques based on the ellipsoidal surfaces and the segmentation boundaries
Knowledge, belief, and noisy sensing in the situation calculus
No full textThe extension to the situation calculus presented by Bacchus et al. formalizes the concept of noisy actions and shows how an agent can update its beliefs, which are modeled probabilistically, when relying on noisy sensors and effectors. The extensions of Scherl and Levesque and Shapiro et al. also model knowledge and belief. While assuming noiseless actions and dealing with boolean beliefs, these frameworks support properties of knowledge and belief such as introspection about current and past beliefs. Here, it is shown how such properties of belief can be formalized and supported in the probabilistic Bacchus et al. extension. In addition, the concept of sensor coarseness is introduced and it is shown how it can be modeled in the Bacchus et al. framework. Finally, it is shown that the Bacchus et al. framework can function in a way which is equivalent to using conditional probability densities to combine noisy sensor readings.M.Sc
