A Planning System for Robot Construction Tasks

This paper describes BUILD, a computer program which generates plans for building specified structures out of simple objects such as toy blocks. A powerful heuristic control structure enables BUILD to use a number of sophisticated construction techniques in its plans. Among these are the incorporation of pre-existing structure into the final design, pre-assembly of movable sub-structures on the table, and use of the extra blocks as temporary supports and counterweights in the course of construction. BUILD does its planning in a modeled 3-space in which blocks of various shapes and sizes can be represented in any orientation and location. The modeling system can maintain several world models at once, and contains modules for displaying states, testing them for inter-object contact and collision, and for checking the stability of complex structures involving frictional forces. Various alternative approaches are discussed, and suggestions are included for the extension of BUILD-like systems to other domains. Also discussed are the merits of BUILD's implementation language, CONNIVER, for this type of problem solving.

Hypothesis Formation and Evaluation in Medical Diagnosis

This thesis describes some aspects of a computer system for doing medical diagnosis in the specialized field of kidney disease. Because such a system faces the spectre of combinatorial explosion, this discussion concentrates on heuristics which control the number of concurrent hypotheses and efficient "compiled" representations of medical knowledge. In particular, the differential diagnosis of hematuria (blood in the urine) is discussed in detail. A protocol of a simulated doctor/patient interaction is presented and analyzed to determine the crucial structures and processes involved in the diagnosis procedure. The data structure proposed for representing medical information revolves around elementary hypotheses which are activated when certain disposing of findings, activating hypotheses, evaluating hypotheses locally and combining hypotheses globally is examined for its heuristic implications. The thesis attempts to fit the problem of medical diagnosis into the framework of other Artifcial Intelligence problems and paradigms and in particular explores the notions of pure search vs. heuristic methods, linearity and interaction, local vs. global knowledge and the structure of hypotheses within the world of kidney disease.

Planning for Conjunctive Goals

The problem of achieving conjunctive goals has been central to domain independent planning research; the nonlinear constraint-posting approach has been most successful. Previous planners of this type have been comlicated, heuristic, and ill-defined. I have combined and distilled the state of the art into a simple, precise, implemented algorithm (TWEAK) which I have proved correct and complete. I analyze previous work on domain-independent conjunctive planning; in retrospect it becomes clear that all conjunctive planners, linear and nonlinear, work the same way. The efficiency of these planners depends on the traditional add/delete-list representation for actions, which drastically limits their usefulness. I present theorems that suggest that efficient general purpose planning with more expressive action representations is impossible, and suggest ways to avoid this problem.

On the use of qualitative reasoning to simulate and identify metabolic pathways

King, R.D., Garrett, S.M., Coghill, G.M. (2005). On the use of qualitative reasoning to simulate and identify metabolic pathways. Bioinformatics 21(9):2017-2026 RAE2008

NHS Wales e-library portal evaluation (For Informing Healthcare Strategy implementation programme)

Thomas, R. & Urquhart, C. NHS Wales e-library portal evaluation. (For Informing Healthcare Strategy implementation programme). Aberystwyth: Department of Information Studies, University of Wales Aberystwyth Follow-on to NHS Wales User Needs study Sponsorship: Informing Healthcare, NHS Wales

Feature Selection based on Rough Sets and Particle Swarm Optimization

X. Wang, J. Yang, X. Teng, W. Xia, and R. Jensen. Feature Selection based on Rough Sets and Particle Swarm Optimization. Pattern Recognition Letters, vol. 28, no. 4, pp. 459-471, 2007.

Simultaneous ant colony optimisation algorithms for learning linguistic fuzzy rules

M. Galea and Q. Shen. Simultaneous ant colony optimisation algorithms for learning linguistic fuzzy rules. A. Abraham, C. Grosan and V. Ramos (Eds.), Swarm Intelligence in Data Mining, pages 75-99.

Lektura twórcza w edukacji humanistycznej

Wydział Filologii Polskiej i Klasycznej UAM: Instytut Filologii Polskiej

Filozofia antyczna wobec problemu interpretacji. Rozwój alegorezy od przedsokratyków do Arystotelesa

