Empirical Characterization of Discretization Error in Gradient-based Algorithms

Jonathan Bachrach; Jacob Beal; Joshua Horowitz; Dany Qumsiyeh

doi:10.1109/SASO.2008.53

Back

Conference proceeding

Empirical Characterization of Discretization Error in Gradient-based Algorithms

Jonathan Bachrach, Jacob Beal, Joshua Horowitz and Dany Qumsiyeh

SASO 2008: SECOND IEEE INTERNATIONAL CONFERENCE ON SELF-ADAPTIVE AND SELF-ORGANIZING SYSTEMS, PROCEEDINGS, pp.203-212

01/01/2008

DOI: 10.1109/SASO.2008.53

View Online

Abstract

Many self-organizing and self-adaptive systems use the biologically inspired "gradient" primitive, in which each device in a network estimates its distance to the closest device designated as a source of the gradient. Distance through the network is often used as a proxy for geometric distance, but the accuracy of this approximation has not previously been quantified well enough to allow predictions (if the behavior of gradient-based algorithms. We address this need with an empirical characterization of the discretization error of gradient on random unit disc graphs. This characterization has uncovered two troublesome phenomena: an unsurprising dependence of error on source shape and an unexpected transient that becomes a major source of error at high device densities. Despite these obstacles, we are able to produce a quantitative model of discretization error for planar sources at moderate densities, which we validate by using it to predict error of gradient-based algorithms for finding bisectors and communication channels. Refinement and extension of the gradient discretization error model thus offers the prospect of greatly improving the engineerability of self-organizing systems on spatial networks.

Computer Science

Computer Science, Theory & Methods

Engineering

Engineering, Electrical & Electronic

Science & Technology

Technology

Details

Title: Subtitle: Empirical Characterization of Discretization Error in Gradient-based Algorithms
Creators: Jonathan Bachrach - MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA
Jacob Beal - MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA
Joshua Horowitz - MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA
Dany Qumsiyeh - MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA
Contributors: S Brueckner (Editor)
P Robertson (Editor)
U Bellur (Editor)
Resource Type: Conference proceeding
Publication Details: SASO 2008: SECOND IEEE INTERNATIONAL CONFERENCE ON SELF-ADAPTIVE AND SELF-ORGANIZING SYSTEMS, PROCEEDINGS, pp.203-212
Publisher: IEEE
DOI: 10.1109/SASO.2008.53
ISSN: 1949-3673
Number of pages: 10
Language: English
Date published: 01/01/2008
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984627194402771

Metrics

1 Record Views