Matching Items (32)
Filtering by
- All Subjects: artificial intelligence
- Creators: Lee, Joohyung
- Creators: Berman, Spring
Description
Action language C+ is a formalism for describing properties of actions, which is based on nonmonotonic causal logic. The definite fragment of C+ is implemented in the Causal Calculator (CCalc), which is based on the reduction of nonmonotonic causal logic to propositional logic. This thesis describes the language of CCalc in terms of answer set programming (ASP), based on the translation of nonmonotonic causal logic to formulas under the stable model semantics. I designed a standard library which describes the constructs of the input language of CCalc in terms of ASP, allowing a simple modular method to represent CCalc input programs in the language of ASP. Using the combination of system F2LP and answer set solvers, this method achieves functionality close to that of CCalc while taking advantage of answer set solvers to yield efficient computation that is orders of magnitude faster than CCalc for many benchmark examples. In support of this, I created an automated translation system Cplus2ASP that implements the translation and encoding method and automatically invokes the necessary software to solve the translated input programs.
ContributorsCasolary, Michael (Author) / Lee, Joohyung (Thesis advisor) / Ahn, Gail-Joon (Committee member) / Baral, Chitta (Committee member) / Arizona State University (Publisher)
Created2011
Description
Answer Set Programming (ASP) is one of the most prominent and successful knowledge representation paradigms. The success of ASP is due to its expressive non-monotonic modeling language and its efficient computational methods originating from building propositional satisfiability solvers. The wide adoption of ASP has motivated several extensions to its modeling language in order to enhance expressivity, such as incorporating aggregates and interfaces with ontologies. Also, in order to overcome the grounding bottleneck of computation in ASP, there are increasing interests in integrating ASP with other computing paradigms, such as Constraint Programming (CP) and Satisfiability Modulo Theories (SMT). Due to the non-monotonic nature of the ASP semantics, such enhancements turned out to be non-trivial and the existing extensions are not fully satisfactory. We observe that one main reason for the difficulties rooted in the propositional semantics of ASP, which is limited in handling first-order constructs (such as aggregates and ontologies) and functions (such as constraint variables in CP and SMT) in natural ways. This dissertation presents a unifying view on these extensions by viewing them as instances of formulas with generalized quantifiers and intensional functions. We extend the first-order stable model semantics by by Ferraris, Lee, and Lifschitz to allow generalized quantifiers, which cover aggregate, DL-atoms, constraints and SMT theory atoms as special cases. Using this unifying framework, we study and relate different extensions of ASP. We also present a tight integration of ASP with SMT, based on which we enhance action language C+ to handle reasoning about continuous changes. Our framework yields a systematic approach to study and extend non-monotonic languages.
ContributorsMeng, Yunsong (Author) / Lee, Joohyung (Thesis advisor) / Ahn, Gail-Joon (Committee member) / Baral, Chitta (Committee member) / Fainekos, Georgios (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2013
Description
Biological organisms are made up of cells containing numerous interconnected biochemical processes. Diseases occur when normal functionality of these processes is disrupted, manifesting as disease symptoms. Thus, understanding these biochemical processes and their interrelationships is a primary task in biomedical research and a prerequisite for activities including diagnosing diseases and drug development. Scientists studying these interconnected processes have identified various pathways involved in drug metabolism, diseases, and signal transduction, etc. High-throughput technologies, new algorithms and speed improvements over the last decade have resulted in deeper knowledge about biological systems, leading to more refined pathways. Such pathways tend to be large and complex, making it difficult for an individual to remember all aspects. Thus, computer models are needed to represent and analyze them. The refinement activity itself requires reasoning with a pathway model by posing queries against it and comparing the results against the real biological system. Many existing models focus on structural and/or factoid questions, relying on surface-level information. These are generally not the kind of questions that a biologist may ask someone to test their understanding of biological processes. Examples of questions requiring understanding of biological processes are available in introductory college level biology text books. Such questions serve as a model for the question answering system developed in this thesis. Thus, the main goal of this thesis is to develop a system that allows the encoding of knowledge about biological pathways to answer questions demonstrating understanding of the pathways. To that end, a language is developed to specify a pathway and pose questions against it. Some existing tools are modified and used to accomplish this goal. The utility of the framework developed in this thesis is illustrated with applications in the biological domain. Finally, the question answering system is used in real world applications by extracting pathway knowledge from text and answering questions related to drug development.
ContributorsAnwar, Saadat (Author) / Baral, Chitta (Thesis advisor) / Inoue, Katsumi (Committee member) / Chen, Yi (Committee member) / Davulcu, Hasan (Committee member) / Lee, Joohyung (Committee member) / Arizona State University (Publisher)
Created2014
Description
Different logic-based knowledge representation formalisms have different limitations either with respect to expressivity or with respect to computational efficiency. First-order logic, which is the basis of Description Logics (DLs), is not suitable for defeasible reasoning due to its monotonic nature. The nonmonotonic formalisms that extend first-order logic, such as circumscription and default logic, are expressive but lack efficient implementations. The nonmonotonic formalisms that are based on the declarative logic programming approach, such as Answer Set Programming (ASP), have efficient implementations but are not expressive enough for representing and reasoning with open domains. This dissertation uses the first-order stable model semantics, which extends both first-order logic and ASP, to relate circumscription to ASP, and to integrate DLs and ASP, thereby partially overcoming the limitations of the formalisms. By exploiting the relationship between circumscription and ASP, well-known action formalisms, such as the situation calculus, the event calculus, and Temporal Action Logics, are reformulated in ASP. The advantages of these reformulations are shown with respect to the generality of the reasoning tasks that can be handled and with respect to the computational efficiency. The integration of DLs and ASP presented in this dissertation provides a framework for integrating rules and ontologies for the semantic web. This framework enables us to perform nonmonotonic reasoning with DL knowledge bases. Observing the need to integrate action theories and ontologies, the above results are used to reformulate the problem of integrating action theories and ontologies as a problem of integrating rules and ontologies, thus enabling us to use the computational tools developed in the context of the latter for the former.
ContributorsPalla, Ravi (Author) / Lee, Joohyung (Thesis advisor) / Baral, Chitta (Committee member) / Kambhampati, Subbarao (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2012
Description
Natural Language Processing is a subject that combines computer science and linguistics, aiming to provide computers with the ability to understand natural language and to develop a more intuitive human-computer interaction. The research community has developed ways to translate natural language to mathematical formalisms. It has not yet been shown, however, how to automatically translate different kinds of knowledge in English to distinct formal languages. Most of the recent work presents the problem that the translation method aims to a specific formal language or is hard to generalize. In this research, I take a first step to overcome this difficulty and present two algorithms which take as input two lambda-calculus expressions G and H and compute a lambda-calculus expression F. The expression F returned by the first algorithm satisfies F@G=H and, in the case of the second algorithm, we obtain G@F=H. The lambda expressions represent the meanings of words and sentences. For each formal language that one desires to use with the algorithms, the language must be defined in terms of lambda calculus. Also, some additional concepts must be included. After doing this, given a sentence, its representation and knowing the representation of several words in the sentence, the algorithms can be used to obtain the representation of the other words in that sentence. In this work, I define two languages and show examples of their use with the algorithms. The algorithms are illustrated along with soundness and completeness proofs, the latter with respect to typed lambda-calculus formulas up to the second order. These algorithms are a core part of a natural language semantics system that translates sentences from English to formulas in different formal languages.
ContributorsAlvarez Gonzalez, Marcos (Author) / Baral, Chitta (Thesis advisor) / Lee, Joohyung (Committee member) / Ye, Jieping (Committee member) / Arizona State University (Publisher)
Created2010
Description
In the next decade or so, there will be a shift in the industry of transportation across the world. Already today we have autonomous vehicles (AVs) tested in the Greater Phoenix area showing that the technology has improved to a level available to the public eye. Although this technology is not yet released commercially (for the most part), it is being used and will continue to be used to develop a safer future. With a high incidence of human error causing accidents, many expect that autonomous vehicles will be safer than human drivers. They do still require driver attention and sometimes intervention to ensure safety, but for the most part are much safer. In just the United States alone, there were 40,000 deaths due to car accidents last year [1]. If traffic fatalities were considered a disease, this would be an epidemic. The technology behind autonomous vehicles will allow for a much safer environment and increased mobility and independence for people who cannot drive and struggle with public transport. There are many opportunities for autonomous vehicles in the transportation industry. Companies can save a lot more money on shipping by cutting the costs of human drivers and trucks on the road, even allowing for simpler drop shipments should the necessary AI be developed.Research is even being done by several labs at Arizona State University. For example, Dr. Spring Berman’s Autonomous Collective Systems Lab has been collaborating with Dr. Nancy Cooke of Human Systems Engineering to develop a traffic testbed, CHARTopolis, to study the risks of driver-AV interactions and the psychological effects of AVs on human drivers on a small scale. This testbed will be used by researchers from their labs and others to develop testing on reaction, trust, and user experience with AVs in a safe environment that simulates conditions similar to those experienced by full-size AVs. Using a new type of small robot that emulates an AV, developed in Dr. Berman’s lab, participants will be able to remotely drive around a model city environment and interact with other AV-like robots using the cameras and LiDAR sensors on the remotely driven robot to guide them.
Although these commercial and research systems are still in testing, it is important to understand how AVs are being marketed to the general public and how they are perceived, so that one day they may be effectively adopted into everyday life. People do not want to see a car they do not trust on the same roads as them, so the questions are: why don’t people trust them, and how can companies and researchers improve the trustworthiness of the vehicles?
Although these commercial and research systems are still in testing, it is important to understand how AVs are being marketed to the general public and how they are perceived, so that one day they may be effectively adopted into everyday life. People do not want to see a car they do not trust on the same roads as them, so the questions are: why don’t people trust them, and how can companies and researchers improve the trustworthiness of the vehicles?
ContributorsShuster, Daniel Nadav (Author) / Berman, Spring (Thesis director) / Cooke, Nancy (Committee member) / Mechanical and Aerospace Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2019-05
Description
Chemical Reaction Networks (CRNs) provide a useful framework for modeling andcontrolling large numbers of agents that undergo stochastic transitions between a set of states
in a manner similar to chemical compounds. By utilizing CRN models to design agent control
policies, some of the computational challenges in the coordination of multi-agent systems can
be overcome. In this thesis, a CRN model is developed that defines agent control policies for a
multi-agent construction task. The use of surface CRNs to overcome the tradeoff between
speed and accuracy of task performance is explained. The computational difficulties involved
in coordinating multiple agents to complete collective construction tasks is then discussed. A
method for stochastic task and motion planning (TAMP) is proposed to explain how a TAMP
solver can be applied with CRNs to coordinate multiple agents.
This work defines a collective construction scenario in which a group of noncommunicating agents must rearrange blocks on a discrete domain with obstacles into a
predefined target distribution. Four different construction tasks are considered with 10, 20,
30, or 40 blocks, and a simulation of each scenario with 2, 4, 6, or 8 agents is performed. As the
number of blocks increases, the construction problem becomes more complex, and a given
population of agents requires more time to complete the task. Populations of fewer than 8
agents are unable to solve the 30-block and 40-block problems in the allotted simulation time,
suggesting an inflection point for computational feasibility, implying that beyond that point
the solution times for fewer than 8 agents would be expected to increase significantly. For a
group of 8 agents, the time to complete the task generally increases as the number of blocks
increases, except for the 30-block problem, which has specifications that make the task slightly
easier for the agents to complete compared to the 20-block problem. For the 10-block and 20-
block problems, the time to complete the task decreases as the number of agents increases;
however, the marginal effect of each additional two agents on this time decreases. This can be
explained through the pigeonhole principle: since there area finite number of states, when the
number of agents is greater than the number of available spaces, deadlocks start to occur and
the expectation is that the overall solution time to tend to infinity.
ContributorsKamojjhala, Pranav (Author) / Berman, Spring (Thesis advisor) / Fainekos, Gergios E (Thesis advisor) / Pavlic, Theodore P (Committee member) / Arizona State University (Publisher)
Created2022
Description
A Graph Neural Network (GNN) is a type of neural network architecture that operates on data consisting of objects and their relationships, which are represented by a graph. Within the graph, nodes represent objects and edges represent associations between those objects. The representation of relationships and correlations between data is unique to graph structures. GNNs exploit this feature of graphs by augmenting both forms of data, individual and relational, and have been designed to allow for communication and sharing of data within each neural network layer. These benefits allow each node to have an enriched perspective, or a better understanding, of its neighbouring nodes and its connections to those nodes. The ability of GNNs to efficiently process high-dimensional node data and multi-faceted relationships among nodes gives them advantages over neural network architectures such as Convolutional Neural Networks (CNNs) that do not implicitly handle relational data. These quintessential characteristics of GNN models make them suitable for solving problems in which the correspondences among input data are needed to produce an accurate and precise representation of these data. GNN frameworks may significantly improve existing communication and control techniques for multi-agent tasks by implicitly representing not only information associated with the individual agents, such as agent position, velocity, and camera data, but also their relationships with one another, such as distances between the agents and their ability to communicate with one another. One such task is a multi-agent navigation problem in which the agents must coordinate with one another in a decentralized manner, using proximity sensors only, to navigate safely to their intended goal positions in the environment without collisions or deadlocks. The contribution of this thesis is the design of an end-to-end decentralized control scheme for multi-agent navigation that utilizes GNNs to prevent inter-agent collisions and deadlocks. The contributions consist of the development, simulation and evaluation of the performance of an advantage actor-critic (A2C) reinforcement learning algorithm that employs actor and critic networks for training that simultaneously approximate the policy function and value function, respectively. These networks are implemented using GNN frameworks for navigation by groups of 3, 5, 10 and 15 agents in simulated two-dimensional environments. It is observed that in $40\%$ to $50\%$ of the simulation trials, between 70$\%$ to 80$\%$ of the agents reach their goal positions without colliding with other agents or becoming trapped in deadlocks. The model is also compared to a random run simulation, where actions are chosen randomly for the agents and observe that the model performs notably well for smaller groups of agents.
ContributorsAyalasomayajula, Manaswini (Author) / Berman, Spring (Thesis advisor) / Mian, Sami (Committee member) / Pavlic, Theodore (Committee member) / Arizona State University (Publisher)
Created2022
Description
Recently, Generative Adversarial Networks (GANs) have been applied to the problem of Cold-Start Recommendation, but the training performance of these models is hampered by the extreme sparsity in warm user purchase behavior. This thesis introduces a novel representation for user-vectors by combining user demographics and user preferences, making the model a hybrid system which uses Collaborative Filtering and Content Based Recommendation. This system models user purchase behavior using weighted user-product preferences (explicit feedback) rather than binary user-product interactions (implicit feedback). Using this a novel sparse adversarial model, Sparse ReguLarized Generative Adversarial Network (SRLGAN), is developed for Cold-Start Recommendation. SRLGAN leverages the sparse user-purchase behavior which ensures training stability and avoids over-fitting on warm users. The performance of SRLGAN is evaluated on two popular datasets and demonstrate state-of-the-art results.
ContributorsShah, Aksheshkumar Ajaykumar (Author) / Venkateswara, Hemanth (Thesis advisor) / Berman, Spring (Thesis advisor) / Ladani, Leila J (Committee member) / Arizona State University (Publisher)
Created2022
Description
Despite the rapid adoption of robotics and machine learning in industry, their application to scientific studies remains under-explored. Combining industry-driven advances with scientific exploration provides new perspectives and a greater understanding of the planet and its environmental processes. Focusing on rock detection, mapping, and dynamics analysis, I present technical approaches and scientific results of developing robotics and machine learning technologies for geomorphology and seismic hazard analysis. I demonstrate an interdisciplinary research direction to push the frontiers of both robotics and geosciences, with potential translational contributions to commercial applications for hazard monitoring and prospecting. To understand the effects of rocky fault scarp development on rock trait distributions, I present a data-processing pipeline that utilizes unpiloted aerial vehicles (UAVs) and deep learning to segment densely distributed rocks in several orders of magnitude. Quantification and correlation analysis of rock trait distributions demonstrate a statistical approach for geomorphology studies. Fragile geological features such as precariously balanced rocks (PBRs) provide upper-bound ground motion constraints for hazard analysis. I develop an offboard method and onboard method as complementary to each other for PBR searching and mapping. Using deep learning, the offboard method segments PBRs in point clouds reconstructed from UAV surveys. The onboard method equips a UAV with edge-computing devices and stereo cameras, enabling onboard machine learning for real-time PBR search, detection, and mapping during surveillance. The offboard method provides an efficient solution to find PBR candidates in existing point clouds, which is useful for field reconnaissance. The onboard method emphasizes mapping individual PBRs for their complete visible surface features, such as basal contacts with pedestals–critical geometry to analyze fragility. After PBRs are mapped, I investigate PBR dynamics by building a virtual shake robot (VSR) that simulates ground motions to test PBR overturning. The VSR demonstrates that ground motion directions and niches are important factors determining PBR fragility, which were rarely considered in previous studies. The VSR also enables PBR large-displacement studies by tracking a toppled-PBR trajectory, presenting novel methods of rockfall hazard zoning. I build a real mini shake robot providing a reverse method to validate simulation experiments in the VSR.
ContributorsChen, Zhiang (Author) / Arrowsmith, Ramon (Thesis advisor) / Das, Jnaneshwar (Thesis advisor) / Bell, James (Committee member) / Berman, Spring (Committee member) / Christensen, Philip (Committee member) / Whipple, Kelin (Committee member) / Arizona State University (Publisher)
Created2022