The present work examines the beginnings of ancient hermeneutics. More specifically, it discusses the connection between the rise of the practice of allegoresis, on the one hand, and the emergence of the first theory of figurative language, on the other. Thus, this book investigates the specific historical and cultural circumstances that enabled the ancient Greeks not only to discover the possibility of allegorical interpretation, but also to treat figurative language as a philosophical problem. By posing difficulties in understanding the enigmatic sense of various esoteric doctrines, poems, oracles and riddles, figurative language created the context for theoretical reflection on the meaning of these “messages”. Hence, ancient interpreters began to ponder over the nature and functions of figurative (“enigmatic”) language as well as over the techniques of its proper use and interpretation. Although the practice of allegorical interpretation was closely linked to the development of the whole of ancient philosophy, the present work covers only the period from the 6th to the 4th century B.C. It concentrates, then, on the philosophical and cultural consequences of allegoresis in the classical age. The main thesis advocated here has it that the ancient Greeks were in-clined to regard allegory as a cognitive problem rather than merely as a stylistic or a literary one. When searching for the hidden meanings of various esoteric doc-trines, poems, oracles and riddles, ancient interpreters of these “messages” assumed allegory to be the only tool suitable for articulating certain matters. In other words, it was their belief that the use of figurative language resulted from the necessity of expressing things that were otherwise inexpressible. The present work has been organized in the following manner. The first part contains historical and philological discussions that provide the point of departure for more philosophical considerations. This part consists of two introductory chapters. Chapter one situates the practice of allegorical interpretation at the borderline of two different traditions: the rhetorical-grammatical and the hermeneutical. In order to clearly differentiate between the two, chapter one distinguishes between allegory and allegoresis, on the one hand, and allegoresis and exegesis, on the other. While pointing to the conventionality (and even arbitrariness) of such distinctions, the chapter argues, nevertheless, for their heuristic usefulness. The remaining part of chapter one focuses on a historical and philological reconstruction of the most important conceptual tools of ancient hermeneutics. Discussing the semantics of such terms as allēgoría, hypónoia, ainigma and symbolon proves important for at least two crucial reasons. Firstly, it reveals the mutual affinity between allegoresis and divination, i.e., practices that are inherently connected with the need to discover the latent meaning of the “message” in question (whether poem or oracle). Secondly, these philological analyses bring to light the specificity of the ancient understanding of such concepts as allegory or symbol. It goes without saying that antiquity employed these terms in a manner quite disparate from modernity. Chapter one concludes with a discussion of ancient views on the cognitive value of figurative (“enigmatic”) language. Chapter two focuses on the role that allegoresis played in the process of transforming mythos into logos. It is suggested here that it was the practice of allegorical interpretation that made it possible to preserve the traditional myths as an important point of reference for the whole of ancient philosophy. Thus, chapter two argues that the existence of a clear opposition between mythos into logos in Preplatonic philosophy is highly questionable in light of the indisputable fact that the Presocratics, Sophists and Cynics were profoundly convinced about the cognitive value of mythos (this conviction was also shared by Plato and Aristotle, but their attitude towards myth was more complex). Consequently, chapter two argues that in Preplatonic philosophy, myth played a function analogous to the concepts discussed in chapter one (i.e., hidden meanings, enigmas and symbols), for in all these cases, ancient interpreters found tools for conveying issues that were otherwise difficult to convey. Chapter two concludes with a classification of various types of allegoresis. Whilst chapters one and two serve as a historical and philological introduction, the second part of this book concentrates on the close relationship between the development of allegoresis, on the one hand, and the flowering of philosophy, on the other. Thus, chapter three discusses the crucial role that allegorical interpretation came to play in Preplatonic philosophy, chapter four deals with Plato’s highly complex and ambivalent attitude to allegoresis, and chapter five has been devoted to Aristotle’s original approach to the practice of allegorical interpretation. It is evident that allegoresis was of paramount importance for the ancient thinkers, irrespective of whether they would value it positively (Preplatonic philosophers and Aristotle) or negatively (Plato). Beginning with the 6th century B.C., the ancient practice of allegorical interpretation is motivated by two distinct interests. On the one hand, the practice of allegorical interpretation reflects the more or less “conservative” attachment to the authority of the poet (whether Homer, Hesiod or Orpheus). The purpose of this apologetic allegoresis is to exonerate poetry from the charges leveled at it by the first philosophers and, though to a lesser degree, historians. Generally, these allegorists seek to save the traditional paideia that builds on the works of the poets. On the other hand, the practice of allegorical interpretation reflects also the more or less “progressive” desire to make original use of the authority of the poet (whether Homer, Hesiod or Orpheus) so as to promote a given philosophical doctrine. The objective of this instrumental allegoresis is to exculpate philosophy from the accusations brought against it by the more conservative circles. Needless to say, these allegorists significantly contribute to the process of the gradual replacing of the mythical view of the world with its more philosophical explanation. The present book suggests that it is the philosophy of Aristotle that should be regarded as a sort of acme in the development of ancient hermeneutics. The reasons for this are twofold. On the one hand, the Stagirite positively values the practice of allegoresis, rehabilitating, thus, the tradition of Preplatonic philosophy against Plato. And, on the other hand, Aristotle initiates the theoretical reflection on figurative (“enigmatic”) language. Hence, in Aristotle we encounter not only the practice of allegoresis, but also the theory of allegory (although the philosopher does not use the term allēgoría). With the situation being as it is, the significance of Aristotle’s work cannot be overestimated. First of all, the Stagirite introduces the concept of metaphor into the then philosophical considerations. From that moment onwards, the phenomenon of figurative language becomes an important philosophical issue. After Aristo-tle, the preponderance of thinkers would feel obliged to specify the rules for the appropriate use of figurative language and the techniques of its correct interpretation. Furthermore, Aristotle ascribes to metaphor (and to various other “excellent” sayings) the function of increasing and enhancing our knowledge. Thus, according to the Stagirite, figurative language is not only an ornamental device, but it can also have a significant explanatory power. Finally, Aristotle observes that figurative expressions cause words to become ambiguous. In this context, the philosopher notices that ambiguity can enrich the language of a poet, but it can also hinder a dialectical discussion. Accordingly, Aristotle is inclined to value polysemy either positively or negatively. Importantly, however, the Stagirite is perfectly aware of the fact that in natural languages ambiguity is unavoidable. This is why Aristotle initiates a syste-matic reflection on the phenomenon of ambiguity and distinguishes its various kinds. In Aristotle, ambiguity is, then, both a problem that needs to be identified and a tool that can help in elucidating intricate philosophical issues. This unique approach to ambiguity and figurative (“enigmatic”) language enabled Aristotle to formulate invaluable intuitions that still await appropriate recognition.

