We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, involve an adversarial relationship (...) between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired. (shrink)

We present a connection tableau based calculus extended by the possibility to exploit equivalences. By making equivalences explicit, it is on the one hand possible to apply well-known methods of equality reasoning, like demodulation, on the predicate level—even in top-down backward-chaining calculi. On the other hand, the explicit use of equivalences allows to strengthen calculi refinements. We show that such an approach has great potential to reduce the search space and to find proofs which are otherwise unobtainable in reasonable time. (...) Since many problems only contain equivalences implicitly, we propose a technique to generate them automatically in the course of the deduction process.1. (shrink)

We describe a relational framework that uniformly supports formalization and automated reasoning in varied propositional modal logics. The proof system we propose is a relational variant of the classical Rasiowa-Sikorski proof system. We introduce a compact graph-based representation of formulae and proofs supporting an efficient implementation of the basic inference engine, as well as of a number of refinements. Completeness and soundness results are shown and a Prolog implementation is described.

A problem is a situation in which an agent seeks to attain a given goal without knowing how to achieve it. Human problem solving is typically studied as a search in a problem space composed of states (information about the environment) and operators (to move between states). A problem such as playing a game of chess has possible states, and a traveling salesperson problem with as little as 82 cities already has more than different tours (similar to chess). Biological neurons (...) are slower than the digital switches in computers. An exhaustive search of the problem space exceeds the capacity of current computers for most interesting problems, and it is fairly clear that humans cannot in their lifetime exhaustively search even small fractions of these problem spaces. Yet, humans play chess and solve logistical problems of similar complexity on a daily basis. Even for simple problems humans do not typically engage in exploring even a small fraction of the problem space. This begs the question: How do humans solve problems on a daily basis in a fast and efficient way? Recent work suggests that humans build a problem representation and solve the represented problem—not the problem that is out there. The problem representation that is built and the process used to solve it are constrained by limits of cognitive capacity and a cost–benefit analysis discounting effort and reward. In this article, we argue that better understanding the way humans represent and solve problems using heuristics can help inform how simpler algorithms and representations can be used in artificial intelligence to lower computational complexity, reduce computation time, and facilitate real-time computation in complex problem solving. (shrink)

We raise the new possibility that people diagnosed with developmental dyslexia (DD) are specialized in explorative cognitive search, and rather than having a neurocognitive disorder, play an essential role in human adaptation. Most DD research has studied educational difficulties, with theories framing differences in neurocognitive processes as deficits. However, people with DD are also often proposed to have certain strengths – particularly in realms like discovery, invention, and creativity – that deficit-centered theories cannot explain. We investigate whether these strengths reflect (...) an underlying explorative specialization. We re-examine experimental studies in psychology and neuroscience using the framework ofcognitive search, whereby many psychological processes involve a trade-off between exploration and exploitation. We report evidence of an explorative bias in DD-associated cognitive strategies. High DD prevalence and an attendant explorative bias across multiple areas of cognition suggest the existence of explorative specialization. An evolutionary perspective explains the combination of findings and challenges the view that individuals with DD have a disorder. In cooperating groups, individual specialization is favored when features that confer fitness benefits are functionally incompatible. Evidence for search specialization suggests that, as with some other social organisms, humans mediate the exploration–exploitation trade-off by specializing in complementary strategies. The existence of a system of collective cognitive search that emerges through collaboration would help to explain our species’ exceptional adaptiveness. It also aligns with evidence for substantial variability during our evolutionary history and the notion that humans are adapted not to a particular habitat but to variability itself. Specialization creates interdependence and necessitates balancing complementary strategies. Reframing DD therefore underscores the urgency of changing certain cultural practices to ensure we do not inhibit adaptation. Key improvements would remove cultural barriers to exploration and nurture explorative learning in education, academia, and the workplace, as well as emphasize collaboration over competition. Specialization in complementary search abilities represents a meta-adaptation; through collaboration, this likely enables human groups (as a species and as cultural systems) to successfully adapt. Cultural change to support this system of collaborative search may therefore be essential in confronting the challenges humanity now faces. (shrink)