AIICS

Patrick Doherty

Other Publications

Hide abstracts BibTeX entries
2012
[22] Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz and Peter Lucas. 2012.
Proceedings of the 20th European Conference on Artificial Intelligence (ECAI).
Conference Proceedings. In series: Frontiers in Artificial Intelligence and Applications #242. IOS Press. 1056 pages. ISBN: 978-1-61499-097-0.

2009
[21] Oleg Burdakov, Kaj Holmberg, Patrick Doherty and Per-Magnus Olsson. 2009.
Optimal placement of communications relay nodes.
Technical Report. In series: LiTH-MAT-R #2009:3. Link√∂pings universitet. 21 pages.

We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.

2007
[20] Mariusz Wzorek and Patrick Doherty. 2007.
A framework for reconfigurable path planning for autonomous unmanned aerial vehicles.
Manuscript (preprint).

2006
[19] Patrick Doherty, John Mylopoulos and Christopher Welty. 2006.
Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning.
Conference Proceedings. AAAI Press. ISBN: 978-1-57735-281-5.

he National Conference on Artificial Intelligence remains the bellwether for research in artificial intelligence. Leading AI researchers and practitioners as well as scientists and engineers in related fields present theoretical, experimental, and empirical results, covering a broad range of topics that include principles of cognition, perception, and action; the design, application, and evaluation of AI algorithms and systems; architectures and frameworks for classes of AI systems; and analyses of tasks and domains in which intelligent systems perform. The Innovative Applications of Artificial Intelligence conference highlights successful applications of AI technology; explores issues, methods, and lessons learned in the development and deployment of AI applications; and promotes an interchange of ideas between basic and applied AI. This volume presents the proceedings of the latest conferences, held in July, 2006.

2003
[18] Patrick Doherty, W. Lukaszewicz, Skowron Andrzej and Andrzej Szalas. 2003.
Knowledge Representation and Approximate Reasoning.
Conference Proceedings. In series: Fundamenta Informaticae #2003(57):2-4. IOS Press.
Note: Special Issue

[17] Patrick Doherty, A Skowron, Witold Lukaszewicz and Andrzej Szalas. 2003.
1st International Workshop on Knowledge Representation and Approximate Reasoning (KR&AR).

1998
[16] Full text  Patrick Doherty and Joakim Gustafsson. 1998.
Delayed effects of actions = direct effects + causal rules.
Technical Report. In series: Link√∂ping Electronic Articles in Computer and Information Science #98-001. Link√∂ping University Electronic Press.
Link: http://www.ep.liu.se/ea/cis/1998/001/

<strong></strong> We propose an approach to modeling delayed effects of actions which is based on the use of causal constraints and their interaction with the direct effects of actions. The approach extends previous work with a causal approach used to deal with the ramification problem. We show the similarity between solutions to the modeling of indirect effects and delayed effects of actions by example. The base logic PMON+ is a temporal logic for reasoning about action and change and uses circumscription. It is shown that the extension for delayed effects of actions retains the first-order reducibility property shown previously for successfully dealing with the frame and ramification problems for a large class of action scenarios. We also consider the ‚Äúcausal qualification‚ÄĚ problem, \"natural death\" of fluents and causal lag, each of which is closely related to the use of delayed effects.

1996
[15] Full text  Patrick Doherty. 1996.
PMON+: A fluent logic for action and change - formal specification, version 1.0.
Technical Report. In series: LITH-IDA-R #33. Department of Computer and Information Science, Link√∂ping University.

This report describes the current state of work with PMON, a logic for reasoning about action and change, and its extensions. PMON has been assessed correct for the K-IA class using Sandewall's Features and Fluents framework which provides tools for assessing the correctness of logics of action and change. A syntactic characterization of PMON has previously been provided in terms of a circumscription axiom which is shown to be reducible to a first-order formula. This report introduces a number of new extensions which are also reducible and deal with ramification. The report is intended to provide a formal specification for the PMON family of logics and the surface language L(SD) used to represent action scenario descriptions. It should be considered a working draft. The title of the report has a version number because both the languages and logics used are continually evolving. Since this document is intended as a formal specification which is used by our group as a reference for research and implementation, it is understandably brief as regards intuitions and applications of the languages and logics defined. We do provide a set of benchmarks and comments concerning these which can serve as a means of comparing this formalism with others. The set of benchmarks is not complete and is only intended to provide representative examples of the expressivity and use of this particular family of logics. We describe its features and limitations in other publications by our group which can normally be found at \"http://www.ida.liu.se/labs/kplab/\".

