Contact:
We are in the Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo. We are also affiliated with the Graduate Program on Environmental Sciences (GPES)
Research Areas
Artificial Intelligence, Heuristic Search, Planning, Constraint Programming, Parallel Programming, Combinatorial Optimization, Machine Learning, Metaheuristics, Evolutionary Computation, and Autonomous Robotics.
Current Lab Members
 Faculty: Alex Fukunaga
 Ph.D. Students: Masataro Asai
 Masters Students: Kazuto Nobuhara, Yuu Jinnai, Satoru Horie, Shuuwa Miura, Takefumi Yamamura
 Undergraduate Students: Shunji Lin (Environmental Science), , Shaun Zen (Environmental Science), Nobutaka Ito (Informatics), Tomofumi Kitamura (Informatics)
Former Lab Members
 Shoma Endo (Undergraduate 2013, Masters 2015), Yuki Nakano (Masters 2015), Ryoji Tanabe (Ph.D. 2015), Masahiro Inohana (Undergraduate 2013, Masters 2014).
 JSPS Summer Program / NSF EAPSI Fellow: Richard Freedman (University of Massachussetts, Amherst)
Selected Recent Publications
 Jinnai Y, Fukunaga A. Automated Creation of an Efficient Work Distribution Method for Parallel BestFirst Search. Proc. 26th International Conference on Automated Planning and Scheduling (ICAPS2016) (accepted).
 Endo S, Asai M, Fukunaga A. Plan Optimization Based on Windows and Optimization Algorithms Applied in Sequence. Proc. ICAPS Workshop on Heuristics and Search for DomainIndependent Planning (HSDIP)
 Asai M, Fukunaga A. Tiebreaking Strategies for A* Search: How to Explore the Final Frontier. Proc. 30th AAAI Conference on Artificial Intelligence (AAAI16) (pdf).
 Jinnai Y, Fukunaga A. Abstract Zobrist Hash: An Efficient Work Distribution Method for Parallel BestFirst Search. Proc. 30th AAAI Conference on Artificial Intelligence (AAAI16) (pdf).
 Imai T, Fukunaga A. On a Practical, IntegerLinear Programming Model for DeleteFree Tasks and its Use as a Heuristic for CostOptimal Planning. Journal of Artificial Intelligence Research (JAIR), Volume 54, pages 631677.(pdf at JAIR site)
 Asai M, Fukunaga A. Solving LargeScale Problems by Decomposition and Macro Generation. Proc. 25th International Confernce on Automated Planning and Scheduling (ICAPS2015) (pdf)
 Asai M, Fukunaga A. Fully Automated Cyclic Planning for LargeScale Manufacturing Domains. Proc. 24th International Confernce on Automated Planning and Scheduling (ICAPS2014), pp.2028(pdf)

