The
web site of Ariel Felner moved in August 2011
Here is a link to the new web site of
Ariel Felner.
============================================
This
is the old web site. It is not updated.
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.