December 10, 2014
November 19, 2014
We introduce a new algorithm for multi-agent path finding, derived from the idea of meta-agent conflict-based search (MA-CBS). MA-CBS is a recently proposed algorithm for the multi-agent path finding problem. The algorithm is an extension of Conflict-Based Search (CBS), which automatically merges conflicting agents into meta-agents if the number of conflicts exceeds a certain threshold. However, the decision to merge agents is made according to an empirically chosen fixed threshold on the number of conflicts. The best threshold depends both on the domain and on the number of agents, and the nature of the dependence is not clearly understood.
We suggest a justification for the use of a fixed threshold on the number of conflicts based on the analysis of a model problem. Following the suggested justification, we introduce a new algorithm, which differs in the ways when and how meta-agents are created and handled during search. The new algorithm exhibits considerably better performance compared to the original algorithm. The new algorithm is evaluated on several sets of problems, chosen to highlight different aspects of the algorithm.
This is a short version of Justifying and Improving MA-CBS.
October 2, 2014
October 8, 2013
My dissertation “Rational Metareasoning in Problem-Solving Search”.
August 22, 2012
July 24, 2012
May 30, 2011
I am having the pleasure of preparing a poster for IJCAI 2011, for the first time in my life. Both the IJCAI and a poster. Fiddling with PowerPoint or Illustrator is painful. Beautiful slides can be prepared with S5 using HTML and CSS; a poster in HTML and CSS is also worth a try.
I am less fearful of preparing conference posters now.
April 5, 2011
Modern scientific digital typography got stuck in a local maximum. LATEX — an archaic idiosyncratical tool — does everything wrong, even hyphenation and paragraph formatting. But this wrongdoing is so polished that cannot be improved. There will be no better LATEX until the ugly fashion for frozen fossils of scientific mind will pass away, and there will be no LATEX at all.
C++ is a zero-paradigm (be as tasteless as you like) specification-oriented (perfect for implementing faulty designs) programming language. Corporations love to hire C++ programmers, those guys do everything for money. I want mutuality from my languages, I write programs only with tools I love.
And get paid well.
May 25, 2010
A good design is approximately optimal. When a reasonable probabilistic model is available, the design can be optimized in expectation: flight delays should be rare, e-mails should arrive within seconds, and buildings should protect from elements and provide comfort on most days of the year. But a single disaster can cause big trouble.