Tanabe R, Fukunaga A. SuccessHistory Based Parameter Adaptation for Differential Evolution. Proc. of IEEE Congress on Evolutionary Computation (CEC2013)(pdf)(Ryoji's SHADE code).
 LSHADE, an improved implementation of SHADE by Ryoji was the winner of the CEC2014 Competition on RealParameter Single Objective Optimization. In addition, the top 4 algorithms in the CEC2015 Competition were all based on SHADE.

Kishimoto A, Fukunaga A, Botea A. Evaluation of a Simple, Scalable, Parallel BestFirst Search
Strategy. Artificial Intelligence, 195:222248, 2013. (Elsevier), (arXiv version)
(If you're interested in HashDistributed A*, please read this journal version, which significantly expands upon the ICAPS2009 paper.
HDA* was scaled up to 2400 cores (vs 128 cores in the ICAPS paper), there are many new experiments analyzing the behavior of HDA* indepth, as well as a comparisons to TDS).
 [Earlier, conference paper]
Kishimoto A, Fukunaga A, Botea A.
Scalable, parallel bestfirst search for optimal sequential planning.
Proc. 19th Int. Conference on Automated Planning and Scheduling
(ICAPS2009)
Best Paper Award (pdf)
 [Earlier, conference paper]
Kishimoto A, Fukunaga A, Botea A.
Scalable, parallel bestfirst search for optimal sequential planning.
Proc. 19th Int. Conference on Automated Planning and Scheduling
(ICAPS2009)
 Fukunaga A, Kishimoto A, Botea A. Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms on Clouds, Grids, and Shared Clusters. Procedings of AAAI2012. (pdf)
 Fukunaga A. Automated discovery of local search heuristics for satisfiability testing. Evolutionary Computation (MIT Press), Vol 16, Number 1, pp.3161, 2008. (pdf)
List of Publications
[Note: In computer science, full papers describing preliminary work are sometimes first submitted to lightly refereed workshops, and further developed versions are later submitted to more selective, refereed conferences. Refereed conference papers are considered archival publications (top conferences have <30% acceptance rates), and therefore, many projects are considered "completed" after a conference publication. However, since conference papers have page limitations, significantly extended versions of conference papers are sometimes submitted to journals. See the ACM policy and IEEE guidelines regarding these practices. Below, I list the most complete publications of my research results. Thus, workshop papers aren't listed if they've been superseded by later, conference or journal papers. However, workshop papers with unique materials not found in later papers are listed.] Jinnai Y, Fukunaga A. Automated Creation of an Efficient Work Distribution Method for Parallel BestFirst Search. Proc. 26th International Conference on Automated Planning and Scheduling (ICAPS2016) (accepted).
 Asai M, Fukunaga A. Tiebreaking Strategies for A* Search: How to Explore the Final Frontier. Proc. 30th AAAI Conference on Artificial Intelligence (AAAI16) (accepted)(pdf).
 Jinnai Y, Fukunaga A. Abstract Zobrist Hash: An Efficient Work Distribution Method for Parallel BestFirst Search. Proc. 30th AAAI Conference on Artificial Intelligence (AAAI16) (accepted)(pdf).
 Imai T, Fukunaga A. On a Practical, IntegerLinear Programming Model for DeleteFree Tasks and its Use as a Heuristic for CostOptimal Planning. Journal of Artificial Intelligence Research (JAIR), Volume 54, pages 631677.(pdf at JAIR site)
 [Earlier, conference paper] Imai T, Fukunaga A. A Practical, IntegerLinear Programming Model for the DeleteRelaxation in CostOptimal Planning. Proc. 21st European Conference on Artificial Intelligence (ECAI2014). (pdf)
 Asai M, Fukunaga A. Solving LargeScale Problems by Decomposition and Macro Generation. Proc. 25th International Confernce on Automated Planning and Scheduling (ICAPS2015) (pdf)
 Tanabe R, Fukunaga A. Tuning Differential Evolution for Cheap, Medium, and Expensive Computational Budgets, Proc. IEEE Congress on Evolutionary Computation (CEC2015), Sendai, May, 2015, pp. 20182025
 Aranha C, Tanabe R, Chassagne R, Fukunaga F. Optimization of Oil Reservoir Models Using Tuned Evolutionary Algorithms and Adaptive Differential Evolution, Proc. IEEE Congress on Evolutionary Computation (CEC2015), Sendai, May, 2015, pp. 877884
 Asai M, Fukunaga A. Fully Automated Cyclic Planning for LargeScale Manufacturing Domains. Proc. 24th International Confernce on Automated Planning and Scheduling (ICAPS2014). (pdf)
 Asai, M, Fukunaga, A. Applying Problem Decomposition to Extremely Large Domains. ICAPS Workshop on Knowledge Engineering for Planning and Scheduling (KEPS2014). (pdf)
 Tanabe R, Fukunaga A. Reevaluating Exponential Crossover in Differential Evolution, Proc. Parallel Problem Solving from Nature (PPSN2014). (pdf)
 Tanabe R, Fukunaga A. On the Pathological Behavior of Adaptive Differential Evolution on Hybrid Objective Functions. Proc. ACM Genetic and Evolutionary Computation Conference (GECCO2014). (pdf)
 Tanabe R, Fukunaga A. Improving The Search Performance of SHADE Using Linear Population Size Reduction, Proc. IEEE Congress on Evolutionary Computation (CEC2014). (pdf)
 Fukunaga A. An Improved Search Algorithm for Minimal Perturbation. Proc. 19th International Conference on Principles and Practice of Constraint Programming (CP2013)(pdf)
 Tanabe R, Fukunaga A. Evaluation of a Randomized Parameter Setting Strategy for IslandModel Evolutionary Algorithms. Proc. of IEEE Congress on Evolutionary Computation (CEC2013)(pdf)
 Tanabe R, Fukunaga A. SuccessHistory Based Parameter Adaptation for Differential Evolution. Proc. of IEEE Congress on Evolutionary Computation (CEC2013)(pdf)
 Ochi K, Fukunaga A, Kondo C, Maeda M, Hasegawa F, Kawano Y. A SteadyState Model for Automated Sequence Generation in a Robotic Assembly System. Proc. ICAPS Scheduling and Planning Applications Workshop (SPARK2013), pp.2734.

Kishimoto A, Fukunaga A, Botea A. Evaluation of a Simple, Scalable, Parallel BestFirst Search
Strategy. Artificial Intelligence, 195:222248, 2013. (Elsevier), (arXiv version)
(If you're interested in HashDistributed A*, please read this journal version, which significantly expands upon the ICAPS2009 paper.
HDA* was scaled up to 2400 cores (vs 128 cores in the ICAPS paper), there are many new experiments analyzing the behavior of HDA* indepth, as well as a comparisons to TDS).
 [Earlier, conference paper]
Kishimoto A, Fukunaga A, Botea A.
Scalable, parallel bestfirst search for optimal sequential planning.
Proc. 19th Int. Conference on Automated Planning and Scheduling
(ICAPS2009)
Best Paper Award (pdf)
 [Earlier, conference paper]
Kishimoto A, Fukunaga A, Botea A.
Scalable, parallel bestfirst search for optimal sequential planning.
Proc. 19th Int. Conference on Automated Planning and Scheduling
(ICAPS2009)
 Fukunaga A, Kishimoto A, Botea A. Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms on Clouds, Grids, and Shared Clusters. Procedings of AAAI2012. (pdf)

Fukunaga A, Hiruma H, Komiya K, Iba H.
Evolving Controllers for HighLevel Applications on a Service Robot: A Case Study of
Visitor Flow Management in an Exhibition Space.
Genetic Programming and Evolvable Machines, 13(2):239263, 2012.
(pdf Draft)
(SpringerLink)
 [Earlier, conference paper  the GPEM journal version includes many more simulation experiments] Hiruma H, Fukunaga A, Komiya K, Iba H. Evolving a Goal Selection Strategy for a Robot Tour Guide. Proc. IEEE Congress on Evolutionary Computation (CEC2011), New Orleans, pp.137144.

Fukunaga A.
A BranchandBound Algorithm for Hard, Multiple Knapsack Problems.
Annals of Operations Research , 184:97119, 2011.
(pdf Draft)
(SpringerLink)
 [Earlier, conference version] Fukunaga A. Integrating Symmetry, Dominance, and Boundandbound in a Multiple Knapsack Solver. Proceedings of the Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR08), Paris, France, 2008. (pdf)
 Gong Y, Fukunaga A. A Distributed, IslandModel Genetic Algorithm Using Heterogeneous Parameter Settings. Proc. IEEE Congress on Evolutionary Computation (CEC2011), New Orleans, pp.137144.
 Akagi Y, Kishimoto A, Fukunaga A. On Transposition Tables for SingleAgent Search and Planning: Summary of Results. Proc. 3rd Annual Symposium on Combinatoril Search (SoCS), pp.29, 2010. (pdf)
 Fukunaga A. Search spaces for minperturbation repair. Proc. 15th Int. Conf. on Principles and Practice of Constraint Programming (CP2009), pp.383390, 2009. (pdf)
 Fukunaga A. A Massively Parallel GP for Discovering Satisfiability Solvers. Proc. IEEE Congress on Evolutionary Computation (CEC2009), Trondheim, Norway, May, 2009.
 Fukunaga A, Tazoe S. Combining Multiple Representations in a Genetic Algorithm for the Multiple Knapsack Problem Proc. IEEE Congress on Evolutionary Computation (CEC2009), Trondheim, Norway, May, 2009.
 Gong Y, Fukunaga A. Fault Tolerance in Distributed Genetic Algorithms with Tree Topologies IEEE Congress on Evolutionary Computation (CEC2009), Trondheim, Norway, May, 2009.