Analityczna filozofia dziejów w poznańskiej szkole metodologicznej. Próba falsyfikacji Popperowskiej krytyki historii teoretycznej

The purpose of this paper is the reconstruction of the theory of historical process elaborated at the Poznań School of Methodology. The heuristic tool will be Popper’s model of knowledge, according to which, the development of scientific theory went through the phase of the posing of the scientific problem, proposing a tentative theory, a critical discussion and its modification. Proposed by Leszek Nowak the adaptive interpretation of historical materialism was transformed – under the influence of the elaboration of the idealizational theory of science and the categorical interpretation of dialectics – into the generalized version of historical materialism. This version includes theory of the class and primitive societies. Difficulties in the building of the theory of real socialism led to the transformation of adaptive historical materialism into the non-Marxian historical materialism where some tenets of Marxism were refuted (e.g. the domination of economy over politics). In the course of the building of the adaptive interpretation of historical materialism and the non-Marxian historical materialism some primary notions were defined and modified satisfying the criteria of falsification. Although Popper severely criticized the possibility of theoretical history, the theory of history as developed at the Poznań School of Methodology satisfies his criteria of falsification. This throws doubt upon the validity of Popperian critique of theoretical history.

On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

Task Assignment in a Distributed System: Improving Performance by Unbalancing Load