[14] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
Declarative ptime queries to relational databases.
Technical Report. In series: LITH-IDA-R #34. Department of Computer and Information Science, Link√∂ping University.

[13] Full text  John-Jules Meyer and Patrick Doherty. 1996.
Preferential action semantics, preliminary report.
Technical Report. In series: LITH-IDA-R #??. Department of Computer and Information Science, Link√∂ping University.

In this paper, we propose a new way of considering reasoning about action and change. Rather than placing a preferential structure onto the models of logical theories, we place such a structure directly on the semantics of the actions involved. In this way, we obtain a preferential semantics of actions by means of which we can not only deal with several of the traditional problems in this area such as the frame and ramification problems, but can generalize these solutions to a context which includes both nondeterministic and concurrent actions. In fact, the net result is an integration of semantical and verificational techniques from the paradigm of imperative and concurrent programs in particular, as known from traditional programming, with the AI perspective. In this paper, the main focus is on semantical (i.e. model theoretical) issues rather than providing a logical calculus, which would be the next step in the endeavor.

[12] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
General domain circumscription and its first-order reduction.
Technical Report. In series: LITH-IDA-R #1. Department of Computer and Information Science, Link√∂ping University.

1995
[11] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1995.
A characterization result for circumscribed normal logic programs. Revised version accepted for publication: Special issue of honor of H. Rasiowa, Fundamenta Informaticae.
Technical Report. In series: LITH-IDA-R #20. Department of Computer and Information Science, Link√∂ping University.

1994
[10] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1994.
Computing circumscription revisited: A reduction algorithm.
Technical Report. In series: LITH-IDA-R #94-42. Department of Computer and Information Science, Link√∂ping University.

In recent years, a great deal of attention has been devoted to logics of \"commonsense\" reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the nd-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, nd-order formulas into equivalent 1st-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method which can be used in an algorithmic manner to reduce circumscription axioms to 1st-order formulas. The algorithm takes as input an arbitrary 2nd-order formula and either returns as output an equivalent 1st-order formula, or terminates with failure. The class of 2nd-order formulas, and analogously the class of circumscriptive theories which can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, non-separated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm and compare it with existing approaches providing formal subsumption results.

[9] Patrick Doherty. 1994.
Notes on PMON circumscription.
Technical Report. In series: LITH-IDA-R #43. Department of Computer and Information Science, Link√∂ping University.

1992
[8] Patrick Doherty and Witold Lukaszewicz. 1992.
FONML3 - A first-order non-monotonic logic with explicit defaults.
Technical Report. In series: LITH-IDA-R #20. Department of Computer and Information Science, Link√∂ping University.

[7] Patrick Doherty, Dimiter Driankov and H. Hellendoorn. 1992.
Fuzzy if-then-unless rules and their implementation.
Technical Report. In series: LITH-IDA-R #21. Department of Computer and Information Science, Link√∂ping University.

[6] Patrick Doherty, Dimiter Driankov and A. Tsoukias. 1992.
Partiality, para-consistency and preference modeling: Preliminary version.
Technical Report. In series: LITH-IDA-R #18. Department of Computer and Information Systems, Link√∂ping University.

[5] Patrick Doherty. 1992.
A constraint-based approach to proof procedures for multi-valued logics.
Technical Report. In series: LITH-IDA-R #2. Department of Computer and Information Science, Link√∂ping university, Link√∂ping, Sweden.

1991
[4] Patrick Doherty and Witold Lukaszewicz. 1991.
NML3 - A non-monotonic logic with explicit defaults.
Technical Report. In series: Anv√§ndarrapport #13. Department of Computer and Information Science, Link√∂ping University.

1990
[3] Patrick Doherty. 1990.
NM3 - A three-valued non-monotonic formalism. Preliminary report.
Technical Report. In series: LITH-IDA-R #44. Department of Computer and Information Science, Link√∂ping University.

[2] Patrick Doherty. 1990.
A correspondence between inheritance hierarchies and a logic of preferential entailment.
Technical Report. In series: LITH-IDA-R #??. Department of Computer and Information Science, Link√∂ping University.

1985
[1] Patrick Doherty. 1985.
A rule interpreter for an emycin-like expert system tool.
Technical Report. In series: Aslab Memo #85-05. Link√∂pings tekniska h√∂gskola.