15 Search Results for "Young, R. Michael"

Document
DOI: 10.4230/LIPIcs.SEA.2023.13
Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem

Authors: Ömer Burak Onar, Tınaz Ekim, and Z. Caner Taşkın

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
This paper considers the Maximum Selective Tree Problem (MSelTP) as a generalization of the Maximum Induced Tree problem. Given an undirected graph with a partition of its vertex set into clusters, MSelTP aims to choose the maximum number of vertices such that at most one vertex per cluster is selected and the graph induced by the selected vertices is a tree. To the best of our knowledge, MSelTP has not been studied before although several related optimization problems have been investigated in the literature. We propose two mixed integer programming formulations for MSelTP; one based on connectivity constraints, the other based on cycle elimination constraints. In addition, we develop two exact cutting plane procedures to solve the problem to optimality. On graphs with up to 25 clusters, up to 250 vertices, and varying densities, we conduct computational experiments to compare the results of two solution procedures with solving a compact integer programming formulation of MSelTP. Our experiments indicate that the algorithm CPAXnY outperforms the other procedures overall except for graphs with low density and large cluster size, and that the algorithm CPAX yields better results in terms of the average time of instances optimally solved and the overall average time.
Cite as

Ömer Burak Onar, Tınaz Ekim, and Z. Caner Taşkın. Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 13:1-13:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{onar_et_al:LIPIcs.SEA.2023.13,
  author =	{Onar, \"{O}mer Burak and Ekim, T{\i}naz and Ta\c{s}k{\i}n, Z. Caner},
  title =	{{Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.13},
  URN =		{urn:nbn:de:0030-drops-183634},
  doi =		{10.4230/LIPIcs.SEA.2023.13},
  annote =	{Keywords: maximum induced tree, selective tree, cutting plane, separation algorithm, mixed integer programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.5
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 5:1-5:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2022.5,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.5},
  URN =		{urn:nbn:de:0030-drops-160136},
  doi =		{10.4230/LIPIcs.SoCG.2022.5},
  annote =	{Keywords: Simple drawings, simple topological graphs, disjoint edges, plane matching, plane path}
}
Document
DOI: 10.4230/OASIcs.SOSA.2019.16
Simple Contention Resolution via Multiplicative Weight Updates

Authors: Yi-Jun Chang, Wenyu Jin, and Seth Pettie

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. To ground the discussion, suppose (identical) devices wake up at various times, and must send a single packet over a shared multiple-access channel. In each time step they may attempt to send their packet; they receive ternary feedback {0,1,2^+} from the channel, 0 indicating silence (no one attempted transmission), 1 indicating success (one device successfully transmitted), and 2^+ indicating noise. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e-O(epsilon), for any epsilon>0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weight-type update to p_i. p_i <- { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{-epsilon/(e-2)} upon hearing noise (2^+) }. This scheme works well even if the introduction of devices/packets is adversarial, and even if the adversary can jam time slots (make noise) at will. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e-epsilon, excluding O(J) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm.
Cite as

Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:OASIcs.SOSA.2019.16,
  author =	{Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth},
  title =	{{Simple Contention Resolution via Multiplicative Weight Updates}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{16:1--16:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16},
  URN =		{urn:nbn:de:0030-drops-100426},
  doi =		{10.4230/OASIcs.SOSA.2019.16},
  annote =	{Keywords: Contention resolution, multiplicative weight update method}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.11
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 11:1-11:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
Document
DOI: 10.4230/DagRep.7.11.86
Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471)

Authors: Pieter Spronck, Elisabeth André, Michael Cook, and Mike Preuß

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
With the dramatic growth of the game industry over the past decade, its rapid inclusion in many sectors of today's society, and the increased complexity of games, game development has reached a point where it is no longer humanly possible to use only manual techniques to create games. Large parts of games need to be designed, built, and tested automatically. In recent years, researchers have delved into artificial intelligence techniques to support, assist, and even drive game development. Such techniques include procedural content generation, automated narration, player modelling and adaptation, and automated game design. This research is still very young, but already the games industry is taking small steps to integrate some of these techniques in their approach to design. The goal of this seminar was to bring together researchers and industry representatives who work at the forefront of artificial intelligence (AI) and computational intelligence (CI) in games, to (1) explore and extend the possibilities of AI-driven game design, (2) to identify the most viable applications of AI-driven game design in the game industry, and (3) to investigate new approaches to AI-driven game design. To this end, the seminar included a wide range of researchers and developers, including specialists in AI/CI for abstract games, commercial video games, and serious games. Thus, it fostered a better understanding of and unified vision on AI-driven game design, using input from both scientists as well as AI specialists from industry.
Cite as

Pieter Spronck, Elisabeth André, Michael Cook, and Mike Preuß. Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471). In Dagstuhl Reports, Volume 7, Issue 11, pp. 86-129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{spronck_et_al:DagRep.7.11.86,
  author =	{Spronck, Pieter and Andr\'{e}, Elisabeth and Cook, Michael and Preu{\ss}, Mike},
  title =	{{Artificial and Computational Intelligence in Games: AI-Driven Game Design (Dagstuhl Seminar 17471)}},
  pages =	{86--129},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Spronck, Pieter and Andr\'{e}, Elisabeth and Cook, Michael and Preu{\ss}, Mike},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.11.86},
  URN =		{urn:nbn:de:0030-drops-86722},
  doi =		{10.4230/DagRep.7.11.86},
  annote =	{Keywords: dynamical systems, entertainment modeling, game design, multi-agent systems, serious games}
}
Document
DOI: 10.4230/DagRep.7.1.19
Automated Program Repair (Dagstuhl Seminar 17022)

Authors: Sunghun Kim, Claire Le Goues, Michael Pradel, and Abhik Roychoudhury

Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17022 "Automated Program Repair". The seminar participants presented and discussed their research through formal and informal presentations. In particular, the seminar covered work related to search-based program repair, semantic program repair, and repair of non-functional properties. As a result of the seminar, several participants plan to launch various follow-up activities, such as a program repair competition, which would help to further establish and guide this young field of research.
Cite as

Sunghun Kim, Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. Automated Program Repair (Dagstuhl Seminar 17022). In Dagstuhl Reports, Volume 7, Issue 1, pp. 19-31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{kim_et_al:DagRep.7.1.19,
  author =	{Kim, Sunghun and Le Goues, Claire and Pradel, Michael and Roychoudhury, Abhik},
  title =	{{Automated Program Repair (Dagstuhl Seminar 17022)}},
  pages =	{19--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{1},
  editor =	{Kim, Sunghun and Le Goues, Claire and Pradel, Michael and Roychoudhury, Abhik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.1.19},
  URN =		{urn:nbn:de:0030-drops-71767},
  doi =		{10.4230/DagRep.7.1.19},
  annote =	{Keywords: Program repair, program analysis, software engineering}
}
Document
DOI: 10.4230/OASIcs.CMN.2016.9
Summarizing and Comparing Story Plans

Authors: Adam Amos-Binks, David L. Roberts, and R. Michael Young

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract
Branching story games have gained popularity for creating unique playing experiences by adapting story content in response to user actions. Research in interactive narrative (IN) uses automated planning to generate story plans for a given story problem. However, a story planner can generate multiple story plan solutions, all of which equally-satisfy the story problem definition but contain different story content. These differences in story content are key to understanding the story branches in a story problem's solution space, however we lack narrative-theoretic metrics to compare story plans. We address this gap by first defining a story plan summarization model to capture the important story semantics from a story plan. Secondly, we define a story plan comparison metric that compares story plans based on the summarization model. Using the Glaive narrative planner and a simple story problem, we demonstrate the usefulness of using the summarization model and distance metric to characterize the different story branches in a story problem's solution space.
Cite as

Adam Amos-Binks, David L. Roberts, and R. Michael Young. Summarizing and Comparing Story Plans. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amosbinks_et_al:OASIcs.CMN.2016.9,
  author =	{Amos-Binks, Adam and Roberts, David L. and Young, R. Michael},
  title =	{{Summarizing and Comparing Story Plans}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{9:1--9:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.9},
  URN =		{urn:nbn:de:0030-drops-67100},
  doi =		{10.4230/OASIcs.CMN.2016.9},
  annote =	{Keywords: artifical intelligence, planning, narrative, comparison, story}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.52
Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors: Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)).
Cite as

Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mahoney_et_al:LIPIcs.ICALP.2016.52,
  author =	{Mahoney, Michael W. and Rao, Satish and Wang, Di and Zhang, Peng},
  title =	{{Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^\{-3\}) Time}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52},
  URN =		{urn:nbn:de:0030-drops-63335},
  doi =		{10.4230/LIPIcs.ICALP.2016.52},
  annote =	{Keywords: Mixed packing and covering, Linear program, Approximation algorithm, Parallel algorithm}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.45
Impulse: a Formal Characterization of Story

Authors: Markus Eger, Camille Barot, and R. Michael Young

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
We present a novel representation of narratives at the story level called Impulse. It combines a temporal representation of a story’s actions and events with a representation of the mental models of the story’s characters into a cohesive, logic-based language. We show the expressiveness of this approach by encoding a story fragment, and compare it to other formal story representations in terms of representational dimensions. We also acknowledge the computational complexity of our approach and argue that a restricted subset still provides a high degree of expressive power
Cite as

Markus Eger, Camille Barot, and R. Michael Young. Impulse: a Formal Characterization of Story. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 45-53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{eger_et_al:OASIcs.CMN.2015.45,
  author =	{Eger, Markus and Barot, Camille and Young, R. Michael},
  title =	{{Impulse: a Formal Characterization of Story}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{45--53},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.45},
  URN =		{urn:nbn:de:0030-drops-52800},
  doi =		{10.4230/OASIcs.CMN.2015.45},
  annote =	{Keywords: Narrative, logic, representation, mental models, time}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.152
Good Timing for Computational Models of Narrative Discourse

Authors: David R. Winer, Adam A. Amos-Binks, Camille Barot, and R. Michael Young

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
The temporal order in which story events are presented in discourse can greatly impact how readers experience narrative; however, it remains unclear how narrative systems can leverage temporal order to affect comprehension and experience. We define structural properties of discourse which provide a basis for computational narratologists to reason about good timing, such as when readers learn about event relationships.
Cite as

David R. Winer, Adam A. Amos-Binks, Camille Barot, and R. Michael Young. Good Timing for Computational Models of Narrative Discourse. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 152-156, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{winer_et_al:OASIcs.CMN.2015.152,
  author =	{Winer, David R. and Amos-Binks, Adam A. and Barot, Camille and Young, R. Michael},
  title =	{{Good Timing for Computational Models of Narrative Discourse}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{152--156},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.152},
  URN =		{urn:nbn:de:0030-drops-52897},
  doi =		{10.4230/OASIcs.CMN.2015.152},
  annote =	{Keywords: causal inference, narrative, discourse structure, computational model}
}
Document
DOI: 10.4230/OASIcs.CMN.2013.4
CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation

Authors: Julio César Bahamón and R. Michael Young

Published in: OASIcs, Volume 32, 2013 Workshop on Computational Models of Narrative

Abstract
The quality and believability of a story can be significantly enhanced by the presence of compelling characters. Characters can be made more compelling by the portrayal of a distinguishable personality. This paper presents an algorithm that formalizes an approach previously described for the incorporation of character personality in narrative that is automatically generated. The approach is based on a computational model that operationalizes personality as behavior that results from the choices made by characters in the course of a story. This operationalization is based on the Big Five personality structure and results from behavioral psychology studies that link behavior to personality traits.
Cite as

Julio César Bahamón and R. Michael Young. CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation. In 2013 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 32, pp. 4-23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bahamon_et_al:OASIcs.CMN.2013.4,
  author =	{Baham\'{o}n, Julio C\'{e}sar and Young, R. Michael},
  title =	{{CB-POCL: A Choice-Based Algorithm for Character Personality in Planning-based Narrative Generation}},
  booktitle =	{2013 Workshop on Computational Models of Narrative},
  pages =	{4--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-57-6},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{32},
  editor =	{Finlayson, Mark A. and Fisseni, Bernhard and L\"{o}we, Benedikt and Meister, Jan Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2013.4},
  URN =		{urn:nbn:de:0030-drops-41601},
  doi =		{10.4230/OASIcs.CMN.2013.4},
  annote =	{Keywords: Artificial Intelligence, Planning, Narrative Generation}
}
Document
DOI: 10.4230/DagSemProc.09341.2
09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments

Authors: Michael Beetz, Oliver Brock, Gordon Cheng, and Jan Peters

Published in: Dagstuhl Seminar Proceedings, Volume 9341, Cognition, Control and Learning for Robot Manipulation in Human Environments (2010)

Abstract
High performance robot arms are faster, more accurate, and stronger than humans. Yet many manipulation tasks that are easily performed by humans as part of their daily life are well beyond the capabilities of such robots. The main reason for this superiority is that humans can rely upon neural information processing and control mechanisms which are tailored for performing complex motor skills, adapting to uncertain environments and to not imposing a danger to surrounding humans. As we are working towards autonomous service robots operating and performing manipulation in the presence of humans and in human living and working environments, the robots must exhibit similar levels of flexibility, compliance, and adaptivity. The goal of this Dagstuhl seminar is to make a big step towards pushing robot manipulation forward such that robot assisted living can become a concrete vision for the future. In order to achieve this goal, the computational aspects of everyday manipulation tasks need to be well-understood, and requires the thorough study of the interaction of perceptual, learning, reasoning, planning, and control mechanisms. The challenges to be met include cooperation with humans, uncertainty in both task and environments, real-time action requirements, and the use of tools. The challenges cannot be met by merely improving the software engineering and programming techniques. Rather the systems need built-in capabilities to deal with these challenges. Looking at natural intelligent systems, the most promising approach for handling them is to equip the systems with more powerful cognitive mechanisms. The potential impact of bringing cognition, control and learning methods together for robotic manipulation can be enormous. This urge for such concerted approaches is reflected by a large number of national and international research initiatives including the DARPA cognitive systems initiative of the Information Processing Technoloy Office, various integrated projects funded by the European Community, the British Foresight program for cognitive systems, huge Japanese research efforts, to name only a few. As a result, many researchers all over the world engage in cognitive system research and there is need for and value in discussion. These discussions become particularly promising because of the growing readiness of researchers of different disciplines to talk to each other. Early results of such interdisciplinary crossfertilization can already be observed and we only intend to give a few examples: Cognitive psychologists have presented empirical evidence for the use of Bayesian estimation and discovered the cost functions possibly underlying human motor control. Neuroscientists have shown that reinforcement learning algorithms can be used to explain the role of Dopamine in the human basal ganglia as well as the functioning of the bea brain. Computer scientists and engineers have shown that the understanding of brain mechanisms can result into realiable learning algorithms as well as control setups. Insights from artificial intelligence such as Bayesian networks and the associated reasoning and learning mechanisms have inspired research in cognitive psychology, in particular the formation of causal theory in young children. These examples suggest that (1)~successful computational mechanisms in artificial cognitive systems tend to have counterparts with similar functionality in natural cognitive systems; and (2)~new consolidated findings about the structure and functional organization of perception and motion control in natural cognitive systems indicate in a number of cases much better ways of organizing and specifying computational tasks in artificial cognitive systems.
Cite as

Michael Beetz, Oliver Brock, Gordon Cheng, and Jan Peters. 09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments. In Cognition, Control and Learning for Robot Manipulation in Human Environments. Dagstuhl Seminar Proceedings, Volume 9341, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{beetz_et_al:DagSemProc.09341.2,
  author =	{Beetz, Michael and Brock, Oliver and Cheng, Gordon and Peters, Jan},
  title =	{{09341 Summary – Cognition, Control and Learning for Robot Manipulation in Human Environments}},
  booktitle =	{Cognition, Control and Learning for Robot Manipulation in Human Environments},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9341},
  editor =	{Michael Beetz and Oliver Brock and Gordon Cheng and Jan Peters},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09341.2},
  URN =		{urn:nbn:de:0030-drops-23647},
  doi =		{10.4230/DagSemProc.09341.2},
  annote =	{Keywords: Mobile manipulation, cognition, control, learning, humanoid robot, unstructured environments}
}
Document
DOI: 10.4230/DagSemProc.09291.12
Creative Computers, Improvisation and Intimacy

Authors: Michael Young

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
Autonomous musical machine partners, ‘live algorithms’, are able to collaborate with human improvisers on an equal footing. Adaptability can be a significant factor in human/machine interaction in this context. Intimacy is an additional factor; intimacy might be achieved if human and machine performers can adapt to each other and learn from one another. Previously associated in computer music with ideas of embodiment and HCI, ‘intimacy’ as more widely understood, refers to the interpersonal process enjoyed between individuals, in which personal self-disclosure finds validation through a partner’s response. Real intimacies are learned over time, not designed, and are based upon an evident reciprocity and emergent mutuality. In the context of musical expression, a social – rather than a biological/technological –discourse can be applied to live algorithms with a capacity for learning. This possibility is explored with reference to the author’s various improvisation/composition systems including au(or)a, piano_prosthesis, and oboe_prosthesis.
Cite as

Michael Young. Creative Computers, Improvisation and Intimacy. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{young:DagSemProc.09291.12,
  author =	{Young, Michael},
  title =	{{Creative Computers, Improvisation and Intimacy}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.12},
  URN =		{urn:nbn:de:0030-drops-22222},
  doi =		{10.4230/DagSemProc.09291.12},
  annote =	{Keywords: Computational creativity, improvisation, intimacy, composition, live algorithm, neural network, computer music, adaptation}
}
Document
DOI: 10.4230/DagSemProc.09291.28
Stimulating creative flow through computational feedback

Authors: Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
This report summarises the discussion and experimental work produced by the authors at the 2009 symposium Computational Creativity: An Interdisciplinary Approach, Dagstuhl Leibniz-Zentrum für Informatik. It outlines the motivation for using computational techniques to stimulate human creativity, briefly summarising its historical context and predecessors, and describes two software studies produced by the group as base-line exemplars of these ideas.
Cite as

Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter. Stimulating creative flow through computational feedback. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:DagSemProc.09291.28,
  author =	{Jones, Daniel and Bown, Oliver and McCormack, Jon and Pachet, Francois and Young, Michael and Berry, Rodney and Asaf, Iris and Porter, Benjamin},
  title =	{{Stimulating creative flow through computational feedback}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.28},
  URN =		{urn:nbn:de:0030-drops-22232},
  doi =		{10.4230/DagSemProc.09291.28},
  annote =	{Keywords: Computational creativity}
}
Document
DOI: 10.4230/DagSemProc.06101.2
06101 Report – Spatial Data: mining, processing and communicating