We consider the problem of task assignment in a distributed system (such as a distributed Web server) in which task sizes are drawn from a heavy-tailed distribution. Many task assignment algorithms are based on the heuristic that balancing the load at the server hosts will result in optimal performance. We show this conventional wisdom is less true when the task size distribution is heavy-tailed (as is the case for Web file sizes). We introduce a new task assignment policy, called Size Interval Task Assignment with Variable Load (SITA-V). SITA-V purposely operates the server hosts at different loads, and directs smaller tasks to the lighter-loaded hosts. The result is that SITA-V provably decreases the mean task slowdown by significant factors (up to 1000 or more) where the more heavy-tailed the workload, the greater the improvement factor. We evaluate the tradeoff between improvement in slowdown and increase in waiting time in a system using SITA-V, and show conditions under which SITA-V represents a particularly appealing policy. We conclude with a discussion of the use of SITA-V in a distributed Web server, and show that it is attractive because it has a simple implementation which requires no communication from the server hosts back to the task router.

Generating Good Degree Distributions for Sparse Parity Check Codes using Oracles

Fast forward error correction codes are becoming an important component in bulk content delivery. They fit in naturally with multicast scenarios as a way to deal with losses and are now seeing use in peer to peer networks as a basis for distributing load. In particular, new irregular sparse parity check codes have been developed with provable average linear time performance, a significant improvement over previous codes. In this paper, we present a new heuristic for generating codes with similar performance based on observing a server with an oracle for client state. This heuristic is easy to implement and provides further intuition into the need for an irregular heavy tailed distribution.

Basis Token Consistency: A Practical Mechanism for Strong Web Cache Consistency

With web caching and cache-related services like CDNs and edge services playing an increasingly significant role in the modern internet, the problem of the weak consistency and coherence provisions in current web protocols is becoming increasingly significant and drawing the attention of the standards community [LCD01]. Toward this end, we present definitions of consistency and coherence for web-like environments, that is, distributed client-server information systems where the semantics of interactions with resource are more general than the read/write operations found in memory hierarchies and distributed file systems. We then present a brief review of proposed mechanisms which strengthen the consistency of caches in the web, focusing upon their conceptual contributions and their weaknesses in real-world practice. These insights motivate a new mechanism, which we call "Basis Token Consistency" or BTC; when implemented at the server, this mechanism allows any client (independent of the presence and conformity of any intermediaries) to maintain a self-consistent view of the server's state. This is accomplished by annotating responses with additional per-resource application information which allows client caches to recognize the obsolescence of currently cached entities and identify responses from other caches which are already stale in light of what has already been seen. The mechanism requires no deviation from the existing client-server communication model, and does not require servers to maintain any additional per-client state. We discuss how our mechanism could be integrated into a fragment-assembling Content Management System (CMS), and present a simulation-driven performance comparison between the BTC algorithm and the use of the Time-To-Live (TTL) heuristic.

Unicast Routing: Cost-Performance Tradeoffs

The objective of unicast routing is to find a path from a source to a destination. Conventional routing has been used mainly to provide connectivity. It lacks the ability to provide any kind of service guarantees and smart usage of network resources. Improving performance is possible by being aware of both traffic characteristics and current available resources. This paper surveys a range of routing solutions, which can be categorized depending on the degree of the awareness of the algorithm: (1) QoS/Constraint-based routing solutions are aware of traffic requirements of individual connection requests; (2) Traffic-aware routing solutions assume knowledge of the location of communicating ingress-egress pairs and possibly the traffic demands among them; (3) Routing solutions that are both QoS-aware as (1) and traffic-aware as (2); (4) Best-effort solutions are oblivious to both traffic and QoS requirements, but are adaptive only to current resource availability. The best performance can be achieved by having all possible knowledge so that while finding a path for an individual flow, one can make a smart choice among feasible paths to increase the chances of supporting future requests. However, this usually comes at the cost of increased complexity and decreased scalability. In this paper, we discuss such cost-performance tradeoffs by surveying proposed heuristic solutions and hybrid approaches.