Fukunaga A.
Automated discovery of local search heuristics for satisfiability testing.
Evolutionary Computation (MIT Press), Vol 16, Number 1, pp.3161, 2008.
(pdf) (significantly expands upon the GECCO04 and AAAI02 papers below)

Fukunaga A.
Evolving Local Search Heuristics for SAT.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2004), Seattle, WA, 2004.
[HumanCompetitive Results Award, Silver Prize] (pdf) [Describes the 2nd implementation of CLASS (in Common Lisp), which results in a much faster solver compared to the AAAI02 implementation, and outperformed fast C implementation of Walksat and Novelty+]  Fukunaga A. Automated Discovery of Composite SAT VariableSelection Heuristics. Proceedings of the National Conf. on Artificial Intelligence), 2002 (AAAI02), Edmonton, Alberta, Canada, pp.641648. (pdf) [Describes the first implementation of CLASS (in C++ and tcl). While the search was efficient (with respect to the # of flips to solve problems), the runtime was not impressive due to the ugly implementation of the embedded heuristic]

Fukunaga A.
Evolving Local Search Heuristics for SAT.
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2004), Seattle, WA, 2004.

Fukunaga A, Korf RE.
Bincompletion algorithms for multicontainer packing, knapsack, and covering problems.
Journal of Artificial Intelligence Research. vol 28, pp.393429, 2007.
(pdf)
 [Earlier, conference version] Fukunaga A, Korf RE. Bincompletion algorithms for multicontainer packing and covering problems. Proc. International Joint Conference on Artificial Intelligence, 2005. (IJCAI05) Edinburgh, Scotland, pp.117124. (pdf)

Castano A, Fukunaga A, Biesiadecki J, Neakrase L, Whelley P, Greeley R, Lemmon M, Castano R, Chien S.
Automatic detection of dust devils and clouds on Mars. Machine Vision and Applications. vol 19(56), pp.467482, 2008.
(pdf)
 [Earlier, conference version] Castano A, Fukunaga A, Biesiadecki J, Neakrase L, Whelley P, Greeley R, Lemmon M, Castano R, Chien S. Autonomous detection of dust devils and clouds on Mars. Proceedings of the International Conference on Image Processing (ICIP06), Atlanta, GA 2006, pp.27652768.
 Chien S, Castano R, Bornstein B, Fukunaga A, Castano A, Biesiadecki J, Greeley R, Whelley P, Lemmon M. Results from Automated Cloud and Dust Devil Detection Onboard the MER rovers. Proceedings of the Ninth International Symposium on Artificial Intelligence, Robotics, and Automation in Space (iSAIRAS08), Los Angeles, CA 2008. [This iSAIRAS08 paper reports some results obtained using the software after it was actually deployed on Mars (after the journal paper was in press)]
 Fukunaga A. A new grouping genetic algorithm for the multiple knapsack problem. Proc IEEE Congress on Evolutionary Computation (CEC2008), Hong Kong, China.pp.22252232, June 16, 2008.
 Castano R, Estlin T, Gaines D, Castano A, Chouinard C, Bornstein B, Anderson R, Chien S, Fukunaga A, Judd M. Opportunistic Rover Science: Finding and Reacting to Rocks, Clouds, and Dust Devils. Proceedings of the IEEE Aerospace Conference, March 2006. (pdf)
 Fukunaga A. Efficient Implementation of SAT Local Search. Proceedings of the Seventh International Conf. on Theory and Applications of Satisfiability Testing (SAT2004), Vancouver, British Columbia, 2004. (pdf)
 Fukunaga A, Rabideau G, Chien S Robust local search for spacecraft operations using adaptive noise. Proceedings of the 4th International Workshop on Planning and Scheduling for Space (IWPSS04), Darmstadt, Germany, 2004 (pdf)
 Fukunaga A. Complete restart strategies using a compact representation of the explored search space. IJCAI03 Workshop on Stochastic Search Algorithms, Acapulco, Mexico. Note: several typographical errors in the original workshop paper have been corrected (In the example in page 3, Section 2, some AND's and OR's were unintentionally reversed). (pdf)

Fukunaga A, Hamilton E, Fama J, Andre D, Matan O, Nourbakhsh.
Staff Scheduling for Inbound Call Centers and Customer Contact Centers. AI Magazine 23(4): Winter 2002, pp.3040.
Special issue on selected papers from Innovative Applications of AI 2002.
(pdf)
 [Earlier, conference version] Fukunaga A, Hamilton E, Fama J, Andre D, Matan O, Nourbakhsh. Staff Scheduling for Inbound Call Centers and Customer Contact Centers. Proc. Innovative Applications of Artificial Intelligence, 2002 (IAAI02), Edmonton, Alberta, Canada.
 Fukunaga A. Genetic Algorithm Portfolios. Proceedings of the IEEE Congress on Evolutionary Computation (CEC2000), San Diego, CA, 2000. (pdf)
 Rabideau G, Knight R, Chien S, Fukunaga A, Govindjee A. Iterative repair planning for spacecraft operations in the ASPEN system. Proceedings of the International Syposium on Artificial Intelligence, Robotics, and Automation in Space (iSAIRAS99), Noordwijk, The Netherlands, June, 1999. (pdf)
 Smith B, Sherwood R, Govindjee A, Yan D, Rabideau G, Chien S, Fukunaga A. Representing Spacecraft Mission Planning Knowledge in ASPEN. AIPS98 Workshop on Knowledge Engineering and Acquisition for Planning, June 1998. (AAAI Technical Report WS9803), pp. 5872. (pdf)
 Stoica A, Fukunaga A, Hayworth K. Evolvable Hardware for Space Applications. Proceedings of the International Conference on Evolvable Systems (ICES98), Lausanne, Switzerland, August, 1998. (pdf)
 Sherwood R, Govindjee A, Yan D, Rabideau G, Chien S, Fukunaga A. Using ASPEN to Automate EO1 Activity Planning. Proceedings of the IEEE Aerospace Conference, Snowmass, CO, March, 1998. (pdf)
 Fukunaga A. Restart Scheduling for Genetic Algorithms. Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSNV), Leiden, Netherlands, September, 1998. (pdf)
 Fukunaga A, Stechert A, Mutz D. A genome compiler for highperformance genetic programming. Proceedings of the 3rd Annual Genetic Programming Conference, 1998 (GP98). (pdf)
 Fukunaga A, Stechert A. Evolving nonlinear predictive models for lossless image compression with genetic programming. Proceedings of the 3rd Annual Genetic Programming Conference, 1998 (GP98). (pdf)
 Fukunaga A. Rabideau G, Chien S, Yan D. ASPEN: An Application Framework for Automated Planning and Scheduling of Spacecraft Control and Operations. Proceedings of the International Symposium on Artificial Intelligence, Robotics and Automation in Space (iSAIRAS97), Tokyo, Japan, 1997, pp. 181187 (pdf)
 Fukunaga A. VariableSelection Heuristics in Local Search for Satisfiability Testing. Proceedings of the National Conference on Artificial Intelligence (AAAI97), Providence, RI, 1997, pp.275280. (pdf)
 Fukunaga A. Application of an Incremental Evolution Technique to Spacecraft Design Optimization. Proc. IEEE International Conference on Evolutionary Computation (ICEC'97), Indianapolis, IN, 1997, pp. 431435

Fukunaga A, Chien S, Mutz D, Sherwood R, Stechert A.
Automating the Process of Optimization in Spacecraft Design.
Proc. IEEE Aerospace Conference, Snowmass CO, 1997, vol. 4 pp. 411428
(pdf)
[Describes OASIS, a spacecraft design optimization system which includes the blackbox optimizer described in the IEA/AIE paper below, as well as a metalevel optimizer which tries to match an appropriate configuration of the blackbox optimizer to each problem instance.]
 Fukunaga A, Stechert A. An Evolutionary Optimization System for Spacecraft Design. Proceedings of the Tenth International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE97)}, Atlanta, GA, 1997, pp.16. [Describes DEVO (Design EVOlver), which is the blackbox optimization component of the OASIS system]

Cao Y, Fukunaga A, Kahng AB.
Cooperative Mobile Robotics: Antecedents and Directions.
Autonomous Robots vol 4, 1997.
[Reprinted as a chapter in the book: Robot Colonies, Arkin RC and
Bekey GA, eds., Kluwer Academic Press, ISBN 0792399048, 1997]
(pdf)
 [Earlier, conference version] Cao Y, Fukunaga A, Kahng AB, Meng F. Cooperative Mobile Robotics: Antecedents and Directions. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems 1995 (IROS95), pp.226234.
 Fukunaga A, Huang DJH, Kahng AB. LargeStep Markov Chain Variants for Netlist Partitioning. Proceedings of the IEEE Int. Symposium on Circuits and Systems, 1996 (ISCAS96)., pp.4969 (vol 4). (pdf)

Auslander J, Fukunaga A, Partovi H, Christensen J, Hsu L, Reiss P,
Shuman A, Marks J, Ngo JT.
Further Experience with ControllerBased Automatic Motion Synthesis for Articulated Figures.
ACM Transactions on Graphics, vol 14, no. 4, pp. 311336, 1995.
(pdf)

Additional details on 2D motion synthesis can be found in the following technical reports. TR0594 was submitted to SIGGRAPH94 but it was rejected (my first rejected paper!), so it was combined with the 3D motion synthesis work of Auslander and Partovi and submitted to the ACM Transactions on Graphics.
 Fukunaga A, Christensen J, Ngo JT, Marks J. A Comparative Study of Search and Optimization Algorithms for the Automatic Control of Physically Realistic 2D Animated Figures. Technical Report TR2394, Center for Research in Computing Technology, Harvard University, August, 1994.
 Fukunaga A, Hsu L, Reiss P, Shuman A, Christensen J, Marks J, Ngo JT. Motion Synthesis Techniques for 2D Articulated Figures. Technical Report TR0594, Center for Research in Computing Technology, Harvard University, March, 1994.
 Fukunaga A, Kahng AB. Improving the Performance of Evolutionary Optimization by Dynamically Scaling the Evaluation Function. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC95), November, 1995, pp. 182187. (pdf)
 Fukunaga A, Ngo JT, Marks J. Solving the Spacetime Constraints Problem Using Evolutionary Programming Algorithms. Proceedings of the 3rd Annual Conference on Evolutionary Programming (EP94), San Diego, CA, World Scientific, 1994. (pdf)
 Fukunaga A, Kimura TD, Pree W. ObjectOriented Development of a Data Flow Visual Language System. Proceedings of the IEEE/CS Symposium on Visual Languages (VL93), Bergen, Norway, IEEE Press, 1993, pp. 134141. (pdf)
 Fukunaga A, Pree W, Kimura TD. Functions as Data Objects in a Data Flow Based Visual Language. Proceedings of the ACM Computer Science Conference, Indianapolis, IN, ACM Press, 1993.
Software
 CLMPI  A portable, Common Lisp binding for the Message Pasing Interface (MPI). Enables messagepassing based parallel Common Lisp programming on either a cluster or a single multicore machine.