Authors: Jörg-Rüdiger Sack, Monika Sester, Michael Worboys, and Peter van Oosterom

Published in: Dagstuhl Seminar Proceedings, Volume 6101, Spatial Data: mining, processing and communicating (2006)

Abstract
This workshop has been organized as a successor to four preceding ones. The major goal has been to bring together experts from digital cartography, spatial modelling, computational geometry and cognitive science to meet with professionals from data mining and data interpretation. This has lead to a fruitful exchange of different – but very close – disciplines and hopefully to the creation of new collaborations. The Dagstuhl seminar has not only posed R&D problems, but provided crucial incentives and directions shaping the entire field. The group of participants was diverse both w.r.t. to their academic discipline and their professional background. Researchers and developers from within industry, government, and universities (senior and young) sha-red their latest topics, problems, doubts, and investigations.
Cite as

Jörg-Rüdiger Sack, Monika Sester, Michael Worboys, and Peter van Oosterom. 06101 Report – Spatial Data: mining, processing and communicating. In Spatial Data: mining, processing and communicating. Dagstuhl Seminar Proceedings, Volume 6101, pp. 1-5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{sack_et_al:DagSemProc.06101.2,
  author =	{Sack, J\"{o}rg-R\"{u}diger and Sester, Monika and Worboys, Michael and van Oosterom, Peter},
  title =	{{06101 Report – Spatial Data: mining, processing and communicating}},
  booktitle =	{Spatial Data: mining, processing and communicating},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6101},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Monika Sester and Peter van Oosterom and Michael Worboys},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06101.2},
  URN =		{urn:nbn:de:0030-drops-5908},
  doi =		{10.4230/DagSemProc.06101.2},
  annote =	{Keywords: Data mining, digital cartography, data interpretation, spatial data}
}
  • Refine by Author
  • 4 Young, R. Michael
  • 2 Barot, Camille
  • 2 Young, Michael
  • 1 Aichholzer, Oswin
  • 1 Amos-Binks, Adam
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Generating functions
  • Show More...

  • Refine by Keyword
  • 2 Computational creativity
  • 2 narrative
  • 1 Approximation algorithm
  • 1 Artificial Intelligence
  • 1 Contention resolution
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 2 2009
  • 2 2015
  • 2 2016
  • 2 2018
  • 1 2006
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact