Research page of Ariel Felner
I am one of
the organizers of the IAAI day on June 19, at
Research
Interest:
My main research area is heuristic search. I am also interested in mobile
agents in unknown physical
environments.
I will soon update and upgrade my web site.
Heuristics and pattern databases
I
am currently interested in pattern-databases (PDBs) which are a recent
breakthrough that have made a revolution in calculating accurate heuristic
functions. Many state of the art problem solvers rely on this new idea. Pattern
databases are large tables that store solutions to "patterns" or
subproblems and are usually stored in main memory. These solutions are then
used as heuristics that guide the search. With heuristics defined by pattern
databases we are able to solve problems thousands of times faster than with
previous heuristics. Many of my papers are on pattern databases. They include:
“Disjoint Pattern Database Heuristics”, “Additive Pattern Database Heuristics", “Multiple Pattern Databases”, “Compressing
Pattern Databases” , "Dual Lookups in Pattern Databases" , Solving the 24 Puzzle with Instance Dependent Pattern
Databases ,Dual Search in Permutation State spaces and Recent Progress in Heuristic Search: A Case Study of the
Four-Peg Towers of Hanoi Problem, Inconsistent Heuristics , Compressed Pattern
Databases. It is best for a new comer to read these papers in this order.
Other related papers are: Finding Optimal Graph
Partitioning with Heuristic search and KBFS: K-best-first Search
We had workshop in AAAI-06 titled Heuristic search,
memory based heuristics and their applications on these topics.
Mobile agents
Another field that I am interested in is the field of mobile agents in unknown physical environments. Here, each agent needs to decide where to go next based on its partial knowledge of the graph and on the problem to be solved. In a multi-agent systems, agents need to communicate and share knowledge. What is the best communication model for that? How different communication models and constraint influence the behavior of the entire group of agents?
My
first work in this topic is the Physical A* (PHA*) algorithm and its multi
agent version MAPHA*. These algorithms are designed to help one or more mobile agents/robots
to activate A* on a physical environment. These algorithms are designed to
minimize the traveling effort of the agents.
I am also interested in a new model of communication in multi agent
systems which we call large pheromones. We already have a version of MAPHA*
with this paradigm. The papers in this topic are: PHA*:
Performing A* in Unknown Physical Environments, PHA*:
Finding the Shortest Path with A* in
Unknown Physical Environments , Large Pheromones: A
case study with Multi-agent PH A*. , "Utility Based Multi-Agent System for Performing Repeated
Navigation Task"
, Multi-agent Physical A* with Large Pheromones , On the Complexity of Physical Problems and a Swarm Algorithm
for K-Clique Search in Physical Graphs and Distributed
Navigation in an Unknown Physical Environment
Curriculum Vita:
Name: Ariel Felner. Address:
100/d Makabim St. Shoham.
Phone: +972-54-7548600 Email: felner@.bgu.ac.il
Academic background and employment:
2004-
2009: A faculty member (Lecturer) in the Department
of Information System Engineering, at Ben-Gurion
University.
2006-2007:
Visiting Scholar in the
2003-2004: Post-Doc, Technion,
research group lead by Prof. Alfred Bruckstein.
2002-2004: Temporary lecturer in the Computer
Science department of
1998-2002: Ph.D:
Bar-
"Improving Search Techniques and using them in Different Environments".
Advisor: Prof. Sarit Kraus. The work was carried out with a
Considerable amount of help and advice from Prof. Richard E. Korf from UCLA.
1994-1995: M.Sc:
Thesis title: "Searching for an Alternative Plan”. Advisor: Prof. Jeff Rosenchein.
1991-1993: B.Sc:
Other Employments:
1993-1997: Software
engineer in Telrad co.
2001-2003: Involved with Eshcolot
group in developing the ‘Thinking Trainer’ software.
Teaching Experience:
1997-2004: Bar
2004-
Professional Activities:
I organized
the the IAAI day on June 19, 2008.
I am a board member of the
Israeli Association for Artificial Intelligences (IAAI).
Reviewing:
program-committee member: AAAI-2002,
IJCAI-2003, AAAI-2004, ICGA-2004, AAAI05, AAAI-06, AAAI-07,SARA-07,
AAAI-08,AAMAS-08,IJCAI-09 and more
Artificial Intelligence journal, Journal of Artificial Intelligence Research.
Organizer of the “Workshop on heuristic search, memory based heuristics and their
applications” took place at AAAI-06 July 2006,
Grants
awarded:
1) The Israeli Ministry of Infrastructures: research title: "Teamwork of Robots" Years: 2005-2007.
2) ISF grant for academic years 2007-2009. Grant number 728/06. Research title: "Duality and inconsistency in search spaces".
Distinguish
paper awards:
1) Additive Pattern Databases, JAIR 2004: 2007 IJCAII-JAIR Runner up for the Best
Paper prize. Honorable mention as an elegant contribution to the area of heuristic
search that enhances the rich body of work on pattern database heuristics.
2) Inconsistent Heuristics, AAAI-07: Selected for the poster presentation which included 47 papers of the highest quality papers out of 921 submissions.
3) Multiple Pattern Databases ICAPS-04: Runner up for best paper award of the conference.
Students
Former M.Sc students in Bar-Ilan and
Technion.
Roni Stern: thesis
title: “PHA*: Applying A* to physical environment" (Aug 2002)
Joint papers: 1 2 3
Shimon Pomeransky: thesis title: “The manpower collector problem” (Nov 2002)
Alex Pomeransky:
thesis title: “Finding alternatives to best path" (Nov 2002) Joint papers: 1
Sarit Hanan:
thesis title: “Solving vertex-cover with heuristic search” (Dec 2002) Joint papers: 1
Ram Meshulam: thesis title: “Attributes of pattern databases” (Feb 2004) Joint papers: 1 2 3
Yaron Shoshani:
thesis title: “MAPHA* with Large Pheromones” (Mar 2004) joint papers: 1 2
Asaf Ben-Yair:
thesis title: “Generalizing PHA* to different cost requirements” (Aug
2004) Joint papers 1
Amir Adler:
thesis title: “Solving the 24 puzzle with pattern databases”:
(August 2005) Joint papers: 1
Uzi Zahavi:
thesis title: “Duality and inconsistency in search spaces”
(August 2005) Joint papers 1
Nir Ofek "Enhancing Pattern Databases" Joint papers 1 (December 2007)
Tal Fadida: "Finding cliques in physical
graphs" 1
(December 2007)
Zahy Bnaya: "D* with cot querying" 1 (December 2007)
Current Ph.D Students:
1) Ram Meshulam co-supervising with Sarit Kraus. His research topic is "Efficient moving physical agents in graphs". 1 2 3 4 5
2)
Uzi Zahavi: thesis title: “Duality and inconsistency in search spaces” Joint papers
1 2
3 4
3) Roni Stern: Thesis title will be determined. Joint papers 1 2 3
4) Zahy Bnaya. Thesis title will be
determined
Current
M.Sc Students in BGU
Tamar Kulberis: "Versions of Breadth-first
Search"
Max Barrer: "New directions in pattern
databases"
Publications
of Ariel Felner:
Book Chapters:
32) Richard E. Korf and Ariel Felner: “Disjoint Pattern Database Heuristics” in “Chips Challenging Champions:
Games, Computers and Artificial Intelligence”, 13-26, Edited by J. Schaeffer
and H. J. van den Herik. Elsevier Science, 2002.
Refereed Journal and Conference Papers:
2009
Conferences
37), Ariel
Felner, Nathan Sturtevant, Jonathan Schaeffer :"Abstraction-Based Heuristics with True Distance Computations” Accepted for
publication in the Eighth International Symposium on Abstraction, Reformulation
and Approximation (SARA-09)
36)
Inon Zukerman, Ariel Felner and Sarit Kraus: “ The MP-Mix Search Strategy For Multi-
Player Games”. Accepted for
publication in the Twenty First International Joint
Conferences on Artificial
Intelligence. (IJCAI-09)
To appear.
35) Nathan Sturtevant, Ariel Felner, Max Barer, Jonathan
Schaeffer, Neil Burch “Memory-Based
Heuristics for Explicit State Spaces”
Accepted
for publication in the Twenty First International
Joint Conferences on Artificial Intelligence.
(IJCAI-09) To appear.
34) Zhiifu Zhang,
Robert Holte, Jonathan Schaeffer, Nathan Sturtevant, Ariel Felner, “A* with
inconsistent heuristics" Accepted for publication in IJCAI-09. To appear.
33) Zahy Bnaya, Ariel
Felner and Solomon Eyal Shimony: "The Canadian
Traveler Problem with Rmote Sensing" Accepted for publication
in
IJCAI-09. To appear.
2008
Journals
32) Fan Yang,
Robert C. Holte, Joe Culberson, Uzi Zahavi and Ariel Felner "A General Theory of Additive State Space Abstractions"
Journal of Artificial Intelligence Research (JAIR),Volume 30 pages 213-247, 2007.
Conferences
31) Mehdi Samadi,
Maryam Siabani, Ariel Felner and Robert C. Holte: Compressing
Pattern Databases with Learning, Accepted for publication in ECAI-08. To
appear.
30) Uzi
Zahavi, Ariel Felner, Neil Burch and Robert C. Holte: "Predicting the Performance of IDA* with Conditional
Probabilities", Accepted for publication in AAAI-08. To appear.
29) Mehdi
Samadi, Ariel Felner and Jonathan Schaeffer: "Learning from Multiple Heuristic",
Accepted for publication in AAAI-08. To appear.
28) William
Yeoh, Ariel Felner and Sven Koenig: " BnB-ADOPT:
An Asynchronous Branch-and-Bound DCOP Algorithm", Accepted for
publication in AAMAS-08. To appear.
2007
Journals
27) Uzi
Zahavi, Ariel Felner, Jonathan Schaeffer and Robert Holte: "Duality
in Permutation State Spaces and the
Dual Search Algorithm. Artificial
Intelligence Journal (AIJ) 172, pp:514-540 2007.
26), Ariel
Felner, Richard E. Korf, Ram Meshulam and
Robert C. Holte: "Compressed Pattern
Databases", Journal of Artificial Intelligence Research (JAIR),Volume
30 pages 213-247, 2007.
Conferences
25) Ariel
Felner and Nir Ofek "Combining Perimeter Search
and Pattern Database Abstractions", Proceedings of the Seventh
International Symposium on Abstraction, Reformulation and Approximation
(SARA-07) Whistler,
24) Kenny
Daniel, Alex Nash, Sven Koenig, Ariel Felner: "Theta*:
Any-Angle Path Planning on Grids Proc of AAAI-07. pp: 1177-1183.
23) Uzi Zahavi,
Ariel Felner, Jonathan Schaeffer and Nathan Stutervant: "Inconsistent Heuristics", Proc of AAAI-07.
pp: 1221-1216. Also accepted for the selective poster session of AAAI-07.
22) Richard E.
Korf and Ariel Felner: "Recent Progress in Heuristic
Search: A Case Study of the Four-Peg Towers of Hanoi Problem", Proc
of IJCAI-07, pages 2324-2329.
2006
Journals
21) Robert C.
Holte, Ariel Felner, Jack Newton, Ram Meshulam, David Furcy: "Maximizing over Multiple Pattern Databases Speeds up
Heuristic Search", Artificial Intelligence Journal (AIJ). Volume
170, pages 1123-1136, November 2006.
20) Ariel
Felner, Roni Stern and Jeffery Rosenchein: "Searching
for Close Alternative Plans",Journal of Autonomous
Agents and Multi-Agent Systems. (JAAMAS) November 2006.
19) Ariel Felner, Yaron Shoshani, Yaniv
Altshuler and Alfred M. Bruckstein: "Multi-agent Physical
A* with Large Pheromones" Journal of Autonomous Agents and Multi-Agent Systems"
(JAAMAS) Volume 12(1), pages:3-34
January 2006
Conferences
18) Uzi Zahavi, Ariel Felner, Jonathan Schaeffer and
Robert Holte: "Dual Search in Permutation State
spaces", in proc. of AAAI-06.
17) Arnon Gilboa, Ariel Felner and Amnon Meisels:
"Distributed Navigation in an Unknown Physical
Environment", in Proc. of AAMAS-06, pages 553-560.
2005
Journals
16) Ariel Felner: “Finding Optimal Graph
Partitioning with Heuristic search”. In the “Annals of Mathematics and
Artificial Intelligence" Journal. (AMAI). Volume 45(3-4) pages 293-322
December 2005.
Conferences
15) Ariel
Felner, Uzi Zahavi, Jonathan Schaeffer and Robert Holte: "Dual Lookups in Pattern Databases", In proc. of
IJCAI-05,
14) Ram Meshualm, Ariel Felner and Sarit Kraus: "Utility
Based Multi-Agent System for Performing Repeated Navigation
Task" In proc. of AAMAS-05,
13) Ariel Felner and Amir Adler: "Solving the 24 Puzzle with Instance Dependent Pattern
Databases". In Proc. of SARA-05, pages 248-260. Edinburgh, July
2005. Also appeared in Lecture Notes in Computer Science, Volume 3607,
pages 248-260
12) Yaniv
Altshuler, Arie Matsliah and Ariel Felner "On the
Complexity of Physical Problems and a Swarm Algorithm for K-Clique Search in Physical Graphs" In proc. of the European
Conference of Complex Systems, November 14-18, 2005,
2004
Journals
11) Ariel Felner, Richard E. Korf and Sarit Hanan: “Additive Pattern Database Heuristics”, Journal
of Artificial Intelligence Research (JAIR), 22:279-318, November 2004. This paper
won the 2007 IJCAII-JAIR Runner up for the Best Paper prize. Honorable
mention as an elegant contribution to the area of heuristic search that
enhances the rich body of work on pattern database heuristics.
10) Ariel Felner, Roni Stern, Asaph Ben-Yair, Sarit
Kraus and Nathan Netanyahu: ”PHA*: Finding the Shortest
Path with A* in Unknown Physical
Environments.” Journal of Artificial Intelligence Research (JAIR).
21:631-670, (2004).
9) Omid Tabibi, Ariel Felner and Nathan Netannyahu "Blockage Detection in King and Pawn endings": International Computer Games Association
journal (ICGA), Vol. 27, No. 3, pp:150-158, September 2004.
Conferences
8) Ariel
Felner, Yaron Shoshani, Israel Wagner and Freddy Bruckstein: "Large Pheromones: A case study with Multi-agent PHA*". In the Forth International
Workshop on Ant Colony Optimization and Swarm Intelligence. (ANTS 2004)
Brussles, Bulgium , September 2004, pp:366-373. Also appeared in Lecture Notes
in Computer Science LNCS volume 3172/ 2004. pp:366-373.
7) Omid Tabibi, Ariel Felner and Nathan Netannyahu "Blockage
detection in pawn endgames", In the "Fourth International
Computer Games Association Conference" (ICGA),
6) Ariel
Felner, Ram Meshulam, Robert Holte and Richard E. Korf: “Compressing
Pattern Databases”.(pdf version) In Proc. of
AAAI04, pp: 638-641, San-Jose, Ca. July 2004.
5) Robet Holte, Jack Newton, Ariel Felner, Ram
Meshulam and David Furcy: “Multiple Pattern Databases”.
Proc. of ICAPS-2004, pp:122-131. June 2004, This paper was a runner up
for best paper prize of the conference.
2003
4) Ariel Felner, Richard E. Korf and Sarit Kraus: “KBFS: K-Best First Search”, Annals of Mathematics and Artificial
Intelligence Journal (AMAI), 39:19-39(2003).
3) Ariel Felner, Alex Pomeransky and Jeff
Rosenchein: “Searching for an Alternative Plan” Proc of
AAMAS-03. 33-40,
2002
2) Richard E. Korf and Ariel Felner: “Disjoint Pattern Database Heuristics”, Artificial
Intelligence Journal (AIJ) 134, 9-22,
(2002).
1) Ariel Felner, Roni Stern and Sarit Kraus: “PHA*: Performing A* in Unknown Physical Environments.” Proc. of AAMAS-02. 240-247.
Posters, Workshops and Abstracts:
2009
William Yeoh, Sven Koenig and Ariel Felner: "IDB_ADOPT: A depth-First Search DCOP Algorithms", in
the Eighth International Workshop on Distributed Constraint Reasoning.
IJCAI-07. January, 8 2007,
Asaf
Shiloni, Alon Levy, Ariel Felner and Meir Kalech: Ants
Meeting in an Unknown Environment: 10th International Workshop on
Multi-Agent-Based Simulation. May 2009. To appear.
2008
Zahy Bnaya,
Ariel Felner, Gal A. Kaminka and Eyal Shimony: "A
fresh look at sensor based navigation – navigation with sensing costs.",
Accepted for publication in STAIR-08. To appear.
Uzi Zahavi,
Ariel Felner, Neil Burch and Robert C. Holte: "Prediction
and bounds of IDA* with Conditional Probabilities", Accepted for
publication in STAIR-08. To appear.
Mehdi Samadai,
Ariel Felner and Jonathan Schaeffer: "Learning
from Heuristic Values", Accepted for publication in STAIR-08.
To appear.
2007
William Yeoh, Sven Koenig and Ariel Felner: "IDB_ADOPT: A depth-First Search DCOP Algorithms", in
the Eighth International Workshop on Distributed Constraint Reasoning.
IJCAI-07. January, 8 2007,
William Yeoh, Sven Koenig and Ariel Felner: " An
Asynchronous Branch-and-Bound DCOP Algorithm", in the Ninth
International Workshop on Distributed Constraint Reasoning. CP-07. September,
19 2007,
2006
Uzi Zahavi, Ariel Felner, Jonathan Schaeffer and
Robert Holte: "Dual Search in Permutation State
spaces", in The workshop on Heuristic Search, Memory Based Heuristics
and Their Applications. W9 of AAAI-06. July 17, 2006.
2004
Ariel Felner,
Yaron
Ariel Felner,
Yaron Shoshani: “Communication with Large Pheromones”.
Abstract in The First International Workshop on Environments for Multi agent
Systems (E4MAS) July 2004 New-York.
Submitted journal papers:
Ram Meshulam, Ariel Felner and Sarit Kraus: "Performing
repeated tasks in physical environments by a number of mobile agents" Subbmited
to JAIR May 2006. Revised version will be submitted.
Other publications:
Ariel Felner: “Improving
Search Techniques and using them in Different Environments. Ph.D Thesis.
Ariel Felner:
“Searching for an Alternative Plan”. M.Sc Thesis,
Currently, (Summer 2008) I have 32 published papers. However, go to see the home
page of my father, Prof.
Israel Felner. How many papers do we have in our family on average???
To answer the request of students and other
people, I add here slides of talks that I gave at different occasions. However,
I encourage the interested people to read the actual papers as they are much
more informed and accurate.
1) Solving the Graph-Partitioning Problem
4) Compressing Pattern Databases
5) Compressing Pattern Databases (short version) >> from AAAI-04
6) Recent Enhancements in Heuristic Search>> Talk at the CS Dept. of Ben-Gurion Univ. in Nov 9.
7) Dual Lookups in Pattern Database from IJCAI, summer 2005
8) Enhancing Pattern Databases Summarizes new advances in PDBs.